A flight plan
You need to draw up a flight plan: the plane takes off from one city, visits all the others once each and returns. Nobody will find the exact shortest tour for fifteen hundred cities, and there is no need: a tour no more than a tenth longer than the reference tour is enough. The reference is the one built by the methods in the article.
The plane flies along a great-circle arc; the distance is by the haversine formula with R = 6371 km, as in the problem “East there, west back”. The third test is all the cities of the world with half a million people or more, the fourth all towns with a population of 10,000 or more within 800 km of Almaty (GeoNames).
Input
The first line holds n (1 ≤ n ≤ 1500). Then n lines: the latitude and longitude of a city in degrees.
Output
One line: the numbers of all cities from 1 to n in the order of the flight, each exactly once. The tour is closed: after the last city the plane returns to the first. The answer is accepted if the length of the tour is at most 1.1 times the length of the reference tour.
Examples
Example 1
8 40.000 60.000 42.000 61.000 40.000 62.000 42.000 63.000 40.000 64.000 42.000 65.000 40.000 66.000 42.000 67.000
1 3 5 7 8 6 4 2
Example 2
15 45.000 77.000 47.500 76.062 49.330 73.500 50.000 70.000 49.330 66.500 47.500 63.938 45.000 63.000 42.500 63.938 40.670 66.500 40.000 70.000 40.670 73.500 42.500 76.062 45.000 70.000 46.000 71.000 44.000 69.000
11 12 1 2 3 4 5 6 14 13 15 7 8 9 10
Limits
- Time · Python
- 10000 ms
- Time · Go
- 4000 ms
- Memory
- 256 MB
- Judging
- 6 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
Start with the tour “each time to the nearest unvisited city” and compute its length. Why is the end of such a tour usually bad?
2Hint 2
If two edges of the tour cross, they can be replaced with two others, and the tour becomes shorter. How do you look for such pairs quickly, without trying all pairs of edges?
3The idea
Build a tour with nearest neighbour and improve it by local search, as in the article: 2-opt (replace two edges with two, reversing the piece between them) and Or-opt (move a piece of one to three cities elsewhere). There is no need to try all pairs of edges: the new edge must be shorter than the old one, so for city a it is enough to look at its nearest neighbours, and the “ten nearest” lists are computed once. Don’t-look bits send a city back for checking only if something next to it has changed.
4Walkthrough
Distances are computed once into a table. Nearest neighbour is O(n²). Then a queue of cities: take out a, and for the edge to the next city b try neighbours c from the list while d(a, c) < d(a, b); if replacing edges a–b, c–e with a–c, b–e pays, reverse the piece between them (the shorter one) and put the four affected cities in the queue. The same for the edge to the previous city. When the queue is empty, make an Or-opt pass; if it moved something, 2-opt again.
Nearest neighbour on its own loses more than ten per cent to the reference already on the first example and on all the real tests; 2-opt with neighbour lists alone is usually enough with room to spare.
4+Solution
5Complexity
The distance table and neighbour lists are O(n² log n), nearest neighbour O(n²). Local search with neighbour lists makes a dozen checks per city at a time and in practice grows almost linearly; reversing a piece costs up to n/2 swaps.
6Common mistakes
- Nearest neighbour only. On the large tests its tour is 13–21% longer than the reference: the last cities are left scattered, and reaching them means flying across half the map.
- 2-opt over all pairs. Correct, but each pass costs n²/2 checks; on fifteen hundred cities in Python that takes too long.
- Comparing without a margin. Distances are fractional, and a replacement with zero gain can look profitable because of rounding; without a small margin the search reverses the same piece back and forth.