MKEQ - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: watoac2001
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have an array A. In one move, you can choose any index i (1 \lt i \lt N) such that
A_{i-1} \leq A_i \geq A_{i+1}, and reduce A_i by 1.

Is it possible to perform several of these moves such that the final array consists of all equal elements?

EXPLANATION:

Let’s make a couple of observations:

  • Only elements in the ‘middle’ of the array can be changed; the endpoints cannot.
    That is, A_1 and A_N can never change their values.
    So, if A_1 \neq A_N, they can never be made equal, and the answer is No.
  • We’re only allowed to decrease elements.
    In particular, if some element starts out smaller than A_1, we’re out of luck: neither can it be increased to reach A_1 nor can A_1 be decreased; so the answer is No.

We’re now left only with arrays such that A_1 = A_N, and A_i \geq A_1 for every i.
For all such arrays, it’s indeed possible to make all the elements equal!

Proof

There’s a pretty simple strategy: till the condition is satisfied, repeatedly choose the maximum element of the array and apply the operation on it (if there are multiple maximums, it doesn’t matter which one is chosen).

This works because, since we can’t change A_1 and A_N, the maximum must always be \geq A_1.
When the maximum becomes A_1 we immediately stop since no element is larger and nothing has been made smaller than A_1, so everything’s definitely equal now.

Since we choose the maximum at each step, and only when it’s \gt A_1, it will be at some index that’s not 1 or N (and hence can be operated on); and since it’s the maximum it’s surely greater than or equal to both of its neighbors.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    print('Yes' if a[0] == a[-1] and a[0] == min(a) else 'No')