Editorial for Back To School '19: Unstable Books
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Please note that since
refused to write an editorial, decided to write his own version. His solution is slightly different than intended.Subtask 1
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:
Subtask 2
This is a reminder that
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 shelf.
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 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
doesn't know how and since refused to write the editorial, this is what you get.Time Complexity:
Subtask 3
For the third subtask, we can compute the array in the same way as subtask 2, however we have to handle the adjustment at the end differently. Consider . If this value is , then belongs to the same subsection, and is greater than the actual answer. Otherwise, the subsection formed by that change in direction has already been counted during the dynamic programming. Once again, the answer is the minimum of for all .
Time Complexity:
Comments