PROBLEM LINK:
Setter: Razaul Hasan Ansari
Tester: Nitin Pundir
Editorialist: Rishav Sharma
DIFFICULTY
Easy
PREREQUISITES
Observation.
PROBLEM
Razaul is having a new year party at his home. There are a total of N people in the party(including himself). He decided to pour cocktails for everyone. The i-th glass has ai amount of cocktail(the amount of cocktail is measured in whole numbers Eg. 1,2,13986 ..). He then remembered that he doesn’t drink so he took one of the glasses at random and divided all of its contents among the rest of the N−1 glasses.
Razaul wants that after doing so all the glasses must have an equal amount of cocktail. You decided to help and poured a total X amount of extra cocktail into the glasses(can be one or many) so as when he divides the contents of one of the random glasses all the glasses have equal amount.
What is the value of X ?
OBSERVATION
The task here to Razaul is to empty the ith drink he’s chosen and wants all the other N-1 drinks to contain equal amounts of cocktail. That means, that the sum of the array must be divisible by (n-1) and the amount of cocktail in each glass must be ceil(sum/n-1).
On the other side, since Razaul chooses the glass at random, then he can choose a glass which is NOT the maximum, and since he empties it, then the final amount in each glass must at least be max.
In total, the resulting number of cocktail, in each of the glass(except the chosen one) must at least be q = max(ceil(sum/n-1), maxx), where maxx = maximum element in the array. And, we need to add at least (n-1)*q - sum elements to the initial array.
TIME COMPLEXITY
The time complexity is O(N) as we traverse the array one time to find the maximum of the array.
SOLUTION
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
int t;
cin>>t;
while(t–)
{
ll sum=0,mx=0,n;
cin>>n;
for(int i=0;i<n;i++)
{
ll k;
cin>>k;
mx=max(mx,k);
sum+=k;
}
ll c = ceil((sum1.0)/(n-1));
ll need=max(mx,c);
cout<<need(n-1)-sum<<endl;
}
}
Tester's Solution
#include "bits/stdc++.h"
#define ll long long
using namespace std;
ll md=1000000007;
ll diff=-1;
string mins;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t–)
{
ll n;
cin>>n;
vector arr(n);
ll sum=0;
ll maxi=-1;
for(int i=0;i<n;i++)
{
cin>>arr[i];
sum+=arr[i];
maxi=max(maxi,arr[i]);
}
ll tr=maxi*(n-1);
if(tr>=sum)
cout<<tr-sum<<endl;
else
{
if((sum-tr)%(n-1)==0)
cout<<0<<endl;
else
cout<<(n-1-(sum-tr)%(n-1))<<endl;
}
}
return 0;
}