Editorial for DMOPC '21 Contest 1 P2 - Folding Clothes
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
There are a plethora of solutions to this problem, of which we present a few notable ideas. All the presented solutions can be comfortably implemented in
moves
The most primitive solution. Similar to a selection sort algorithm, we will sort the clothes in decreasing order of width (i.e. bottom to top). Let's say we have already sorted the bottom
- Move all clothes above the
-th to the second stack. - Move the
-th piece of clothing to the second stack. - Move everything in the second stack back to the first.
Then, we can use another
- Move all clothes above the
-th to the second stack. - Move the
-th piece of clothing, which is now at the top of the second stack, back to the first. - Move everything in the second stack back to the first.
It is easy to see that we use at most
moves
Let's optimize the strategy above. Again, we sort the clothes in decreasing order of width. If we have already sorted the bottom
- Move all clothes above the
-th to the second stack. - Move all clothes above and including the
-th back to the first stack. - Move everything in the second stack back to the first.
Now we use at most
moves: First Strategy
We can further improve upon the
- Move all clothes above the
-th to the second stack. - Move all clothes above and including the
-th back to the first stack.
This leaves some clothes in the second stack temporarily, but everything should be back in place (due to the nature of the algorithm) in the end.
Since we use at most
moves: Second Strategy
We may apply the logic of insertion sort to this problem. We maintain a sorted stack of clothes in the second stack, and each time insert the top piece of clothing in the first stack to where it should be in the second. First, let's move the top piece of clothing in the first stack to the second. Now, for the next
- Move all clothes with smaller width than
in the second stack back on top of in the first stack. We know this will be a prefix of the second stack since we maintain its sorted property. - Move all clothes above and including
back to the second stack.
In this manner, we have inserted
Comments