Tutorial for problem "D. Kings Problem?"

In this problem to create a wright solution you need to perform the following chain of inferences (though, if you skip some steps or do them not completely, you can still get an AC solution :) ):

• Note that after we visit the city numbered n + 1, the further answer depends only from the leftmost and the rightmost unvisited cities (and it would be optimal to come to the nearest to n + 1-th city of them, and the come to another of them). That's why we know the answer for the case k = n + 1, and won't consider this case later.
• Before we visit the n + 1-th city, - this part of the path covers some segment of cities lying in the OX axis. This segment, obviously, contains the point k. But we can't iterate over all such possible segments, because there are O(n²) of them, so it's still a slow solution.
• Let's understand the following fact: if before visiting city n + 1 we visited some other cities, but neither the leftmost nor the rightmost, then it was surely unprofitable. Really, after we come into the n + 1, the answer will depend only on the leftmost and the rightmost of non-visited cities. So, if before the n + 1-th city we performed some movements, but didn't change the leftmost and the rightmost cities, then it was completely unnecessary and unprofitable action.
• We can can get even more: there is no optimal solution, where we should move from the start city k to the n + 1-th city directly, without vithout visiting other cities (here I suppose that k is neither the leftmost nor the rightmost city). Btw, this step of reasoning could be skipped - we can believe it's sometimes profitable to come from k to n + 1 directly, and it's not difficult to support this case in a solution we'll build later; but in order to describe the problem completely let's prove this fact too. In order to prove this, let's write down two formulas: first for the length of the answer if we come from k to n + 1 directly, then come to city 1, and then to city n (here I suppose that 1 and n are the leftmost and the rightmost cities, accordingly, and city 1 is nearer to n + 1 than n); second formula - for the length of the answer if we come from k to 1 first, then to n + 1, then to k + 1, and then to n. If we compare these two formulas, then after the cancellation of like terms we can use the triangle's inequality to see that the second formula always gives smaller value (at least, not greater) than the first. So, it's really unprofitable to come from k to n + 1 directly.
• So, to make a right solution, it's enough to iterate over only two types of segments: [1;i] for i ≥ k, and [i;n] for i ≤ k (here I suppose for convenience that cities are sorted by their x-coordinate).
• The last idea is how to process each of these cases accurately. In order to do this we iterate over all possible i = 1... n. Let, for example, i ≤ k. Then we have to try the following case: go from k to n, then return to i, then come to n + 1, and then return back to the OX axis if need (if i > 1). Also it is required to check another type of cases: try to go from k to i, then to n, and then come to n + 1, and return back to the OX axis if need. Answer for each of these cases can be calculated in O(1). For i ≥ k everything is symmetric.

So, not taking into account the sorting of the citites in the beginning of the program, we get a O(n)-solution.