Try   HackMD

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

1. Abridged Statement:

Given

n tables, each table has a book. The table is numbered from
0
to
n1
, and each book has a distinct value from
0
to
n1
(let's denote the value of the book on the
ith
table as
pi
). Initially, lil Johnson starts at table number
s
(
0s<n
), and is not holding any book.

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

s, then he can either go to table number
s1
or
s+1
(obviously, he has to maintain
0s<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
    n1
    .
  • n106
    ,
    0s<n
    .
  • Time limit: 2 seconds. That means the complexity must be
    O(n)
    or
    O(nlog(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

p00, and
pn1n1
.

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

i=0n1|pii|.

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

ipi, it forms a cycle (or circle for uncultured peasants). That is because you can bring the book at table number
s
to table number
ps
, then the book at table number
ps
to the table number
pps
, 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!

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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.

  1. Pick up
    p0
    book.
  2. Go to table number
    1
    and replace the book. Note that we are switching to cycle
    [1,3]
    here.
  3. 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.
  4. 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.

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:

  • 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
[l1,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,n1], while ensuring the cost is minimized.

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

(s+1)(ns), therefore, this would easily solve the
s=0,n106
and the
n103
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

[l0,r0]. Let us also assume there exists a cycle whose span
[x1,x2]
strictly contains the current range, i.e., (
x1<l0r0<x2
).

Claim: Consider any "stretched" range

[lx,rx], such that it contains
[l0,r0]
, and it also contains a cycle whose span strictly contains
[l0,r0]
. Let's call them "beautiful". Now consider the smallest of them, let's call it
[l1,r1]
. We claim that regardless of which direction you expand
[l0,r0]
,
[l1,r1]
will be the first "beautiful" range you reach.

Proof:

Proof by contradiction: Assuming there exist two distinct "beautiful" and "stretched" ranges

[l1,r1] and
[l2,r2]
, such that it is possible to reach them before reaching any other "beautiful" ranges from
[l0,r0]
.

  • These ranges cannot intersect (

    l1l2r1r2, or vice versa). Because if they do, then every element appears in
    [l1,r1][l2,r2]
    do not appear in
    [l2,r2]
    , and vice versa. Therefore, the two segments
    [l1,r1][l2,r2]
    and
    [l2,r2][l1,r1]
    are actually useless, and we would encounter the segment
    [max(l1,l2),min(r1,r2)]
    first, which is contradicting.

  • Without loss of generality, assume

    [l1,r1] contains
    [l2,r2]
    . This implies that every element appears in
    [l1,r1][l2,r2]
    do not appear in
    [l2,r2]
    , because if they do,
    [l2,r2]
    is not "stretched," contradicting the definition.

  • However, that means that

    [l1,r1][l2,r2] is useless too, so no matter which direction we expand from
    [l0,r0]
    , we will encounter
    [l2,r2]
    before
    [l1,r1]
    , which, again, contradicts our definition.

Thus,

[l1,r1]=[l2,r2].

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

[l1,r1]. But that is not enough. Observe that since they are the first range in the way that strictly contains
[l0,r0]
, 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

[l1,r1]. So, we can just simulate the process and choose which direction incurs the fewest costs.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

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(nlog(n))
, depending on the implementation.

My code