MXPERST - 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 a binary string S.
Construct any permutation of [1, N] such that:

  • If S_i = 1, there must exists a subarray of length i whose maximum element is i.
  • If S_i = 0, every subarray of length i must have its maximum element be not i.

EXPLANATION:

Since the elements of P are distinct integers from 1 to N, observe that the only way for a subarray of length i to have its maximum element be i, is for the subarray to contain all the elements [1, 2, \ldots, i] in some order.

In particular, note that this is always going to be true for i = 1 and i = N, since the subarray [1] will always be present; and the entire permutation is a rearrangement of [1, 2, \ldots, N].
So, if S_1 = 0 or S_N = 0, surely no solution can exist.

We now only concern ourselves with the case where S_1 = 1 and S_N = 1.

Now, each constraint of the form S_i = 1 tells us that [1, 2, \ldots, i] must appear as a (rearranged) subarray, while each constraint of the form S_i = 0 means that [1, 2, \ldots, i] must not appear as a (rearranged) subarray.

In particular, S_i = 0 means that we need to ‘break apart’ the values [1, 2, \ldots, i] - which is only possible by inserting a larger value in their middle.

This gives us the following construction.

  • Start with P = [1].
  • Let i_1 \gt 1 be the nearest index such that S_{i_1} = 1.
    Append the values i_1, i_1-1, i_1-2, \ldots, 3, 2 to P.
    So now P = [1, i_1, i_1-1, \ldots, 3, 2].
    Observe that for any 1 \lt x \lt i_1, if a subarray contains both 1 and x then it will also contain i_1. So, certainly the values [1, 2, \ldots, x] don’t appear as a (rearranged) subarray.
    This satisfies all values till i_1.
  • Next, simply repeat this process: let i_2 \gt i_1 be the next index such that S_{i_2} = 1.
    Append the values i_2, i_2-1, \ldots, i_1+1 to P.
    It’s easy to see that once again, for any i_1 \lt x \lt i_2, [1, 2, \ldots, x] doesn’t appear as a (rearranged) subarray; since a subarray containing both 1 and x will also contain i_2 which is larger than x.
  • Once again repeat this process with the next 1 after i_2, and so on.
  • Since S_N = 1, this process will end exactly when we’ve placed N; at which point we’ve built the entire permutation we need!

Note that this constructive proof also shows that as long as S_1 = S_N = 1, a solution always exists.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    
    if s[0] == '0' or s[-1] == '0':
        print(-1)
        continue
    
    ans = [1]
    L = 2
    for i in range(1, n):
        if s[i] == '0': continue
        # L...i+1 in reverse
        for x in reversed(range(L, i+2)):
            ans.append(x)
        L = i+2
    print(*ans)
1 Like
2

Great detailed explanation thank you

1 Like