Author: Hasan Jaddouh
Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak
For a binary string A, let’s define a block as a substring of A containing either only 1's or only 0's, so 111 and 0 are blocks, while 10 and 0010 are not. Moreover, let a major block be a block of A, such that no block in A is longer that it and L be the length of a major block of A. Notice that there can be many major blocks, but all of them have the same length.
Then the problem can be reformulated as follow: for a given binary string A of length N and integer K, we have to return the minimum L (the length of a major block) that we can get by performing at most K bit flips on A.
For example, if A = 11100 and K=1, the best we can do is to either flip the first or the second bit to get for respectively 01100 and 10100. In both these strings, L is 2, which is the best we can get in this case.
First, check if getting L=1 is possible. If yes the problem is solved, otherwise, perform a binary search on the result checking if getting L=M is possible in linear time.
First of all, let’s take a closer look at the constraints. It is said that K \leq 10^6, but since also N \leq 10^6 and there is no point of flipping a single bit more than once, we can rewrite the constraint as K \leq N.
In the first subtask N \leq 10, so one can generate all possible strings we can get by performing at most K flips on A, and compute the smallest L among them. This is possible because there are at most 2^N such strings and computing L for a single string takes O(N) time. Thus the overall time complexity of solving all test cases will be O(T \cdot 2^N \cdot N), which is completely fine for these constraints and T \leq 11000.
In the second subtask we have N \le 10^6, so the problem has to be solved in a clever way. The crucial observation is that for any L and any block of A with length M, \lceil M / (L+1) \rceil flips are necessary to convert that block into a substring without blocks of length greater than L, and we can perform exactly that many flips to do that.
For example, if we have a block of length 5, 00000, and L=2, we flip its bits with indices L+1, 2 \cdot (L+1), 3 \cdot (L+1) \ldots, so in this particular case, we flip only its third bit to get 00100. Similarly, if we have a block of length 6, 000000, and L=2, we flip its third and sixth bits to get 001001.
Thus it looks like we can perform a binary search for the answer and for a fixed M, check if we can transform all the blocks in A into block of length at most X using at most K flips by just iterating over all blocks in A and computing the sum of needed swaps for all of these blocks. Notice that binary search is correct here, because if it is not possible to use at most K swaps to get A with L=X, then it is also not possible to use at most K swaps to get A with L \lt X. This will result in O(N \cdot \log N) time complexity for a single test case, but since the sum of N across all test cases is at most 10^6, this will run fast enough. However, we are not finished yet, because there is a tricky case to handle.
Notice that when we divide A into blocks, the blocks alternate in such a way that after a block consisting of 0's there is a block consisting of 1's, then one consisting of 0's again and so on. The observation we made says that for a block of length M, \lceil M / (L+1) \rceil flips are necessary and sufficient to convert this block into blocks of sizes at most L. It is true for an isolated block, however, since in some cases we are forced to flip the first or the last bit of such block, that may ruin our solution because that bit can create another block with adjacent blocks.
Let’s take a closer look where this situation can happen, so in what cases we are really forced to flip either the first of the last bit of a block? As mentioned above, for a block of length M and a fixed L, we can flip bits with indices L+1, 2 \cdot (L+1), 3 \cdot (L+1) \ldots. It follows that we are flipping its last bit if M \mod (L+1) = 0. However, if this happens and L \gt 1, we can always flip bits with indices L, 2 \cdot L, 3 \cdot L, \ldots and we avoid flipping the first and the last bits, which caused the problem. But what happens when L = 1? Well, then we cannot use that trick, however, this case is easy to handle: at the beginning, we can just check if A can be transformed using at most K flips to get L=1. Notice that there are just 2 possible strings of given length with L=1, either a sequence of alternating 0's and 1's starting with 0 or the same but starting with 1. If this is the case we are done. Otherwise, we use binary search described above searching for the answer in a range [2, N]. For implementation details, please refer to multiple solutions linked below.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.
Editorialist’s solution can be found here.