PROBLEM LINK:
Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi
PREREQUISITES:
NONE
PROBLEM:
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.
QUICK EXPLANATION:
For each maximal substring consisting of only '0’s, find out its contribution to the answer.
EXPLANATION:
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 AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.