The official solution isn't exactly the clearest, so I guess I will present own solution to this problem.
HackMD blog if you prefer it: HackMD: My Solution to IOI17 P6 — Ancient Books
1. Abridged Statement:
Given $$$n$$$ tables, each table has a book. The table is numbered from $$$0$$$ to $$$n-1$$$, and each book has a distinct value from $$$0$$$ to $$$n-1$$$ (let's denote the value of the book on the $$$i^{th}$$$ table as $$$p_i$$$). Initially, lil Johnson starts at table number $$$s$$$ ($$$0 \leq s < n$$$), and is not holding any book.
Lil Johnson has four possible operations:
- If lil Johnson isn't holding a book, and there is a book in the current table, then he can pick it up.
- If lil Johnson is holding a book, and there is no book in the current table, then he can put that book down.
- If lil Johnson is holding a book, and there is also a book in the current table, then he can replace the book.
- Lil Johnson go to the left or to the right i.e. if he is current at position $$$s$$$, then he can either go to table number $$$s-1$$$ or $$$s+1$$$ (obviously, he has to maintain $$$0 \leq s < n$$$ at all time.
The first three operations can be done instantaneously, and the fourth operation will take 1 second. What is the minimum time lil Johnson need to sort the array $$$p$$$ and come back to where he start?
Example: $$$p = [1, 0], s = 0$$$. Here, Lil Johnson picks up the book at table 0, moves to table 1 to replace the book, returns to table 0, and places the book down. The total time is 2 seconds.
Constraint:
- $$$p$$$ is a permutation consisting of distinct integers from $$$0$$$ to $$$n-1$$$.
- $$$n \leq 10^6$$$, $$$0 \leq s < n$$$.
- Time limit: 2 seconds. That means the complexity must be $$$O(n)$$$ or $$$O(n * log(n))$$$, or more if you are an optimization connoisseur.
2. The lower bound of the answer
For the sake of simplicity, we will assume that $$$p_0 \neq 0$$$, and $$$p_{n-1} \neq n-1$$$.
You can imagine that each time we do the operation (4), we are moving at most one book closer to its intended destination. Therefore, the answer would be at least $$$\sum^{n-1}_{i = 0}|p_i - i|$$$.
So can we always achieve this lower bound? No, but it is helpful to know when can this be achieved.
To make my life easier, just interpret "wasted time" as any additional time over the lower bound of the answer. For example, if the answer is 420 while the lower bound is 400, then we call those 20 seconds "wasted time".
One obvious case is that if we draw the edge $$$i \rightarrow p_i$$$, it forms a cycle (or circle for uncultured peasants). That is because you can bring the book at table number $$$s$$$ to table number $$$p_s$$$, then the book at table number $$$p_s$$$ to the table number $$$p_{p_s}$$$, and so on. This gives us an insight: Just sort the cycles, and if you can conveniently switch cycle while you are at it, without incurring any cost, then great, just do it!
Figure 1: How would the cycle looks like.
Another case is that you would come across another cycle when you are sorting the current cycle. Then, you can jump to that cycle, then get back later.
Figure 2: How would the "intersecting" cycles would looks like. As you can see, when lil Johnson was on the $$$[0, 2]$$$ cycle, he can actually hop on the $$$[1, 3]$$$ cycle and sort that cycle, then come back. The operation would look like this.
- Pick up $$$p_0$$$ book.
- Go to table number $$$1$$$ and replace the book. Note that we are switching to cycle $$$[1, 3]$$$ here.
- Go to table number $$$3$$$, replace the book, then go back to table number $$$1$$$ and replace the book. Now we are back to the $$$[0, 2]$$$ cycle.
- Go to table number $$$2$$$, replace the book, then go back to $$$0$$$ and place the book down. The entire thing cost $$$8$$$ seconds.
So, we know that we do not have to waste anytime switching to a different cycle, as long as we encounter a vertex of that cycle while traversing.
Explaination of the algorithm:
- Consider the "0 wasted movement" range, which is initially $$$[s, s]$$$. As we can reach every vertex inside this range, we also have access to every cycle that each vertex in the range belongs to i.e. we can switch to these cycles while we are sorting the current cycle, without incurring additional time.
- Since we can jump to those cycles, we can travel to the minimum and maximum elements of the cycles that these vertices belongs to as well. Just imagine that our range "eat" every cycles of each vertices, which makes it bigger, which allows it to "eat" more. The process ends when it cannot expand any more.
3. Snipe some easy subtask.
From the above code, we can determine how far to the left or right Lil Johnson can move without incurring additional wasted time.
Let's call a range "stretched" if it cannot be expanded further without incurring additional wasted time. For example, $$$p = [2, 3, 4, 1, 0, 5]$$$. The range $$$[1, 1]$$$ is not stretched, because Lil Johnson can expand the range to $$$[1, 3]$$$. Similarly, $$$[1, 3]$$$ is not stretched, because we can expand it to $$$[0, 4]$$$, but $$$[0, 4]$$$ and $$$[5, 5]$$$ are stretched.
When Lil Johnson arrives at the border of the "travellable" range, he can either move left or right and extend the current range at the cost of 2 seconds of wasted walking time (you have to go back too). That is, if the current range is $$$[l, r]$$$, then he can expand it to $$$[l-1, r]$$$ or $$$[l, r+1]$$$.
Let not forget what our goal is. We need to sort the permutation while incurring the fewest cost, which means we need to expand our "travellable" range to $$$[0, n-1]$$$, while ensuring the cost is minimized.
Note that the number of distinct states in our dp table is $$$(s+1) * (n - s)$$$, therefore, this would easily solve the $$$s = 0, n \leq 10^6$$$ and the $$$n \leq 10^3$$$ subtasks. That is an easy 70 points right there.
4. The last subtask (the only hard one)
Let's call the current range (stretched) we are working with $$$[l_0, r_0]$$$. Let us also assume there exists a cycle whose span $$$[x_1, x_2]$$$ strictly contains the current range, i.e., ($$$x_1 < l_0 \leq r_0 < x_2$$$).
Claim: Consider any "stretched" range $$$[l_x, r_x]$$$, such that it contains $$$[l_0, r_0]$$$, and it also contains a cycle whose span strictly contains $$$[l_0, r_0]$$$. Let's call them "beautiful". Now consider the smallest of them, let's call it $$$[l_1, r_1]$$$. We claim that regardless of which direction you expand $$$[l_0, r_0]$$$, $$$[l_1, r_1]$$$ will be the first "beautiful" range you reach.
This means we just need to calculate the fastest way to get to $$$[l_1, r_1]$$$. Observe that since they are the first range in the way that strictly contains $$$[l_0, r_0]$$$, that means that expanding left will not make expanding right faster, and vice versa.
Therefore, it is best to expand in 1 direction until we encounter $$$[l_1, r_1]$$$. So, we can just simulate the process and choose which direction incurs the fewest costs.
If no cycle strictly contains the current range, then the range can only expand independently to the left or right. In this scenario, we calculate the cost of moving entirely to the left and to the right separately, then sum these costs to determine the total time.
Time complexity: $$$O(n)$$$ or $$$O(n * log(n))$$$, depending on the implementation.
