TIES - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: still_me
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

1289

PREREQUISITES:

None

PROBLEM:

You have an array A.
In one move, you can choose an integer k \geq 1 and two indices i and j, and move 2^k from A_i to A_j. However, the elements of A must remain non-negative at all times.

Can all the elements of A be made equal?

EXPLANATION:

First, observe that performing an operation doesn’t change the overall sum of the array, since we’re just moving values around a bit.

Let S = A_1 + A_2 + \ldots + A_N be the sum of the array elements.
Suppose we’re able to make all the elements equal, say to y.
Then, the sum of the final array is just N\cdot y, which should equal S.
This uniquely fixes y = \frac{S}{N}.

In particular, N must divide S — if it doesn’t, the answer is immediately No.

Next, we need to check if everything can indeed be made equal to y = \frac{S}{N}.
We’re allowed to move any powers of 2 other than 2^0 = 1.
Notice that since we have unlimited moves, we can just move exactly 2 at each step (do you see why?)

In other words, our operation is just “move 2 from one element to another”.
For an element A_i to be able to reach y at all using this operation, we must have |y - A_i| be even, since each element can only be increased/decreased by 2.

We now have two conditions:

  • N should divide S.
  • For every i, |A_i - y| should be even (where y = \frac{S}{N}).
    Equivalently, every A_i should have the same parity as y.

These two conditions are sufficient for the answer to be Yes!

How?

The argument to show this is quite simple.
Consider a situation where not all the A_i are equal to y = \frac{S}{N}.
Since their sum is S, this means some element has to be strictly greater than y and some other element has to be strictly less than y.

Now, just move 2 from the larger element to the smaller one.
Repeat this till all the A_i become equal.

This gives us a solution in \mathcal{O}(N): check the above two conditions; if they’re both satisfied the answer is Yes, otherwise it’s No.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    S = sum(a)
    if S%n != 0: print('No')
    else:
        target = S//n
        ans = 'Yes'
        for i in range(n):
            if a[i]%2 != target%2: ans = 'No'
        print(ans)
2

Here is the code in cpp-
include
#include<bits/stdc++.h>

using namespace std;

int main() {
// your code goes here
int t;cin>>t;
while(t–){
int n;cin>>n;
vectora;

    for(int i =0; i<n; i++){
        int b; cin>>b;
        a.push_back(b);
   
    }
   
    
     int long long sum=0;
     for(int i=0;i<n;i++){
         sum += a[i];
     }
     
         int ct =0;
     if(sum%n==0){
         int Y = sum/n;
         for(int i =0; i<n;i++){
             if(abs(a[i]-Y)%2==0)ct++;
         }
          
     }
     if(ct==n)cout<<"Yes"<<endl;
     else cout<<"No"<<endl;
     
}   
return 0;

}