## Editorial for DMOPC '18 Contest 3 P5 - Bob and Physics Class

**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.**

Authors:

For the first subtask, on the restacking, we move paper to the top and everything else to the bottom. Then after restackings, we obtain a reverse-sorted array. A final restacking is needed to reverse it.

**Number of Restackings:**

For the second subtask, on the restacking, we move paper to the top and everything else to the bottom. Then after restackings, we obtain a sorted array.

There are many other ways to obtain a sorted array in restackings.

**Number of Restackings:**

For the third subtask, assign an interval to each page. Initially, all the intervals are . Then during a restacking, for the current page, check the middle of the interval (). If the current page's value is less than the middle, we move it to the top and its interval becomes . Otherwise, we move it to the bottom and its interval becomes . We stop once all the intervals become exactly the value of the page. So this takes restackings. However, it does not sort the pages.

Observe that this algorithm will always give the same end result (assuming the number of pages is the same). So if we assign a number for each , and then follow the algorithm with these new numbers, we can force the array to become sorted.

**Number of Restackings:**

## Comments

Instead of remapping, we can also explicitly sort the stack in time.

If the largest number has bits, we treat all numbers as bit strings. Starting from the least significant bit, we compare the two adjacent bits of each string. If they are different, move it to the top of the stack. If they are the same, move it to the bottom of the stack. When comparing the bit with the bit, treat the bit as 1.

The idea is that we keep the invariant that there exists a number such that all numbers are in descending order and all numbers are in ascending order. If the stack has this property, we can sort the stack in a single turn.

Thus we use restackings.