LARGESTLADDU - Editorial

PROBLEM LINK:

Contest

DIFFICULTY:

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!

TIME COMPLEXITY:

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