The official solution isn't exactly the clearest, so I guess I will present own solution to this problem.
Codeforces blog: Codeforces: My Solution to IOI17 P6 - Ancient Books
Given
Lil Johnson has four possible operations:
(1) If lil Johnson isn't holding a book, and there is a book in the current table, then he can pick it up.
(2) If lil Johnson is holding a book, and there is no book in the current table, then he can put that book down.
(3) If lil Johnson is holding a book, and there is also a book in the current table, then he can replace the book.
(4) Lil Johnson go to the left or to the right i.e. if he is current at position
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
Example:
Constraint:
For the sake of simplicity, we will assume that
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
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
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
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.
Therefore, our algorithm for checking whether the answer reached our "lower bound" would look something like this:
// get the maximum and minimum element of each cycle
vector<pair<int,int>> range(n, {-1, -1});
for(int i = 0; i < n; ++i){
if (range[i].first != -1) continue;
pair<int,int> mi = {i, i};
int j = p[i];
while(j != i){
// maximize_range means that it takes in two range, then minimize the left boundary and maximize the right boundary.
maximize_range(mi, make_pair(j, j));
j = p[j];
}
do{
range[j] = mi;
j = p[j];
} while(j != i);
}
// check if as we are sorting the current cycle, whether we can go outside
pair<int, int> cur = {s, s};
pair<int, int> target = range[s];
while(cur.first > target.first || cur.second < target.second){
if (cur.first > target.first){
maximize_range(target, range[--cur.first]);
}
else{
maximize_range(target, range[++cur.second]);
}
}
if (cur.first == 0 && cur.second == n-1) cout << "Yes\n":
else cout << "No\n":
Explaination of the algorithm:
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,
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
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
This let us arrive at a range DP solution, featuring three operations: expand to the left, expand to the right, and "stretch" the current range:
ll dp[n][n]; memset(dp, 63, sizeof dp);
dp[s][s] = 0;
for(int i = n-1; i >= 0; --i)
for(int j = i; j <= n; ++j){
// calculate the stretched range, I omitted the detail of the function for brevity.
pair<int, int> stretched = stretch_range(make_pair(i, j));
minimize(dp[stretched.first][stretched.second], dp[i][j]);
if (i > 0) minimize(dp[i-1][j], dp[i][j] + 2);
if (j + 1 < n) minimize(dp[i][j+1], dp[i][j] + 2);
}
}
cout << dp[0][n-1] + ans_lower_bound << "\n";
Note that the number of distinct states in our dp table is
Let's call the current range (stretched) we are working with
Claim: Consider any "stretched" range
Proof by contradiction: Assuming there exist two distinct "beautiful" and "stretched" ranges
These ranges cannot intersect (
Without loss of generality, assume
However, that means that
Thus,
This means that the number of states we need to consider is greatly reduced, as we just need to calculate the fastest way to get to
Therefore, it is best to expand in 1 direction until we encounter
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: