# FLIP2K - Editorial

**URL:** <https://discuss.codechef.com/t/flip2k-editorial/125588>\
**Category:** editorial\
**Tags:** editorial, simple, start247\
**Created:** [July 15, 2026, 4:30pm UTC](https://discuss.codechef.com/t/flip2k-editorial/125588 "2026-07-15T16:30:12Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![iceknight1093](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@iceknight1093](https://discuss.codechef.com/u/iceknight1093)\
**Post date:** [July 15, 2026, 4:30pm UTC](https://discuss.codechef.com/t/flip2k-editorial/125588/1 "2026-07-15T16:30:12Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/FLIP2K)  
[Contest: Division 1](https://www.codechef.com/START247A/problems/FLIP2K)  
[Contest: Division 2](https://www.codechef.com/START247B/problems/FLIP2K)  
[Contest: Division 3](https://www.codechef.com/START247C/problems/FLIP2K)  
[Contest: Division 4](https://www.codechef.com/START247D/problems/FLIP2K)

_ **Author:** _ [iceknight1093](https://www.codechef.com/users/iceknight1093)  
_ **Tester:** _ [sushil2006](https://www.codechef.com/users/sushil2006)  
_ **Editorialist:** _ [iceknight1093](https://www.codechef.com/users/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)**
>
> ```python
> 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)
> 
> ```