PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
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
-
cnt_1 < cnt_0 : 2 \cdot cnt_1 : We start and end the sequence with a 0.
-
cnt_0 < cnt_1 : 2 \cdot cnt_0 : We start and end the sequence with a 1.
-
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;
}
