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!