Dazzling Even-Odd Challenge solution codechef

Dazzling Even-Odd Challenge solution codechef

 

Dazzler has an interesting task for you.

You will be given an array AA of NN positive integers such that:

  • NN is always even.
  • Exactly N2N2 elements in the array are even and N2N2 elements are odd.

In one operation, you should do the following steps:

  • Choose two different indices ii and jj (1i,jN)(1≤i,j≤N).
  • Set Ai:=Ai+1Ai:=Ai+1.
  • Set Aj:=Aj1Aj:=Aj−1.

You need to apply some finite (possibly zero) number of operations on the array such that:

  • The parity of the final element at each index is same as the parity of the initial element at that index. For example, if the ithith element in the initial array is even, then, the ithith element in the final array must be even as well.
  • All the N2N2 odd elements in the final array are equal.
  • All the N2N2 even elements in the final array are equal.

Print YES if it is possible to meet all the above conditions after doing some finite (possibly zero) number of operations. Otherwise, print NO.

Input Format Dazzling Even-Odd Challenge solution codechef

  • First line will contain TT, number of test cases. Then the test cases follow.
  • First line of each test case contains NN, number of elements in the array AA. Note that, NN is even.
  • Second line of each test case contains NN space-separated positive integers, the elements of the array.

Output Format

For each test case, output in a single line, YES if it is possible to meet all the given conditions after doing some finite (possibly zero) number of operations. Otherwise, print NO.

You may print each character of the string in uppercase or lowercase (for example, the strings YeSyEsyes and YES will all be treated as identical).

Constraints

  • 1T1041≤T≤104
  • 2N21052≤N≤2⋅105
  • 1A[i]1091≤A[i]≤109
  • N%2=0N%2=0
  • Sum of NN over all test cases does not exceed 21052⋅105.

Dazzling Even-Odd Challenge solution codechef Sample Input 1 

4
4
1 1 2 4
4
1 2 5 6
2
1 2
4
1 2 3 4

Sample Output 1 

NO
YES
YES
YES

Explanation Dazzling Even-Odd Challenge solution codechef

Test case 11: It is not possible to satisfy all the given conditions using any number of operations.

Test case 22: One of the possible sequence of operations is listed below:

  • In the first operation, choose i=2i=2 and j=4j=4. Thus, A2=2+1=3A2=2+1=3 and A4=61=5A4=6−1=5. The array will become [1,3,5,5][1,3,5,5].
  • In the second operation, choose i=2i=2 and j=4j=4. Thus, A2=3+1=4A2=3+1=4 and A4=51=4A4=5−1=4. The array will become [1,4,5,4][1,4,5,4].
  • In the third operation, choose i=1i=1 and j=3j=3. Thus, A1=1+1=2A1=1+1=2 and A3=51=4A3=5−1=4. The array will become [2,4,4,4][2,4,4,4].
  • In the fourth operation, choose i=1i=1 and j=3j=3. Thus, A1=2+1=3A1=2+1=3 and A3=41=3A3=4−1=3. The array will become [3,4,3,4][3,4,3,4].

Here, all the odd elements are equal and all the even elements are equal. Also, the parity at each index is preserved.

Test case 33: The array [1,2][1,2] satisfies all the conditions. Thus, 00 operations are needed.

 Solution

Click here

Leave a Comment

Your email address will not be published.