Contest

SIMPLE

# PROBLEM:

Given a length 2^N array A of positive integers. You have to perform the following operations, until impossible:

• pair each number with exactly one other number from the array, such that the absolute difference between the numbers is \le 1.
• Replace the array with the values of sum of the elements of each pair.

Determine if it is possible to make the length of the array equal 1.

# EXPLANATION:

Claim: The answer is `YES` if and only if \max A - \min A\le 1.

Proof

The proof has two parts - proving the answer is `NO` when \max A - \min A > 1 and, `YES` when \max A - \min A\le 1.

Proof of the former

We show that at the end of every operation, \max A-\min A is always greater than 1 (which implies it is impossible to merge the two elements in the N^{th} operation).

Let x=\min A and y=\max A. After executing a valid operation on A, the minimum value in the resultant array is either x+x or x+x+1. Similarly, the maximum value is either y+y or y+y-1.

Then, using y-x>1, itâ€™s trivial to prove that the absolute difference between the minimum and maximum (over all possible pairs of values) is greater than 1.

Proof of the latter

Sort A in non-decreasing order. Let n be the length of the array.
For the current operation, merge A_i and A_{n-i+1}, for all valid i.

It is not hard to see that the absolute difference between the minimum and maximum value in the resultant array is still \le 1. Thus, we can do the above recursively until only one element remains!

Thus proved.

Then, output `YES` if the above equation holds, and `NO` otherwise!

O(N)

per test case.

# SOLUTIONS:

Editorialistâ€™s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters