KFLIP - Editorial

PROBLEM LINK:

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

Author: Daanish Mahajan
Preparer: Utkarsh Gupta
Testers: Jeevan Jyot Singh, Hriday
Editorialist: Nishank Suresh

DIFFICULTY:

2432

PREREQUISITES:

None

PROBLEM:

Given a binary string of length N and an integer K, in one move you can flip any subsequence of the string of length K. How many distinct strings can you obtain using zero or more moves?

EXPLANATION:

The actual binary string S doesn’t matter at all — only the values of N and K matter, since each string you can obtain is uniquely determined by the set of positions flipped.

So the question boils down to the following: given N and K, how many subsets of positions can we flip?

The answer has three cases:

  • If N = K, obviously either we flip nothing or we flip everything, so the answer is 2
  • Otherwise, K \lt N, and:
    • If K is odd, we can flip any subset of positions, so the answer is 2^N
    • If K is even, we can flip any subset of positions of even size, so the answer is the number of subsets of even size, i.e, 2^{N-1}
Proof

The N = K case is trivial, so let’s look at K \lt N.

First, let K be odd. It’s enough to show that any single position can be flipped without changing the state of any of the other positions, since this allows us to flip any subset by repeatedly applying it. So, let’s show that position 1 can be flipped.

Construction

Consider the positions 1, 2, \ldots, K+1.
There are \binom{K}{K-1} = K ways to choose a subset of size K-1 from positions 2, \ldots, K+1. To each of these K subsets, insert 1 to obtain a size-K subset.

Now perform K flipping moves, one on each of the subsets we have. Note that:

  • Position 1 is flipped K times (an odd number), and so is flipped at the end
  • Positions 2, 3, \ldots, K+1 are flipped K-1 times (an even number) each, and so aren’t flipped at the end
  • Positions \gt K+1 are untouched.

So, only position 1 is flipped, as required.

Next, let K be even. Note that in this case, after each operation the number of positions flipped will be even. It thus remains to show that any even-sized subset is attainable.

Construction

Similar to the odd case, we will show that positions 1 and 2 can be flipped without affecting the rest of the string. Chaining together operations of this type allows any even-sized subset to be formed.

The construction is also essentially the same: there are K-1 ways to choose a subset of size K-2 from \{3, 4, \ldots, K+1\}. To each of these, insert 1 and 2 to obtain a size K subset, and operate on each one.

  • Positions 1 and 2 flip K-1 times, which is odd.
  • Positions 3 to K+1 flip K-2 times each, which is even

So, at the end only 1 and 2 are flipped and we are done.

Make sure to compute the above values modulo 10^9 + 7.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python)
mod = int(10**9 + 7)
for _ in range(int(input())):
	n, k = map(int, input().split())
	s = input()
	if k == n:
		print(2)
	elif k%2 == 1:
		print(pow(2, n, mod))
	else:
		print(pow(2, n-1, mod))
3 Likes

You didn’t show that in 2nd case it’s not possible to have more than 2n-1 strings.
It’s because when K is even, the parity of 1’s and 0’s is invariant. So you cannot have more than 2n-1 strings.

I in fact did prove that the number of strings is exactly 2^{N-1}:

  • The number of flipped positions after any number of moves is even
  • I proved any such configuration is achievable

The number of ways of choosing an even number of positions to flip is exactly 2^{N-1}. This already shows equality, there is no need to further show an upper bound (in fact, the property about parity you stated is essentially a rephrasing of the fact that an even number of positions must be flipped after each move).

@iceknight1093 Can you please explain how to get intuition that there we have to look on count of 1s in string?

The count of ones in the string doesn’t matter, in fact the very first line of the editorial is

The actual binary string S doesn’t matter at all

Like in approah we considered count of 1s to reach ans.
For example: if s = “1010” and k = 1/3 then
it can create strings with 0 “1”, 1 “1”, 2 “1”, 3 “1”, 4 “1”. So , we did 4c0 + 4c1 … 4c4 = 2^4
if s = “1010” and k = 2/4 then
it can create strings with 0 “1”, 2 “1”, 4 “1”. So , we did 4c0 + 4c2 + 4c4 = 2^4/2
Here, nck means choose “k” positions in string of len “n” where “1” can be present.
So, we reached ans by observing the count of ones in process.
So, How to get intuition that there we have to look on count of 1s in string in process?

Again, you’re fundamentally looking at the wrong thing. I mentioned nothing about the count of ones in the string in the editorial, and the code I linked doesn’t compute it either. The entire input string simply doesn’t matter, the solution depends purely on the values of N and K.

When you have operations like this, you should try out a few examples and see what you can get:

  • Say k is odd.
    • In the first move, you flip an odd number of positions.
    • In the second move, you once again flip an odd number of positions. Now, you can notice that it’s always an even number of positions flipped compared to the initial string.
    • After the third move, you have an odd number of positions flipped compared to the initial string.
    • After the fourth move, you have an even number of positions flipped compared to the initial string.
    • And so on
  • You can reach any binary string by flipping some number of positions from the initial string, so it makes sense to ask whether you can reach them all. The editorial proves that this is the case.
  • Now look at when k is even.
    • After the first move, an even number of positions are flipped.
    • After the second move, still an even number of positions are flipped
    • After the third move, still an even number of positions are flipped
    • And so on
  • You see that no matter what you do, you can only flip an even number of positions compared to the original string. Once again, it makes sense to ask whether you can flip any even-sized set of positions, and once again, the editorial proves that this is possible.
1 Like

Ohh Okay, Thank you!