EANDO Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Sandeep V
Tester: Jakub Safin, Satyam
Editorialist: Pratiyush Mishra

DIFFICULTY:

1817

PREREQUISITES:

None

PROBLEM:

Dazzler has an interesting task for you.

You will be given an array A of N positive integers. N is always even.
Exactly N/2 elements in the array will be Even and N/2 elements will be Odd.

In one operation you should do the following steps:

  • Choose two different indices i (1 \le i \le N) and j (1 \le j \le N)
  • Make A[i] = A[i] + 1
  • Make A[j] = A[j] - 1

After doing all the necessary number of operations (possibly none) you need to preserve the parity of each element as in the initial array A. For example if an element at the index i (1 \le i \le N) is even, at the end A[i] should be even

You need to find whether you can make all the odd elements in the array equal and all the even elements equal separately.

Print YES if it is possible to meet the above conditions after doing any number of operations, else print NO.

EXPLANATION:

First thing to observe is that, since we can select any i and j and change A[i] = A[i] + 1 and A[j] = A[j] - 1, so we can essentially change the array to any other array A' as long as it holds the condition \sum_{i=1}^{i=n} A'[i] = sum, where sum = \sum_{i=1}^{i=n} A[i]
Now we want the final array A' to be such that N/2 of its elements are even, say 2X and rest N/2 elements to be odd, say (2Y + 1). Thus

sum = \frac{N}{2} \times (2X + 2Y + 1)

If we subtract \frac{N}{2} from sum, we would have:

sum - \frac{N}{2} = N \times (X + Y)

Thus for such X and Y to exist, (sum - \frac{N}{2}) would have to be divisible by N.
Thus if (sum - \frac{N}{2}) is divisible by N then it is possible, otherwise its not possible.

TIME COMPLEXITY:

O(N), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

4 Likes
2

It is not obvious that any array can be formed as long as their sums are equal. Please explain more clearly.

2 Likes
4

Condition is sum- N/2 is divisible by N; So, X+Y = (sum-N/2)/N; Fix some value of X, and you will get a value for Y Example X = 0, Y = (sum-N/2)/N This means in even array you need to make all element zero, and in odd array you need to make all elements 2*Y+1, which is odd and is doable because sum is same

3 Likes
5

Ah, I see. Thinking about putting all the elements as 0 is a much more intuitive way to think about it! Thank you.

6

In editorial solution what’s the logic behind this
sum -= (n / 2);

2 Likes
7

can anyone explain me why we did sum - = n/2 ??

8

This condition must hold true
Where SUM = SUM(Array) = N/2 * even_number + N/2 * odd_number!

Now with Code, You can check the above condition in different ways!

1st Way > editorial solution →
Assume even_number = 2x , and odd_number = 2y + 1 (where x,y are integers) then
we can write SUM = N/2 * (2x) + N/2 * (2Y + 1)
=> SUM = N/2 *2X + N/2 * 2Y + N/2
=> SUM - N/2 = (N/2) * (2X + 2Y)
=> SUM - N/2 = N * (X + Y)
=> X + Y = (SUM - N/2) / N
So, We would get valid integral solutions for X and Y, if and Only If (SUM - N/2)/N is an integer , that is (SUM - N/2) % N == 0 ,

2nd WAY (The way I solved)

We need SUM = N/2 * even_number + N/2 * odd_number ,
so SUM = N/2 * (even_number + odd_number)
So, here just check if SUM % (N/2) == 0 and ((SUM / (N/2)) % 2 == 1) because SUM / (N/2) is nothing but EVEN NUMBER + ODD NUMBER that should result into an ODD NUMBER only !

5 Likes
9

The question is one to three liner,that is if the sum of all a[i] is not divisible by (n/2) then print "NO"otherwise find the divisor(sum/n). Then if the divisor is odd then print “YES” otherwise print “NO”.

10

For your 2nd solution if ( SUM % (N/2) == 0 and ((SUM / (N/2)) % 2 == 1) ) then answer will be “YES” ?

11 
    ll n;
    cin>>n;
    vector<ll> a(n);
    cin>>a;
    ll oddSum = 0; ll evenSum = 0; ll odd = 0; ll even = 0;
    for(ll i=0;i<n;i++){
        if(a[i] % 2 == 0) evenSum += a[i], even++;
        else oddSum += a[i], odd++;
    }
    auto check = [&](ll evenSum, ll oddSum){
        if(evenSum < 0 or oddSum < 0) return false;
        return ( (evenSum % even == 0) and ((evenSum / even) % 2 == 0) and (oddSum % odd == 0) and ((oddSum / odd) % 2 == 1) );
    };
    if(check(evenSum,oddSum)){
        cout << "YES" << endl;
        return;
    }
    ll E = evenSum / even;
    if(E % 2 == 1){
        ll toAdd = ((E+1) * even) - evenSum;
        if(check(evenSum+toAdd,oddSum-toAdd)){
            cout << "YES" << endl;
            return;
        }
        ll toSub = evenSum - ((E-1) * even);
        if(check(evenSum-toSub,oddSum+toSub)){
            cout << "YES" << endl;
            return;
        }
    }
    ll O = oddSum / odd;
    if(O % 2 == 0){
        ll toAdd = ((O+1) * odd) - oddSum;
        if(check(evenSum-toAdd,oddSum+toAdd)){
            cout << "YES" << endl;
            return;
        }
        ll toSub = oddSum - ((O-1) * odd);
        if(check(evenSum+toSub,oddSum-toSub)){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
12

Can anyone tell me any test case that my code is failing on?

#include<bits/stdc++.h>
using namespace std;

int main(void) {
	int t,N,x,total,temp;
	cin>>t;
	while(t--)
	{
	    total=0;
	    cin>>N;
	    temp=N;
	    while(temp--)
	    {
	        cin>>x;
	        if(x%2==1)
	            total+=x/2; //No. of 2's that can be extract from odd numbers(till 1 is left)
	        else
	            total+=x/2-1; //No. of 2's from even numbers(till 2 is left)
	    }
	    if(total%(N/2)==0)  //if number of 2's that were extracted can be distributed equally
	    cout<<"YES"<<endl;
	    else
	    cout<<"NO"<<endl;
	}
	
	return 0;
}
13

yes

14

Can anyone tell me , what is the mistake in my logic ?

I have thought that , at first , i have sorted the array, then i have stored every odd elements in a list and every even elements in another list .

i.e , if the array is 1 8 4 5 12 9 , then after sorting final array is : 1 4 5 8 9 12 , then odd=[1,5,9] and even=[4,8,12]. So now i have checked that if the difference between every pairwise continuous elements in the odd array is same or not ,

i.e, for this example odd=[1,5,9] , so 5-1=4 , and 9-5 = 4 , so if this not hold for every contiguous pair , then i print “NO” , otherwise i have checked difference between odd elements is same as the difference between even elements ,

i.e, diff_odd=4 for odd=[1,5,9] and even=[4,8,12] , now for even elements 8-4=4 and 12-8=4 , so both the difference between pairwise odd and even elements is same. So , i have print “YES” , if this condition holds true , otherwise print “NO”.

let’s take another example : a=[1,3,7,2,4,8] , so odd = [1,3,7] , even=[2,4,8] ,
Now for odd=[1,3,7] , 3-1=2 , 7-3=4 , So the difference is not same ,as 2 != 4 , So , print “NO”

Now , if a=[1,3,5,2,6,10] , here odd = [1,3,5], even = [2,6,10] , now for odd=[1,3,5] , 3-1= 2 , 5 - 3 = 2 , So every pairwise difference is same , now for even=[2,6,10] , 6 - 2 = 4 , 10 - 6 = 4 , Now as the diff_odd = 2 and diff_even = 4 , so as those are not same , print “NO”.

Can anyone please tell me , What is the mistake of my logic , Please tell me , there is any test case where my logic fails . Please help !!!

15

Hey @sohamdey345 :wave: ,
Can you please provide your code for the same?

16

it is really beautifull

17

Ya sure !!!



for _ in range(int(input())):
    # n=(int(i) for i in input().split())
    n=int(input())
    a=[int(x) for x in input().split()]
    if(n==2):
        print("YES")
    else:
        odd,even=[],[]
        for i in a:
            if(i&1):
                odd.append(i)
            else:
                even.append(i)
        odd.sort()
        even.sort()
        diffodd=odd[1]-odd[0]
        flag=True
        for i in range(1,(n//2)-1):
            if(a[i+1]-a[i]!=diffodd):
                flag=False
                break
        if(flag):
            diffeven=even[1]-even[0]
            if(diffeven==diffodd):
                flag1=True
                for i in range(1,(n//2)-1):
                    if(even[i+1]-even[i]!=diffeven):
                        flag1=False
                        break
                if(flag1):
                    print("YES")
                else:
                    print("NO")
            else:
                print("NO")
        else:
            print("NO")
18

Thank You so much :innocent: :innocent: :innocent: :innocent:

19

Hey @sohamdey345,
Your code is failing at test case
1
8
2 8 10 18 1 5 7 33
Correct output is : YES
Your output is : NO

20

Ok , Thank you so much for reviewing and helping to understand the problem clearly , I think my logic is not perfect , I will fix it , And again Thank you so much sir !!! :innocent: :innocent: :innocent: