Author: Lucian Bicsi
Solved by:
First to solve: ETF/MATF Beograd - Seals
The key approach to this problem is to try to progressively sort the colors one by one, in at most operations per color. However, not all colors can immediately be solved in operations. Nonetheless, we claim that there is always a color that can be sorted in operations, also leaving us in a state with exactly one empty rod.
Let's define as the sum of the depths of the three disks of color (we consider the top row to be of depth , the middle row to be of depth , and the bottom row to be of depth ). The sum of weights for all colors is exactly . This means that there must be some color for which \text{weight}(c) \leq 6. This is the color that we will choose.
There are, in fact, possible cases for a configuration with weight at most (we omit the situation where multiple disks are on the same rod, but they also have to be treated carefully). These cases are [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [2, 2, 2].
Then, after doing some case analysis on paper, one might notice that all cases can be solved in at most operations (including restoring to a situation where there is exactly one empty rod), except for the case [2, 2, 2]. However, it is not hard to see that, if we ignore all colors for which the depths of the disks correspond to the case [2, 2, 2], the sum of the remaining weights is still 6 n' (where n' is the number of the yet unexcluded colors), therefore we can always find one of the other favorable cases to solve at any point in time.
The rest of the solution is careful implementation of all cases. For example, the case [1, 2, 2] can be solved in at most steps as follows:
Move disk from rod to empty rod;
Move disk from rod to rod ;
Move disk from rod to empty rod;
Move disk from rod to rod ;
Move disk from rod to empty rod;
Move disk from rod to rod ;
At the end of the six moves, the old empty rod is now sorted, and the new empty rod is rod . The solution for the other cases are left as an exercise for the reader.
Note that at the end, all colors would be sorted and one empty rod will exist; however, if the empty rod is not n+1, we also have to move all disks from rod n+1 to the empty rod. The total number of operations cannot ever exceed 6n-3.
The complexity of such solution is O(n^2). It can be optimized to , but the optimization was not required for these constraints.