## Editorial for Back To School '19: Unstable Books

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

Please note that since Ninjaclasher refused to write an editorial, wleung_bvg decided to write his own version. His solution is slightly different than intended.

For the first subtask, we can see that for each pair of indices and , there are only two options: swapped, and not swapped. Since there are of these pairs (where ), then there are possible permutations of the books. For each permutation, we can count the minimum number of increasing and decreasing subsections using a greedy algorithm to extend the current subsection as long as possible in time. We keep track of the minimum and print that as the answer.

Time Complexity:

This is a reminder that wleung_bvg still does not know how to dp, so please bear with him again.

For the second subtask, we can use dynamic programming to efficiently compute the answer. We will store the optimal answer for the subarrays and for all integers . A key observation is that to compute the optimal answer, we only need to worry about the previous/next elements in the array, in addition to the current element.

Let us define a function . If is either the maximum or minimum of , then . Otherwise, . If are consecutive heights on the shelf, we can see that this corresponds to a change from either increasing to decreasing, or decreasing to increasing, which increases the instability of the shelve.

For simplicity, we can define another function . If , then , otherwise, .

Let and store the minimum instability for the subarray and where index is swapped with iff , is swapped with iff , and index is swapped with iff .

We can see the optimal answer for each state relies on the optimal answer ending at index with the same elements swapped as the current state. The optimal answer for the current state is at least .

We know that if there if there is a change in direction for , then the optimal answer increases by one. This also applies for . Thus, we have the following:

When is even, the optimal answer should be the minimum of for all , however the answer could possibly be off by depending on the number of direction changes not counted between indices and . Consider and . If these two values are both , then it means that the subarray belongs to the same subsection, and that is greater than the actual answer. If both values are , then forms an additional subsection that has not been counted and that is less than the actual answer. In all other cases, stores the correct answer for those specific values of . We can keep track of the minimum for all and print the answer.

It is very likely that one of the dimensions in the dynamic programming can be eliminated. Unfortunately wleung_bvg doesn't know how and since Ninjaclasher refused to write the editorial, this is what you get.

Time Complexity: