A regular week

The Aug 19 - Aug 25 week had TopCoder SRM 765 (problems, results, top 5 on the left, my screencast). I've spent quite a lot of time on each of the first two problems, but managed to recoup those losses by challenging a lot of solutions to the easy problem, which required a lot of accuracy when coding and ended up having just 20% success rate.

Codeforces hosted a round called "Manthan, Codefest 19" (problems, results, top 5 on the left, analysis). Nobody except tourist could get the hardest problem accepted, and therefore the challenge fight was only for the second place. Congratulations to Gennady on the win!

In the previous summary, I have mentioned an AtCoder problem: you are given a n times m grid (n, m <= 100), containing each number between 1 and nm once. Your goal is to sort the grid in row-major order in three steps. In the first step, you can rearrange the numbers within each row arbitrarily. In the second step, you can rearrange the numbers within each column arbitrarily. In the third step, you can rearrange the numbers within each row again.

Before the third step, we need each row to contain the numbers it should have in the end, in any order. Let's color numbers in n colors, such that all numbers that end up in the same row have the same color. Then before the first step we must have all numbers of one color in the corresponding row.

This means that before the second step, each column must have exactly one number of each color. In the first step, we are rearranging the rows arbitrarily, so let's assume that we're filling columns one by one, so every time we need to take one from the remaining colors in each row in such a way that we get one of each color.

This subproblem is a matching one: we can make a bipartite graph where the left part contains rows, the right part contains colors, and there's an edge for each number in the initial grid. Since this graph is regular, it has a matching, and moreover it keeps being regular after we remove all edges of a matching, so we can just repeat this process m times to split the entire graph into n matchings, which gives us the necessary rearrangement of numbers for the first step.

Thanks for reading, and check back for more!