INAMMO - Editorial

PROBLEM LINK:

Practice

Contest

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 :slight_smile:

3 Likes

Hello, sibasish_14. I would like to share my approach of solving this problem. Well, i solved it by using binary search setting the lower and upper bound to 1 and 1e9.
And for each value mid , i just checked if the sum of values to be substracted from all the elements greater than mid is lesser than or equal to the sum of values to be added to all the elements lesser than mid. If it is so, i just set
r to mid-1 else l=mid+1.

Well, your approach is also good. I found an intuitive proof for it which I would like to share.

For, making the all elements equal, we would want all the operations to be of type 1. So, in an ideal case , we choose such an x( all the values of a[] becomes equal to this value after the operation) such that

(x-a[0])+(x-a[1])+…+(x-a[i])=(a[i+1]-x)+(a[i+2]-x)+…+(a[n-1]-x);
where
after array is sorted a[i]<=x and a[i+1]>x
=> n*x=a[0]+a[1]+a[2]+…+a[n-1]
=>x=(a[0]+…+a[n-1])/n
=>x=average of the sequence

I hope this would help many people.My solution with Binary search

1 Like

Yes, your solution is also nice.