PROBLEM LINK:
Author: Sibasish Ghosh
Tester: Pritish Nayak
Editorialist: Sibasish Ghosh
DIFFICULTY:
Simple
PREREQUISITES:
Basic Maths, Greedy
PROBLEM:
You are given N integers A_1,A_2,...,A_N and you can apply the following operations any number of times:
- Choose two distinct integers i and j(1\leq i,j\leq N) and do:
- A_i=A_i+1 and,
- A_j=A_j-1
- Choose an integer i(1\leq i\leq N) and do A_i=A_i+1.
You have to make all the integers equal by performing the minimum number of operations.
QUICK EXPLANATION:
- Calculate avg=\lceil \frac{\sum_{i=1}^{N} A_i}{N} \rceil.
- Answer is \sum_{i=1}^{N} max(0,A_i-avg).
EXPLANATION:
First, we will try to make the distribution as uniform as possible by only using the 1^{st} operation. Calculate x=\lfloor \frac{\sum_{i=1}^{N} A_i}{N} \rfloor. Now for every A_i that is less than x, there must be an A_j that is greater than x. So we can always transfer a 1 between such indices. When all such indices are over, the array will become something like x,x,x,x+1,x+1,...x+1 (try it on a piece of paper if you don’t understand why). Note that the number of (x+1)'s might be zero as well (it will happen when \sum_{i=1}^{N} A_i is divisible by N). Now, all we have to do is add 1's to all x's to make all the array elements equal to x+1. We can do so by applying the 2^{nd} operation.
Now, if you notice carefully, the total number of operations needed is equal to \sum_{i=1}^{N} max(0,A_i-avg), where avg=\lceil \frac{\sum_{i=1}^{N} A_i}{N} \rceil.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input5.txt","r",stdin);
// freopen("output5.txt","w",stdout);
ll t=1;
cin>>t;
while(t--)
{
ll n,i,ans=0;
cin>>n;
ll a[n+10],sum=0;
for(i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
ll avg=ceil(1.0*sum/n);
for(i=1;i<=n;i++)
{
if(a[i] < avg)
ans+=(avg-a[i]);
}
cout<<ans<<"\n";
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
assert(t>=1);
assert(t<=10);
while(t--)
{
int n;
cin>>n;
long long a[n],ans=0,tot=0,each=0,loot=0;
for(int i=0;i<n;i++){
cin>>a[i];
tot+=a[i];
}
if(tot%n!=0){
loot+=n-tot%n;
tot+=n-tot%n;
}
each=tot/n;
for(int i=0;i<n;i++)
if(a[i]>each)ans+=a[i]-each;
ans+=loot;
cout<<ans<<'\n';
}
return 0;
}
Feel free to write your approach in the comments