A tourist week

Codeforces hosted its Global Round 1 on Thursday (problems, results, top 5 on the left, analysis). tourist and Um_nik were quite close, both finishing the problem-solving part around 1:20 mark and having some challenge fun thereafter. However, in the end the challenges did not affect the standings, and tourist stayed in first place. Congratulations!

TopCoder SRM 750 followed a day later (problems, results, top 5 on the left, analysis). This time tourist managed to get a commanding lead thanks to solving the 1000-pointer in just 8 minutes, while rng_58 needed 22 minutes and others even more. Well done!

Finally, the Open Cup returned on Sunday with the Grand Prix of Gomel (results, top 5 on the left). This was the first of seven consecutive Open Cup Sundays stretching right up to the ICPC World Finals, and that will provide a good preview as many top-rated ICPC teams are competing. The team from MIT earned the first place with just four minutes remaining, solving two of the hardest problems in the last hour. Amazing performance!

In the previous summary, I have mentioned a TopCoder problem: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.

When we apply this operation to a one and a zero, we're effectively moving the one to the bottom or to the right. By applying this operation several times, the one can move to the bottom and to the right. Moreover, the opposite is true: for any position to the bottom and to the right, we can move the one there in exactly two operations. If the cell in the middle (in the same row or column as both source and target cells) contains a zero, then we just move the one twice in a straightforward manner. If the cell in the middle contains a one, then we can first move that one to the target, and then move the one from the source to the middle cell, restoring the one there.

Finally, the other option of applying the operation to a one and a one, or moving a one onto a one in two operations as described above, results in both ones disappearing. Now we're in a very nice position: we understand the full structure of the problem, and have described everything that is possible in a very concise manner, which allows to see the solution.

More precisely, we need find a "source" one in the initial grid to the left and/or to the top for each one from the final grid, which might also leave some ones in the initial grid unused. Note that if the number of unused ones is odd, there's no solution since all operations preserve parity, and if the number of unused ones is even, we can always get rid of them by moving each to the bottom-right corner in at most two operations.

This observation leaves us with a matching problem which can actually be solved greedily because of the special structure of the graph. If we traverse the ones from the final grid in row-major order, we can simply always pick the rightmost yet-unused one in the initial grid to the left and/or to the top from the current position. This can be proven by a typical exchange argument: let's look at the first time in this row-major traversal when the optimal solution uses a different one to cover the final one in the current position, and uses the greedy choice to cover something else. We can swap the assignments of those two ones and still obtain a valid solution.

Thanks for reading, and check back next week!