Editorial for DMOPC '21 Contest 1 P2 - Folding Clothes


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

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 \mathcal{O}(N^2). Feel free to add your own solutions in the comments.

6N 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 i clothes in the first stack, and we want to get the (i+1)-th piece of clothing where it should be. First, we can use 3 moves to move it to the top of the first stack, regardless of where it is currently:

  1. Move all clothes above the (i+1)-th to the second stack.
  2. Move the (i+1)-th piece of clothing to the second stack.
  3. Move everything in the second stack back to the first.

Then, we can use another 3 moves to get it on top of the i-th piece of clothing:

  1. Move all clothes above the i-th to the second stack.
  2. Move the (i+1)-th piece of clothing, which is now at the top of the second stack, back to the first.
  3. Move everything in the second stack back to the first.

It is easy to see that we use at most 6 moves per item of clothing, so there are a total of 6N moves. This scores us 20 points.

3N moves

Let's optimize the strategy above. Again, we sort the clothes in decreasing order of width. If we have already sorted the bottom i clothes in the first stack, then to get the (i+1)-th piece of clothing where it should be:

  1. Move all clothes above the i-th to the second stack.
  2. Move all clothes above and including the (i+1)-th back to the first stack.
  3. Move everything in the second stack back to the first.

Now we use at most 3 moves per item of clothing, so there are a total of 3N moves. This scores us 80 points.

2N moves: First Strategy

We can further improve upon the 3N solution, by noting that it is not necessary to return all the clothes back to the first stack every single time. Thus, we may save the last move from every iteration and proceed as follows:

  1. Move all clothes above the i-th to the second stack.
  2. Move all clothes above and including the (i+1)-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 2 moves per item of clothing, there are a total of 2N moves maximum. This is enough for 100 points.

2N 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 N-1 clothes, denote the piece of clothing currently at the top of the first stack x:

  1. Move all clothes with smaller width than x in the second stack back on top of x in the first stack. We know this will be a prefix of the second stack since we maintain its sorted property.
  2. Move all clothes above and including x back to the second stack.

In this manner, we have inserted x to the position where it should be in the second stack. Finally, we move the fully sorted second stack back to the first. This algorithm takes 2(N - 1) + 2 = 2N moves at maximum, so it is also sufficient for 100 points.


Comments

There are no comments at the moment.