OPAR - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: hellolad
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A of odd length.
In one move, you can choose a valid index i, delete A_{i-1}, A_i, A_{i+1}, and insert \max(A_{i-1}+1, A_i, A_{i+1}+1) in their place.
One element will remain in the end. Find its maximum possible value.

EXPLANATION:

N is odd, so let’s write N = 2k+1 for some k \geq 0.
Each move decreases the length of the array by 2, so we’ll end up performing exactly k moves.

Now, we want to maximize the last remaining element.
An operation on index i either places A_i back into the array, or one of A_{i-1}+1 or A_{i+1}+1.
The second case is clearly ideal since it’s the only way we can increase an element.

Let M = \max(A) denote the maximum element present in A.
Ideally, we’d like to increase this maximum with every operation, i.e. the first operation should insert M+1, the second should insert M+2, and so on till the last operation inserts M+k (which is clearly the absolute maximum attainable).
However, this isn’t always possible (as seen with the example [1, 2, 1]), so the goal is now to analyze when it is indeed possible (and what to do when it’s not).

Given that our goal is to repeatedly increase the maximum, this means that every move we make must have the maximum as one of its endpoints: it cannot be the middle element among the three.
Essentially, every operation must delete two elements from either the left or the right of the maximum - this is the only way it can be increased.

Now, it’s not hard to see that this is almost always possible: if N \geq 4 then we can always find two elements to either the left or the right of any given element, so the maximum can always be increased.
The only “bad” case is when N = 3 and the maximum is in the middle (as well as the trivial case of N = 1 where no operations can be performed).

In particular, this means that no matter what N is, we can always increase the maximum on every operation except maybe the last.
So, the answer is definitely at least M+(k-1).
Further, we’ll be unable to perform the last increase only when we reach a state where there are three elements left, and the maximum is in the middle.
But, when exactly will we reach this state?

Here, we use the observation that we’re deleting two elements from the left/right of the maximum in every move.
Suppose the maximum is initially at index i.
Then, after performing a move that increases the maximum, its index will either remain the same, or decrease by 2. In particular, its parity will not change.
So, if i is even, when there are three elements remaining it must be the middle element, and if i is odd then it will never be the middle element.

In the end, we end up with an extremely simple check.
Recall that N = 2k+1 and M = \max(A).
Then,

  • If there’s an odd index i (in 1-based indexing) such that A_i = M, the answer is M+k.
  • Otherwise, the answer is M+k-1.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    k = n//2
    a = list(map(int, input().split()))
    M = max(a)
    
    if max(a[::2]) == M: # Check if maximum of odd indices is M
        print(M+k)
    else:
        print(M+k-1)