Задачник Базовый курс EN

Туда на восток, обратно на запад

динамика оптимизация точки на плоскости геоданные олимпиады

Почтовый самолёт облетает n городов и возвращается домой. Диспетчеры упростили расписание: сначала самолёт летит только на восток — каждый следующий город восточнее предыдущего, — от самого западного города до самого восточного, а потом только на запад, обратно к самому западному. Каждый город он посещает ровно один раз: либо по дороге туда, либо по дороге обратно. Какой самый короткий маршрут такого вида?

Самолёт летит по дуге большого круга. Расстояние между городами с широтами φ₁, φ₂ и долготами λ₁, λ₂ (в радианах), R = 6371 км:

$$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}}.$$

Третий тест — все города мира от миллиона жителей, четвёртый — города в 600 км вокруг Алматы (GeoNames).

Вход

В первой строке n (1 ≤ n ≤ 3000). Дальше n строк: широта и долгота города в градусах (−90 ≤ широта ≤ 90, −180 ≤ долгота ≤ 180). Долготы всех городов различны.

Выход

Длину самого короткого маршрута в километрах; ответ принимается с относительной погрешностью 10⁻⁶. При n = 1 лететь некуда, ответ 0; при n = 2 — туда и обратно.

Примеры

Пример 1

Вход

4
43.250 76.920
51.170 71.430
42.870 74.590
41.310 69.280

Выход

2746.486827

Пример 2

Вход

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

Выход

3799.431197

Ограничения

Время · Python: 6000 мс
Время · Go: 3000 мс
Память: 256 МБ
Проверка: 8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Самый простой маршрут такого вида — взять по дороге на восток все города, а назад лететь без остановок. Сравните его с ответом второго примера.

2Подсказка 2

Отсортируйте города с запада на восток и представьте маршрут как два пути из самого западного города, которые вместе проходят все города и встречаются в самом восточном. Что нужно знать о двух путях, которые уже прошли первые j городов?

3Идея

Задача коммивояжёра в общем виде трудна, но ограничение «только на восток, потом только на запад» её сильно упрощает: маршрут такого вида называют битоническим. Пусть города пронумерованы с запада на восток от 0 до n − 1. Обозначим b(i, j), i < j, — наименьшую суммарную длину двух путей из города 0, которые вместе проходят все города 0…j по разу и кончаются в i и в j. Город j + 1 присоединяется к одному из двух концов:

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

Ответ — b(n − 2, n − 1) + d(n − 2, n − 1): последний город замыкает оба пути. Это динамика на O(n²) состояниях и переходах — вместо 2ⁿ⁻² способов разложить города на «туда» и «обратно».

4Разбор

Почему хватает двух чисел: путь «туда», отсечённый на городе j, и путь «обратно», прочитанный с конца, — это два пути из города 0 на восток. Всё, что нужно знать о них для продолжения, — где кончается каждый: следующий город j + 1 восточнее всех пройденных, и к нему можно прийти только из одного из двух концов. Один конец всегда j, иначе город j пропущен; поэтому достаточно помнить второй конец i.

Хранить всю таблицу не нужно: строка для j + 1 считается из строки для j. В эталоне на Python строка — массив numpy, и обе формулы — одно действие над массивом. Во втором примере города стоят зигзагом: южнее, севернее, снова южнее. Маршрут «всё по дороге туда» мечется между ними и выходит 7319 км. Лучший летит на восток по южным городам, а северные собирает на обратном пути: 3799 км.

4+Решение

5Сложность

O(n²) времени и O(n) памяти. Для 3000 городов это 4,5 миллиона расстояний.

6Типичные ошибки

Все города по дороге туда. Такой маршрут разрешён, но почти никогда не самый короткий: города, лежащие в стороне от прямой, выгоднее собрать на обратном пути.
Перебор раскладок. Каждый город, кроме крайних, идёт «туда» или «обратно» — 2ⁿ⁻² вариантов; при n = 30 это уже сотни миллионов.
Несортированный вход. Восток и запад — это порядок по долготе; динамика по номерам из входа считает совсем другие маршруты.

Алгоритмы задачи

GRA Алгоритм Задача коммивояжёра Кратчайший объезд всех точек: ближайший сосед, 2-opt со списками соседей, Or-opt, оценка Хелда — Карпа. NP-трудна; точно O(2ⁿ · n²) 2 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи