Problem of May '21

For this month, our algorithm problem is the problem TransposeColors which was used as the hard problem for division 2 and also the easy problem for division 1 in SRM 806.

The problem is really easy to explain: we have a board with colorful tokens. Each row of tokens has a different color:

We want to have a different color in each column: the first column should have the red tokens, the second one should have the green ones, and so on.

In order to get that new configuration, we need to move the tokens around. We have to move one token at a time. And to make matters slightly more complicated, we can only place one token outside of the board. What is the minimum number of moves needed to rearrange the board, and how should we do it?

One of the nice things about this problem is how approachable it is. When solving it by hand, it’s clear how to get started: take one of the tokens that isn’t in its correct location and put it outside of the board to have some space. For example, suppose we remove the yellow in the bottom left corner. Now we have an empty space on the board. The empty space is in the column that is supposed to be red, so let’s move one of the red tokens there. And once we do so, we have again created an empty space which should be filled by a token of the correct color. Here’s one possible situation after the first four moves (with a yellow, red, yellow, and then a blue token):

We are getting closer to the goal: there are now two red tokens in the column that should end all red, and we also have two blue and two yellow tokens in their correct columns.

Once we try to finish the solution, we will encounter the main obstacle. If we just move the tokens around without having any bigger plan, it is really easy to get into a situation like the one shown in the figure below:

In the figure, we have already placed all the yellow tokens correctly but some of the other tokens are still in place. We now have to return the yellow token into the box and then waste a move by taking another of the incorrectly placed tokens out of the box. We probably just failed to use the smallest possible number of moves.

After playing around with the problem for a while, you may get a feeling that this somehow resembles the old pen and paper puzzles in which you are shown some figure and the goal is to draw the entire figure without lifting the pen and without going along the same line twice. In those puzzles, if you were careless, you could end up stuck in a location from which it is no longer possible to continue - while in other regions some parts of the figure were still not done.

If you did make this observation, you were certainly on the right track. Both types of a puzzle are special cases of what is known as Euler tours in graphs. In our problem the graph is directed: each color is one vertex of the graph and each token that needs to be moved is a directed edge from its own color to the color whose place it occupies. For example, if you have a blue token in a yellow column, at some point during the solution you need to move this token into the blue column. And once you do so, you now have an empty space in the yellow column, so you can move a yellow token next, and so on.

There are general algorithms for efficient construction of Euler tours in arbitrary graphs, and you certainly could solve our problem by applying such an algorithm. But a part of the beauty of the problem is in that you don’t have to. Our problem with colorful tokens is only a special case of the general problem, and thanks to this there are also other, simpler ways of solving it. Even if you don’t know the general algorithm, you can still come up with a strategy that is guaranteed to work for our box of tokens.

One good way of coming up with such an algorithm is trying to reduce the problem to a smaller one. For example, if we already know how to rearrange a box of size N and now we are handed a box of size N+1, can we somehow use the previous solution? Sure we can, we just need to make sure to also swap the tokens between the last row and the last column at some point. Once you figure out the details how to do that, you have a full solution ready.