Задача о перемещении между островами
Отдыхая в деревне, Пётр мысленно вернулся в детство и вспомнил одну из своих любимых компьютерных игр. В мире этой игры произошёл катаклизм, разорвавший его на множество островов, летающих в космическом пространстве. Со временем острова расположились в пространстве ровным рядом, один за другим.
После катаклизма, осталось всего два способа путешествовать по миру:
- магические паромы, перемещающиеся между соседними островами (естественно, паром может двигаться в обе стороны); таким образом с острова, который стоит на i-ом месте в космическом ряду, можно попасть на i-1 и i+1 острова;
- порталы, через которые можно телепортироваться между островами независимо от расстояния, но только если до катаклизма эти острова составляли один материк (любопытно, что материки в этом мире имели не названия, а номера).
Петру стало интересно, за какое минимальное количество перемещений можно добраться от первого острова до последнего. Помогите ему это выяснить (сам он всё ещё отдыхает).
Входные данные (поступают в стандартный поток ввода)
На вход вашей программе подаётся одна строка, содержащая массив целых чисел islands, где islands[i] - это числовое обозначение материка, к которому когда-то относился i-ый остров. Элементы в массиве расположены в том же порядке, что и острова в космическом пространстве.
Причём, -100 000 000 ≤ islands[i] ≤ 100 000 000, а количество островов n удовлетворяет условию 1 ≤ n ≤ 50 000.
Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются.
Выходные данные (ожидаются в стандартном потоке вывода)
Одно целое число, минимальное число шагов от первого острова до последнего.
Пример 1
Ввод:
3 5 2 2 5
Вывод:
2
Простой пример для ознакомления с входными и выходными данными.
На вход подаются 5 островов.
С первого острова можно попасть только на второй с помощью парома. Порталы использовать не получится, т.к. нет других островов носящих тот же номер материка.
Со второго можно добраться на пароме обратно на первый или вперёд на третий. А также можно переместиться через портал на пятый (ведь они имеют один и тот же номер).
Таким образом мы можем переместиться от первой ячейки до последней за два шага.
Пример 2
Ввод:
11 -86 -86 201 11 86 86 86 3 201
Вывод:
3
Во втором примере потребуется уже 3 шага: Перемещение через портал до 5го острова, шаг назад до 4го (с помощью парома) и, наконец, скачок через портал до последнего.
Пример 3
Ввод:
3 2 5 2 5 2 5 3
Вывод:
1
Тривиальный пример: требуется всего одно перемещение через портал от первого острова до последнего.
Я написал следующий код:
def teleportation(islands):
n = len(islands)
min_teleports = 0
i = 0
while i < (n - 1):
for j in reversed(range(i + 1, n)):
island_1 = islands[i]
island_2 = islands[j]
if island_1 == island_2:
i = j
min_teleports += 1
break
if i < (n - 1):
i += 1
min_teleports += 1
return min_teleports
if __name__ == '__main__':
islands = [int(x) for x in input().split()]
print(teleportation(islands))
но для второго примера он не годится. Как доработать?
Ответы (2 шт):
Ваше решение предполагает что мы всегда двигаемся слева направо. Второй пример показывает что это не так, иногда выгодно двигаться влево. Не думаю что ваше решение можно доработать. Задача предполагает навигацию по графу и решается поиском в ширину. Возможно, есть другое решение, которое я не увидел.
Построим двудольный граф: в первой доле реальные острова, во второй доле дополнительные узлы в цепочке и материки. Любой путь между реальными островами в таком графе будет иметь чётную длину. Деля её пополам получим ответ к задаче.
Материк оформляется как звезда: центральный узел материка связан со всеми своими островами. В цепочку между островами вставлены дополнительные узлы.
Граф индексируется целыми числами. Реальный остров i получает индекс 2i в графе, индексы между реальными островами занимают дополнительные узлы. Индексы материков последовательные, начиная с 2n - 1, где n количество реальных островов.
Задача решается поиском в ширину по графу от узла 0 до узла 2n - 2. Множества посещённых узлов нет, его роль играет список distance:
import collections
islands = input().split()
n = len(islands)
graph = [[] for _ in range(2 * n - 1)]
def connect(j1, j2):
graph[j1].append(j2)
graph[j2].append(j1)
for j in range(2 * n - 2):
connect(j, j + 1)
continents = {}
for i, c in enumerate(islands):
k = continents.setdefault(c, len(graph))
if k == len(graph):
graph.append([])
connect(2 * i, k)
distance = [0] * len(graph)
queue = collections.deque([0])
while queue:
j = queue.popleft()
if j == 2 * n - 2:
break
for k in graph[j]:
if distance[k] == 0:
distance[k] = distance[j] + 1
queue.append(k)
print(distance[2 * n - 2] // 2)
$ echo 3 5 2 2 5 | python journey.py 2 $ echo 11 -86 -86 201 11 86 86 86 3 201 | python journey.py 3 $ echo 3 2 5 2 5 2 5 3 | python journey.py 1 $ time python -c "print(*[1] * 50000)" | python journey.py 1 real 0m0.205s user 0m0.220s sys 0m0.008s $ time python -c "print(*range(50000))" | python journey.py 49999 real 0m0.267s user 0m0.264s sys 0m0.028s
Моя идея решения: Первое - надо обрабатывать в первую очередь вершины материки, потому что количество шагов до остальных вершин и так известно. Второе (додумался когда закончились попытки) - когда мы обработали все вершины материки мы можем вычислить оставшееся количество шагов, как последний индекс элемента - текущий индекс элемента + вес текущего элемента (кол шагов до него), потому что если использовать дейкстру (очередь с приоритетом), в каждый момент времени мы обрабатываем самый короткий маршрут значит нет смысла ходить по вершинам когда все материки обработали, как только мы обработали последний материк (в очереди нет вершин материков) оставшейся маршрут это переходы на следующую вершину до конца массива.
Попробую описать еще раз. Например, у нас на входе массив arr 0 2 3 2 8 9
на первом шаге я иду по массиву и сохраняю в мап[arr[i]] = list.add(i),
на втором шаге обрабатываю мап только те ключи, где больше одного элемента в значении (это материки), беру самый первый (остальные не трогаю)
и добавляю в очередь,
на 3 шаге обрабатываю очередь и в ходе обработки добавляю туда новые элементы, обновляю расстояния (обычный дейкстра).
Я отправил такое решение оно не укладывалось по времени. Попытки закончились. У меня появилась идея, что нет смысла обрабатывать все вершины
как только я обработаю все материки это вершины индексы 1 и 3 из примера, я буду находится в точке с самым коротким маршрутам и на оставшемся
пути нет материков, поэтому я могу просто прибавить к текущему весу оставшееся количество элементов arr.length - curr_index + curr_weight и
получу самый короткий путь