FLIP2K - 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 A. You can repeatedly perform the following operation:

  • Choose 2K positions, of which K must contain 0 and K must contain 1.
  • Then flip the characters at all these positions between 0 and 1.

Find the lexicographically minimum string that it’s possible to reach.

EXPLANATION:

Let c_0 and c_1 denote the number of zeros and ones in A, respectively.

The operation requires us to choose K each of zeros and ones.
So, if c_0 \lt K or c_1 \lt K, it’s impossible for us to perform an operation at all.
Thus, in this case the answer is simply A.

From now on, we assume c_0 \ge K and c_1 \ge K.

Now, consider the case of 2K = N.
Here, in any move we’re forced to choose all the characters.
Since every character is flipped, the second move we perform just gives us back the original string.
Thus, only two strings are reachable: A itself, and then the string formed by flipping every character of A.
The answer is the minimum of these two strings (whichever one of them starts with a 0.)

Finally, we’re left with the case of 2K \lt N, while still having (at least) K each of zeros and ones.

Observe that since each move flips K zeros and K ones, the number of zeros and ones in the string always remains the same.
Thus, the absolute best we can hope for is to have c_0 zeros as a prefix and then c_1 ones after that, the string

\underbrace{00\ldots 00}_{c_0}\ \ \underbrace{11\ldots 11}_{c_1}

As it turns out, this string can always be reached!

In fact, something even stronger can be proved: it’s possible to reach any binary string with c_0 zeros and c_1 ones.

Proof

The string contains at least one occurrence each of 0 and 1.
We’ll prove that it’s possible to swap and pair of a 0 and a 1 using some sequence of moves (while leaving all the other elements unchanged.)
This will allow us to chain together an arbitrary sequence of swaps, thus proving that any rearrangement of the initial string is reachable.

So, let i and j be two indices such that A_i = 0 and A_j = 1.

We assumed that c_0 \ge K and c_1 \ge K, which means the string contains at least K-1 extra occurrences each of 0 and 1.
Pick any K-1 other occurrences of each - say the zeros are at x_1, \ldots, x_{K-1} and the ones are at y_1, \ldots, y_{K-1}.

Finally, we’re in the case of 2K \lt N, and the above indices have accounted for 2K elements in total.
Thus, there must be at least one unpicked element.
Choose any one such element - say at index e.

Without loss of generality, we assume A_e = 0. The below construction is easy to adapt for the A_e = 1 case as well.

Now consider the following two moves:

  • First, pick indices x_1, \ldots, x_{K-1}, y_1, \ldots, y_{K-1}, as well as e and j.
    • Note that after this move, we’ll have A_i = A_j = 0 while A_e = 1.
  • Then, pick indices x_1, \ldots, x_{K-1}, y_1, \ldots, y_{K-1}, as well as e and i.
    • After this move, all of x_1, \ldots, x_{K-1}, y_1, \ldots, y_{K-1} were flipped twice so they’re back to their original values.
    • e was also flipped twice, so it’s back to its original value.
    • i and j were flipped once each, so they’ve both changed value - which is equivalent to swapping them, so we’re done!

To summarize,

  • If c_0 \lt K or c_1 \lt K, the answer is A itself.
  • If 2K = N, the answer is the minimum of A and \bar{A}, where \bar{A} denotes the string obtained by flipping every character of A.
  • If 2K \lt N, the answer is c_0 zeros followed by c_1 ones; equivalently the string obtained by sorting A.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = input()
    
    zero, one = a.count('0'), a.count('1')
    if min(zero, one) < k:
        print(a)
        continue
    if n == 2*k:
        flipped = ''.join('1' if x == '0' else '0' for x in a)
        print(min(a, flipped))
        continue

    print('0'*zero + '1'*one)
1 Like
FLIP2KHD - Editorial