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
If we subtract \frac{N}{2} from sum, we would have:
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