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

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: r3mark

For the first subtask, on the $i^\text{th}$ ~i^\text{th}~ restacking, we move paper $i$ ~i~ to the top and everything else to the bottom. Then after $N$ ~N~ restackings, we obtain a reverse-sorted array. A final restacking is needed to reverse it.

Number of Restackings: $N+1$ ~N+1~

For the second subtask, on the $i^\text{th}$ ~i^\text{th}~ restacking, we move paper $N-i+1$ ~N-i+1~ to the top and everything else to the bottom. Then after $N$ ~N~ restackings, we obtain a sorted array.

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

Number of Restackings: $N$ ~N~

For the third subtask, assign an interval to each page. Initially, all the intervals are $(1, N)$ ~(1, N)~. Then during a restacking, for the current page, check the middle of the interval ( $\text{mid}=\left\lfloor \frac{\text{left}+\text{right}}{2} \right\rfloor$ ). If the current page's value is less than the middle, we move it to the top and its interval becomes $(\text{left}, \text{mid})$ ~(\text{left}, \text{mid})~. Otherwise, we move it to the bottom and its interval becomes $(\text{mid}+1, \text{right})$ ~(\text{mid}+1, \text{right})~. We stop once all the intervals become exactly the value of the page. So this takes $\lceil \log N \rceil$ ~\lceil \log N \rceil~ 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 $i$ ~i~, and then follow the algorithm with these new numbers, we can force the array to become sorted.

Number of Restackings: $\lceil \log N \rceil$ ~\lceil \log N \rceil~

Comments

2

simp1eton commented on Nov. 15, 2018, 11:58 p.m. ← edited →

Instead of remapping, we can also explicitly sort the stack in $\lceil \log N \rceil$ ~\lceil \log N \rceil~ time.

If the largest number has $k$ ~k~ bits, we treat all numbers as $k$ ~k~ 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 $k^{th}$ ~k^{th}~ bit with the $(k+1)^{th}$ ~(k+1)^{th}~ bit, treat the $(k+1)^{th}$ ~(k+1)^{th}~ bit as 1.

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

Thus we use $k = \lceil \log N \rceil$ ~k = \lceil \log N \rceil~ restackings.