Problems Base course RU

East there, west back

dynamic programming optimization points geodata contests

A mail plane flies around n cities and returns home. The dispatchers have simplified the schedule: first the plane flies only east, each next city east of the previous one, from the westernmost city to the easternmost, and then only west, back to the westernmost. It visits each city exactly once: either on the way out or on the way back. What is the shortest tour of this kind?

The plane flies along a great-circle arc. The distance between cities with latitudes φ₁, φ₂ and longitudes λ₁, λ₂ (in radians), R = 6371 km:

$$d = 2R \arcsin \sqrt{\sin^2\frac{\varphi_2 - \varphi_1}{2} + \cos\varphi_1 \cos\varphi_2 \sin^2\frac{\lambda_2 - \lambda_1}{2}}.$$

The third test is all the cities of the world with a million people or more, the fourth the towns within 600 km of Almaty (GeoNames).

Input

The first line holds n (1 ≤ n ≤ 3000). Then n lines: the latitude and longitude of a city in degrees (−90 ≤ latitude ≤ 90, −180 ≤ longitude ≤ 180). The longitudes of all cities are distinct.

Output

The length of the shortest tour in kilometres; the answer is accepted with a relative error of 10⁻⁶. For n = 1 there is nowhere to fly, and the answer is 0; for n = 2 it is there and back.

Examples

Example 1

Input

4
43.250 76.920
51.170 71.430
42.870 74.590
41.310 69.280

Output

2746.486827

Example 2

Input

7
40.000 60.000
50.000 62.000
40.500 64.000
50.500 66.000
41.000 68.000
49.000 70.000
40.000 72.000

Output

3799.431197

Limits

Time · Python: 6000 ms
Time · Go: 3000 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The simplest tour of this kind is to take all the cities on the way east and fly back without stopping. Compare it with the answer to the second example.

2Hint 2

Sort the cities from west to east and think of the tour as two paths from the westernmost city that together pass through all the cities and meet at the easternmost. What do you need to know about two paths that have already passed the first j cities?

3The idea

The travelling salesman problem is hard in general, but the restriction “only east, then only west” simplifies it greatly: a tour of this kind is called bitonic. Let the cities be numbered from west to east from 0 to n − 1. Denote by b(i, j), i < j, the smallest total length of two paths from city 0 that together pass through all cities 0…j once each and end at i and at j. City j + 1 attaches to one of the two ends:

$$b(i, j+1) = b(i, j) + d(j, j+1) \text{ for } i < j, \qquad b(j, j+1) = \min_{k < j} \bigl(b(k, j) + d(k, j+1)\bigr).$$

The answer is b(n − 2, n − 1) + d(n − 2, n − 1): the last city closes both paths. This is dynamic programming on O(n²) states and transitions, instead of 2ⁿ⁻² ways of splitting the cities into “out” and “back”.

4Walkthrough

Why two numbers are enough: the outward path cut off at city j and the return path read from the end are two paths from city 0 going east. All you need to know about them to continue is where each ends: the next city j + 1 is east of all those passed, and it can be reached only from one of the two ends. One end is always j, otherwise city j would be skipped; so it is enough to remember the other end i.

There is no need to store the whole table: the row for j + 1 is computed from the row for j. In the Python reference a row is a numpy array, and each formula is a single array operation. In the second example the cities stand in a zigzag: south, north, south again. The tour “everything on the way out” rushes back and forth between them and comes to 7319 km. The best one flies east through the southern cities and collects the northern ones on the way back: 3799 km.

4+Solution

5Complexity

O(n²) time and O(n) memory. For 3000 cities that is 4.5 million distances.

6Common mistakes

All cities on the way out. Such a tour is allowed but is almost never the shortest: cities lying off the straight line are better collected on the way back.
Enumerating the splits. Each city except the extreme ones goes “out” or “back”, 2ⁿ⁻² options; at n = 30 that is already hundreds of millions.
Unsorted input. East and west are the order by longitude; dynamic programming over the input numbers computes quite different tours.

Algorithms behind it

GRA Algorithm Travelling salesman problem The shortest tour of all points: nearest neighbour, 2-opt with neighbour lists, Or-opt, the Held–Karp bound. NP-hard; exactly O(2ⁿ · n²) 2 problems DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems