NOADJK - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given an array A and a parameter K.
A valid subsequence (i_1, \ldots, i_r) is one such that no two adjacent indices belong to it, and any segment of length K contains at least one chosen index.

Across all valid subsequences, find the maximum possible value of

\max(A_{i_1}, A_{i_2}, \ldots, A_{i_r}) - \min(A_{i_1}, A_{i_2}, \ldots, A_{i_r})

EXPLANATION:

First, let’s look at K = 2.
We want to ensure that no adjacent indices are picked; and also that among every two consecutive indices, at least one is chosen.
This greatly constrains our choices: in particular, observe that the only valid sequences of indices are

(1, 3, 5, 7, \ldots) \quad \text{ and } \quad (2, 4, 6, 8, \ldots)

That is, either we take all odd indices, or all even indices.

For each choice, the difference between maximum and minimum can be computed, and we take the best one among them.

Next, let’s look at K \ge 3.
We have a bit more freedom now.

Since we’re not allowed to choose adjacent elements, clearly the best possible answer is just the maximum difference between two non-adjacent elements of A.
That is, the absolute best we can hope for is for the maximum possible value of
|A_i - A_j| across all pairs of indices (i, j) such that i+1 \lt j.

It turns out that for K \ge 3, we have enough freedom that this is always attainable!

Proof

Let i and j be the two indices we pick; i \lt j.
Without loss of generality, let A_i \le A_j.

Observe that for any index k such that |i-k| \gt 1 and |j-k| \gt 1, we must have A_i \le A_k \le A_j.
That is, any element not adjacent to indices i and j must have its value in [A_i, A_j].
This is because, if it didn’t, then picking index k would result in a larger difference instead (for example if A_k \lt A_i we could choose indices (k, j) instead of (i, j) and obtain a larger difference.)

Now that we know this, observe that we can choose the following subset:

  • Indices i, i-2, i-4, i-6, \ldots till either index 1 or 2, depending on parity.
  • Indices j, j+2, j+4, \ldots till either index N or N-2, depending on parity.
  • Indices i+2, i+4, \ldots till either index j-2 or j-3 depending on parity.

This will in fact cover every subarray of length 3 (and so everything of length \ge 3 as well), while ensuring that A_i and A_j are the min/max of the subset respectively, so the required difference is obtained.

So, when K \ge 3 we only need to compute the maximum non-adjacent difference between two elements of the array.

There are many ways to do this quickly; one of them is as follows.

  • Iterate j = 3, 4, 5\ldots in order.
    While performing this iteration, also maintain the minimum and maximum elements among indices 1, 2, \ldots, j-2.
  • This minimum and maximum can be easily maintained; since when processing index j we only need to update them with the value A_{j-2}.
  • Let this prefix minimum/maximum be m_1 and m_2, respectively.
    Then, update the answer with |A_j - m_1| and |A_j - m_2|, since if A_j is the second element then for the maximum difference the first element should be either minimized or maximized.

This allows us to compute the answer in linear time.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    assert min(a) >= 1 and max(a) <= 10**9
    
    if k == 2:
        a1, a2 = a[::2], a[1::2]
        print(max(max(a1) - min(a1), max(a2) - min(a2)))
    else:
        mn, mx = a[0], a[0]
        ans = 0
        for i in range(2, n):
            ans = max(ans, a[i] - mn)
            ans = max(ans, mx - a[i])

            mn = min(mn, a[i-1])
            mx = max(mx, a[i-1])
        print(ans)
2 Likes