WTCH - Editorial



Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi




You’re given a string consisting of characters ‘0’ and ‘1’. Initially, no two '1’s are adjacent. You should output the maximum number of '0’s that can be flipped to ‘1’ without having any two '1’s adjacent.


For each maximal substring consisting of only '0’s, find out its contribution to the answer.


First, let’s answer the first subtask.
If we have x '0’s in a row, the maximum number of them that can be flipped to ‘1’ is \lceil \frac{x}{2} \rceil. The reason is that if you group the first 2 positions together, the second 2 positions together and so on, you can flip at most one position in each group to ‘1’. This bound can be achieved by flipping the odd positions (1, 3, 5, …).

Now let’s get back to the original problem. Consider the maximal substrings of the given string that consist of only '0’s. For example, if the input string is “0101000”, these maximal substrings are “0”, “0” and “000”. It’s easy to see that we can solve the problem for these substrings independently and sum the results.
Let’s solve the problem for one of these substrings, t. If there is a ‘1’ immediately to the left of t, the first character of t is useless and cannot be flipped. Similarly, if there is a ‘1’ to the right of t, the last character of t is useless and can’t be flipped. Hence, we can reduce t's length appropriately depending on what’s to its left and right. What remains is a string consisting of only '0’s each of whose characters can be flipped. This is the same as the first subtask, and we already know how to solve it.
So we solve the problem for each of the maximal substrings and sum the results to find the answer to the original problem.

This solution runs in O(N). Refer to the setter’s solution to see the implementation.


Author’s solution can be found here.
Tester’s solution can be found here.

Video Editorial :

Sir, according to what I did for case 2 where string is a combination of 0s and 1s : first counting number of '1’s in the string then
we can also consider suppose taking all n digits to be 0 , then applying case 1 formula i.e. n/2 or n/2 +1, and after that
subtracting the count from n/2 or n/2 + 1
that difference will be the output
Is this logic wrong?? Plz reply

@ani95 That approach would not be correct. Consider the input “010010”, for which there are two 1’s and n = 6. Then n/2 = 3, and your approach would yield 1. However, the correct answer is 0, as no zeros can be flipped given this configuration.