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!