TSP - Editorial

Let’s prove that optimal route has the following form:

1 < a_1 < a_2 < \ldots < n > b_1 > b_2 \ldots > 1.

To prove it, consider some optimal route. Let’s delete n from it for now and let’s try to insert it to some place in a route. If we are inserting between x < y, we are substracting weight of edge xy and adding weights of edges xn and yn. So, it will increase value by (n - x)D + c_{xn} + (n - y)D + c_{yn} - (y - x)D - c_{xy}= 2(n - y)D + c_{xn} + c_{yn} - c_{xy}

We can see that

2(n - y) - D \lt 2(n - y)D + c_{xn} + c_{yn} - c_{xy} \lt 2(n - y)D + 2D.

From that we can see that it always optimal to place n near n - 1.

With the same reasoning, we can show that n - 2 will be near the segment of n and n - 1(by deleting segment of n and n - 1 and couting contribution after inserting it between x and y).

So, it follows that each time we will insert smallest number either to the left, or to the right, so route indeed has such form.

Knowing the form of the optimal answer, we can write dynamic programming dp[x][y] -suppose that we have placed numbers from x to n and numbers on the border are x(it will be also on the border) and y, what’s the minimal length in this case? Then, we can add x - 1 to either left or right border, and update values by the following rules:

  • dp[x - 1][x] = min(dp[x - 1][x], dp[x][y] + weight_{x - 1 y})
  • dp[x - 1][y] = min(dp[x - 1][y], dp[x][y] + weight_{x - 1 x})

Where weight_{ab} denotes length of the edge ab.

Complexity of our solution is O(n^2).

1 Like

What is meant by the term “border” here?

Can you please explain a bit more? I read the editorial but literally got nothing other than the claim that the optimal sequence will be of form 1<a1<a2<…n>b1>b2>…1. I mean the meaning of dp states and transitions are quite unclear.

I believe border mean the starting and ending points. For example in {3,6,7,5,4} , 3 and 4 are borders

Suppose the border points are x and y , so dp[x][y] denotes the minimum cost to get the left border as x and right as y ,
Initial consider both the end-points are n
Consider x<y , so now from dp[x][y] you can go to either dp[x][x-1] or dp[x-1][y] adding corresponding edge weight respectively . Notice it mandatory to have x-1 as one of the end points as per the sequence formed .

This builds up pretty good intuition - Invitation to CodeChef SnackDown Elimination and Parallel Rated Contests - Codeforces