MINREDSR - 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:

Easy

PREREQUISITES:

Greedy

PROBLEM:

There are N boxes in a row, each with a distinct value in [1, N].
Initially, all boxes are red.

You can color some of the boxes blue, then do the following:

  • Choose two blue boxes. Move the later blue box to just before the earlier one.

Find the minimum number of boxes that need to be colored blue, so that it’s possible to sort the values on the boxes.

EXPLANATION:

Rather than minimizing the number of blue boxes, we’ll try to maximize the number of red boxes.

First, let’s see which boxes at all can be left red.

Consider some box i with value P_i.
Observe that if there exists a box j \lt i with P_j \gt P_i, then we cannot leave box i red.
This is because the only way of moving boxes is to move blue boxes left; so if a red box has a larger value to its left then that larger value will always remain to its left - which in turn means the array can never be sorted.

Thus, the only possible candidates for boxes that can be left red, are prefix maximums of the array P, i.e. those i for which P_i \gt \max(P_1, \ldots, P_{i-1}).

However, we can’t really leave every prefix maximum red, even if that would be optimal for us.
This is because of how the operation works: a blue box can only be moved left to another blue box.
In particular, this means that if we leave boxes i and i+1 both red, then it’s impossible for us to ever place a blue box between them - they’ll always be adjacent to each other.

So, it’s only allowed to color boxes i and i+1 red if we have P_{i+1} = P_i + 1, since any other value for P_{i+1} would require us to move something between these adjacent boxes, which is impossible.

Note that this also applies to the first box in a way; where we can only choose box 1 to be red if P_1 = 1.

As seen above, we can only choose prefix maximums to leave red; and adjacent boxes can be left red only when they’re consecutive values (with the first box only being allowed red if it has value 1.)

Choosing red boxes under these constraints is sufficient to ensure that the boxes can be sorted.
The construction is simple:

  • If P_1 = 1 then it’s already in place.
  • If P_1 \gt 1, then all values smaller than P_1 are not prefix maximums.
    So, all of them would have been marked blue.
    But since P_1 \gt 1, P_1 is also marked blue.
  • Thus, we can simply move all values smaller than P_1 to before P_1 using the operation.
    If we do this in descending order of value, they’ll be sorted here.
  • Thus, whether P_1 = 1 or P_1 \gt 1, we’re able to create a sorted prefix of the values 1, 2, \ldots, P_1.
  • Now simply discard this prefix and apply the same argument to the remaining suffix.
    The “only consecutive red values” condition ensures that if the first element of the remaining suffix is not its minimum element, then it is guaranteed to be colored blue.

This gives rise to a simple greedy solution: process boxes from left to right, and simply leave the current box red if it satisfies the condition (i.e. is a prefix maximum, and either the preceding box was blue, or the preceding box was red and their values are consecutive.)

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = [0] + list(map(int, input().split()))

    ans = 0
    take = [0]*(n+1)
    take[0] = 1
    mx = 0
    for i in range(1, n+1):
        mx = max(mx, a[i])

        if a[i] == mx:
            if take[i-1] == 0: take[i] = 1
            elif a[i-1] == a[i]-1: take[i] = 1
    print(n - sum(take[1:]))
1 Like
MINREDSR2 - Editorial