MMAX - Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Mayank Agarwal

Tester : Alipasha Montaseri / Kasra Mazaheri

Editorialist : Anand Jaisingh

DIFFICULTY :

Simple

PREREQUISITES :

None

PROBLEM :

You need to distribute K chocolates among N people, such that if the i^{th} person receives A[i] chocolates, the sum S_1= \sum_{i=1}^{N} abs(A[i]-A[i-1]) is minimum.

Now, after doing so, you need to rearrange the elements of array A in such a way that the sum S_2=\sum_{i=1}^{N} abs(A[i]-A[i-1]) is maximum. You need to print this number.

However, there is a small catch here. The number K may be as large as 10^{10^5}

QUICK EXPLANATION :

It can be proved that the number S_1 = 1 if K \mod N \ne 0 , else S_1=0 . Now, once we know K \mod N and N - (K \mod N) , then we can calculate S_2 in O(1), that is a function of these 2 parameters.

EXPLANATION :

The first thing that comes to mind after reading the statement is, how can we deal with K so large ? A crucial observation one can make to simplify this issue is the following :

Claim 1:

Only the value K \mod N matters for calculating S_1.

Proof :

If K \mod N = 0 , then we can give each of the participants \frac{K}{N} chocolates, and the value of S_1 is 0 else, for K \mod N > 0, we can given the first K \mod N people \left\lfloor \frac{K}{N} \right \rfloor +1 chocolates, and the rest of the people \left \lfloor \frac{K}{N} \right \rfloor chocolates.

In this case the the value of S_1 is 1, and it’s quite simple to see we cannot achieve a lower value. It can also easily be proved that any such sequence that guarantees S_1=1 can only be the sequence above or that sequence reversed.

Now, once we know all the information we’ve gathered above, the final answer can be built as follows :

Let’s consider that each person we initially gave \left\lfloor\frac{K}{N} \right \rfloor+1 chocolates, actually gets only 1 chocolate, and the other people get 0 chocolates.

The problem : Rearrange these 0's and 1's in such a manner so as to maximize S_2 can be seen is totally equivalent to the problem we were originally trying to solve.

The maxima, can be seen, is achieved in the scenario when these 0's and 1's are alternated for as long as possible. We just need to find the largest length of an alternating sequence we can construct with these and that’s the answer we need.

Here are the cases for those :

Let cnt_ 1= K \mod N , cnt_0=N-cnt_1

  1. cnt_1 < cnt_0 : 2 \cdot cnt_1 : We start and end the sequence with a 0.

  2. cnt_0 < cnt_1 : 2 \cdot cnt_0 : We start and end the sequence with a 1.

  3. cnt_0 = cnt_1 : 2 \cdot cnt_1 -1 : We create a fully alternating sequence, beginning with a 0/1

All of these can be proved quite simply by drawing these sequences on paper and examining them.

And, finally we can find the value of K \mod N as follows :

   // k is taken into input as a string...

    int now=0;

    for(int i=0;i<k.size();i++)
    {
        now=(now*10)%n;

        now=(now+k[i]-'0')%n;
    }  

That’s it, we’re done. Your comments are welcome !

COMPLEXITY ANALYSIS :

Time Complexity : O(\log_{10} (K))

Space complexity : O(\log_{10}((K)))

SOLUTION LINKS :

Setter
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define ll long long int
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
 
 
int main()
{
	//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      // freopen("in06.txt","r",stdin);
      // freopen("out06.txt","w",stdout);
 	int i,j,x,y,t;
    cin>>t;
    assert(0<t && t<=10);
    while(t--){
    	int n;
    	string k;
    	cin>>n;
    	cin>>k;
 
        assert(0<n && n<=100000);
        int l = k.length();
        assert(0<l && l<=100000);
        assert(k[0]!='0');
    	//reverse(k.begin(),k.end());
    	int rem =0;
    	for(i=0;i<k.length();++i){
    		rem = (rem*10 + (k[i]-'0'));
    		rem%=n;
    	}
    	if(rem<(n/2)){
    		cout<<2*rem<<"\n";
    		continue;
    	}
    	if(rem==(n/2)){
    		cout<< 2*rem -1 + (n%2)<<"\n";
    		continue;
    	}
    	cout<< 2*(n-rem)<<"\n";
 
 
    }   
    
return 0;
}
Tester
def Test():
    n = int(input())
    k = int(input())
    low = min(k % n , n - k % n)
    print(min(n - 1 , low * 2))
T = int(input())
for t in range(T):
    Test()
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh

#include<bits/stdc++.h>
 
using namespace std;
 
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
 
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
 
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
 
    int t;cin>>t;
 
    while(t>0)
    {
        int n;cin>>n;string k;cin>>k;
 
        int now=0;
 
        for(int i=0;i<k.size();i++)
        {
            now=(now*10)%n;
 
            now=(now+k[i]-'0')%n;
        }
 
        if(now<n-now)
        {
            cout<<(2*now)<<endl;
        }
 
        else if(now==n-now)
        {
            int res=(2*now)-1;
 
            cout<<res<<endl;
        }
 
        else
        {
            cout<<(2*(n-now))<<endl;
        }
 
        t--;
    }
 
    return 0;
}
3 Likes

Can u please explain how this code is working, I copied the code from geeksforgeeks but couldn’t understand it.
What - ’ 0’ is doing?

2 Likes

As the value of constraints of k upto 10^100000. So we should take k as a string not a number.
(k[i]-‘0’) converts every char of string into int.

My solution: https://www.codechef.com/viewsolution/25070955

3 Likes

-‘0’ has been used to convert a char value to a numeric value. suppose if string contains character as ‘5’ so internally it is stored as an ASCII code. Since the value of ASCII ‘5’ is 53 so if subtract ASCII ‘0’ which is 48 we get numeric 5.

Same approach but i puzzled . But now I got the solution . Thank you so much

cnt1<cnt0 : 2 * cnt0
is this correct?

or it should be cnt1<cnt0 : 2 * cnt1…please explain

1 Like

Hi,
In the question it was mentioned n and k to be integers but you’ve taken k to be string…
I believe that’s the reason I was getting WA…
Please check and revert ASAP…
Thanks

1 Like

Oh I have understood the logic… No need for explaination…
Thanks

k has a constraint of 10^100000, so in most of the languages, it has to be taken as a string

loved this question brilliant for beginners got the trick after a day

1 Like

Oh we can input k as string, my bad. I applied the same logic as well.

What @anand20 ??
PREREQUISITES none ???
It needs modular arithmetic at least.
Think about beginners when you prepare editorial.

6 Likes

Yeah I think so too. But please someone reply if it’s otherwise.

It’s converting the character number into integer number.

According to the editorial -

But, shouldn’t it be the opposite? I mean, 2 must be multiplied to lesser of the two values right?

Thanx for pointing it out, I’ve made those changes

i m confused pls if k is so large 10^10000 so on iterating through it why arnt we getting TLE

The number is upto 10^100000. So we can take it as a string which is only upto 10^5.

Link of geeksforgeeks where you copied from ??:sweat_smile::sweat_smile:

googled after looking at the constraint.