I would like to discuss C. Triple Flips from today's competition.
This problem was way too difficult for me during the competition because of its constructive nature. However, when upsolving I came up with the following solution:
1) If we have enough space from one side, we could flip '1' to '0' without influencing other elements. For instance, flipping 8th '1' to '0' would be three operations (2, 5, 8), (2, 3, 4), (3, 4, 5).
2) When we may not have enough space (it could happen with n = 7 for a middle element, for example), n is small (let's say n <= 15). In this case, we could apply a simple BFS for bitmasks.
3) When n > 15, I consider the first and the second '1'. I try to erase them both at once by finding the third element (which is to the right of the second '1', and it does not matter whether it is '0' or '1'), and flipping them all. Of course, this element might not exist (the third element of the arithmetic progression might be out of bounds of the string :) ). In this case, I eliminate the first '1' according to (1). When I apply this step, I repeat the process until one elements remains. Then I just eliminate it.
Do you think that this is correct? Spoiler alert: no, this is not. Although at first I thought that the idea in (3) manages to capture all '1's efficiently, it is quite clear that this could lead to n / 2 operations for lengthy strings. However, before realizing this, I managed to submit this idea and get AC. Look at my accepted incorrect submission here.
The test is: 11010..010101 (string length of 100000). My solution needs only 50005 operations to solve this! :))
The moral of the story: guys, please prepare strong test cases! I know how hard it is to prepare problems, but I think that it is worth doing this extra step.
Thanks!
UPD: For those who are looking for a working solution using a similar idea, I fixed it by this submission. It is almost the same, but avoids the issue of the substring "110", maintaining not only the previous '1' (for the second '1'), but a couple of them. This makes the inefficiency caused by "110" avoidable. Take a look at the solution for details. Let me know if you could hack this one as well! :)
Another solution overcoming the issue is proposed by tfg in comments.
Also komendart has added this test and some others (look down for his comment). So your solutions are currently checked against those tests when submitting!
Not about the test cases but here's a way to fix that solution:
Try to erase the 3 first positions and ignore them. This reduces N to N — 3. But there's a problem when 110xxxxxx appears. To solve that, do the same thing on the back and if there's 110xxx011 you can erase them in 2 moves. This reduces N by 3 every time.
I can assure you that authors always strive for test cases as strong as possible. Sometimes, there is a suboptimal solution that manages to pass all test cases nevertheless. This is especially true in constructive tasks like this one, because there is an abundance of different approaches. It is simply not possible for the problem author to think about all of them.
During a contest, hacks might alleviate the issue to certain extent. I have thought of this approach and understood that it does not work. If you were to submit this and you were in my room (and I had time for hacking), there would be a good chance you would be hacked.
If anybody cares I added tests suggested here and in comments to round's announcement (maybe with little changes) and several more small tests.
Accepted wrong solutions won't be rejudged.
Sorry for incovenience :):
Great, thanks!