ALLASIDE - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You have a binary string S.
It can be modified by the following operation:

  • Choose an index i, and let [L, R] be the maximal segment of equal elements containing index i.
  • Flip every character at indices [L, i-1] \cup [i+1, R].

Find the lexicographically smallest final string after using this operation finitely many times.

EXPLANATION:

We’ll call a substring S[L, R] of the string S a maximal block if:

  • S_L = S_{L+1} = \ldots = S_R,
  • L = 1 or S_L \ne S_{L-1}, and
  • R = N or S_R \ne S_{R+1}

Note that each index of the string belongs to a unique maximal block.
Each operation then consists of choosing an index and flipping all characters other than it in the maximal block containing it.

In particular, observe that after an operation, the number of maximal blocks of the string can never decrease!
This is because, if we operate on index i and [L, R] is the maximal block containing it,

  • We lose the block [L, R].
  • We gain the three blocks [L, i-1], [i, i], [i+1, R].
    (The left/right ones here might be empty, we can treat them as existing and then always merging with the block to the left/right respectively.)
  • If L \gt 1, then [L, i-1] will merge with the block to its left.
  • If R \lt N, then [i+1, R] will merge with the block to its right.

So, all in all we come out equal in block count at best; and if some merges don’t happen then the number of maximal blocks can even increase!

Let B denote the number of maximal blocks in the input string S.

It can be verified that with B blocks, the lexicographically smallest possible string that can be formed is

00\ldots 00101010\ldots

Specifically, N - (B-1) zeros followed by an alternating string of length B-1 starting with a 1.
Let’s call this string \text{best}(B).

Note that \text{best}(B) is lexicographically smaller than \text{best}(B+1) for any B, since \text{best}(B+1) has one less 0 in its prefix of 0’s.

Since we saw that our operations cannot reduce B, clearly the best possible final string we can hope for is \text{best}(B).

It turns out that quite often, we can indeed reach \text{best}(B)!
In particular, as long as S_1 = 0, i.e. S starts with a 0, we can always convert S to \text{best}(B).
The construction is simple: just perform operations with i = N, N-1, N-2, \ldots in order; for the last B-1 indices.
This will repeatedly shrink maximal blocks to have length 1 towards the back of the string without increasing the number of blocks; so that we eventually end up with \text{best}(B).

Unfortunately, if S_1 = 1, then this doesn’t quite work: we want to start with a 0 but we have a 1 there, so we need to flip it.
However, flipping the first index will always strictly increase the number of maximal blocks; because we must do so by choosing some i \gt 1 and then the segment [1, i-1] does not have anything to its left to merge with; thus increasing the block count.

However, if we don’t increase the block count, then the string will surely start with a 1.
This is strictly worse than starting with a 0, so it’s optimal to increase the block count (by 1).

Putting everything together, we have the following.

  • Let B denote the number of maximal blocks in S.
  • If S_1 = 0, then the answer is \text{best}(B).
  • Otherwise, the answer is \text{best}(B+1).
    • There’s one exception: if S_1 = 1 and B = N then \text{best}(B+1) is not a valid string of length N.
      In this case, the string looks like 101010\ldots and cannot be changed; so the answer is S itself.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
def best(b, n):
    alt = '10'*n
    return '0'*(n-b+1) + alt[:b-1]

for _ in range(int(input())):
    n = int(input())
    s = input()
    b = 1
    for i in range(1, n):
        if s[i] != s[i-1]: b += 1
    
    if s[0] == '0': print(best(b, n))
    else:
        if b == n: print(s)
        else: print(best(b+1, n))
1 Like