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

Authors: r3mark

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: