MEXRANGE - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a binary string S of length N+1.
Construct any array A of length N such that:

  • 0 \le A_i \le N
  • S_i = 1 if and only if some subarray of A has MEX equal to i.

It’s guaranteed that A_0 = A_1 = 1.

EXPLANATION:

There are several possible constructions - here is a relatively simple one.

Let’s start with A = [0, 1, 2, \ldots, N-1].
Observe that for this array:

  • The prefix [0, 1, 2, \ldots, i] has a MEX of i+1.
  • We can also obtain a MEX of 0 by taking the subarray [1], for example.

This array thus gives us every possible MEX from 0 to N.
Importantly, for any i \gt 0, note that the prefix [0, 1, \ldots, i-1] is the only subarray with a MEX of i.

Now, it might be the case that we don’t want all the MEX-es.
So, suppose we have S_i = 0 for some i.
One way to “turn off” the MEX of i, is to simply swap the values i and i-1.
That is, turn the array into A = [0, 1, 2, \ldots, i-2, \ \ \underline{i, i-1}, \ \ i+1, \ldots, N-1].

This ensures that i doesn’t appear as a prefix MEX, because once we have all the values 0, 1, 2, \ldots, i-1, we’ll also have to include i itself in the subarray - so the MEX becomes i+1 instead.
On the other hand, it can also be seen that this doesn’t change any of the other prefix MEX-es.

This idea easily generalizes to turning off any other MEX-es as well.
That is, we have the following:

  • Start with A = [0, 1, 2, \ldots, N-1].
    For convenience, we treat A as being 0-indexed, so that A_i = i initially.
  • Now, for each i such that S_i = 0 in order from left to right, simply swap A_i and A_{i-1}.
    Note that A_{i-1} might not equal i-1 (because of a previous swap), but it will certainly be some value \lt i, and that’s enough for us.
    This swap does the following:
    • The prefix ending at index i-1 now has the set of values \{0, 1, 2, \ldots, i-2, i\}, with a MEX of i-1.
      Earlier, it used to have a MEX of i.
    • All other prefixes have exactly the same set of elements they had before; so their MEX-es don’t change.
      This means we’ve exactly eliminated the MEX of i, while not affecting anything else.

This allows us to eliminate all the MEX-es we don’t need, while retaining the ones we do need.

There is one edge case: since we’re just swapping elements, the MEX of the entire array will always remain N.
So, if S_N = 0, we need an additional step: set A_{N-1} = N, so that N doesn’t appear as a MEX.

One way of seeing this, is that we’re performing our swapping algorithm on the array A = [0, 1, \ldots, N] of length N+1, and then printing its first N elements.
This interpretation allows for an implementation that avoids having to casework out S_N = 0.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    a = list(range(n+1))
    for i in range(2, n+1):
        if s[i] == '0':
            a[i], a[i-1] = a[i-1], a[i]
    print(*a[:n])