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

Задача

Коды городов

паросочетания потоки граф геоданные

Каждому городу нужен свой код из трёх заглавных латинских букв, как у аэропортов. Правило такое: первая буква кода — первая буква названия, а две другие — буквы названия, которые стоят в нём дальше, в том же порядке. У BERN подходят коды BER, BEN и BRN, у BRNO — BRN, BRO и BNO. Двум городам нельзя дать один и тот же код, даже если названия у них одинаковые. Какому наибольшему числу городов можно раздать коды?

Тесты 4–6 — настоящие города мира с населением от 10 000 человек из GeoNames: все 45 204, двадцать тысяч самых больших и все, чьё название начинается на S. Из названий убраны пробелы, дефисы, апострофы и надстрочные знаки, буквы вроде Ł или Ø заменены на L и O, а названия короче трёх букв не вошли.

Вход

В первой строке число городов n (1 ≤ n ≤ 50 000). Дальше n строк — названия из заглавных латинских букв, от 3 до 40 букв в каждом. Разных пар «название — подходящий код» не больше 1,2 · 10⁶.

Выход

Одно число — наибольшее число городов, которые получат коды.

Примеры

Пример 1

Вход
4
BERN
BRNO
BREST
BARI
Выход
4

Пример 2

Вход
4
ORAN
ORA
ORN
OAN
Выход
3

Ограничения

Время · Python
9000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
10 тестов

Разбор

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

1Подсказка 1

Это задача о парах: слева города, справа коды, ребро — «код подходит городу». Нужно наибольшее паросочетание. Сколько всего кодов может понадобиться и сколько рёбер у графа на всех городах мира?

2Подсказка 2

Городов 45 тысяч, а кодов, которые хоть кому-то подходят, 16 046: две трети городов останутся без кода. Чем это плохо для алгоритма, который ищет пару каждому городу по очереди?

3Идея

Паросочетание — это поток в сети исток → города → коды → сток со всеми ёмкостями 1. У каждого города одна входящая дуга, у каждого кода одна исходящая — сеть единичная, и по теореме о единичных сетях алгоритм Диница делает не больше 2√V + 1 фаз, каждую за O(E). Удобно держать его в виде алгоритма Хопкрофта — Карпа: фаза раскладывает города по длине чередующегося пути от свободного города, а поиск в глубину с указателями берёт столько кратчайших путей без общих вершин, сколько помещается.

4Разбор

Для каждого названия перебираем пары позиций i < j после первой буквы и собираем множество кодов без повторов. Дальше — фазы. Обход в ширину стартует сразу от всех свободных городов: из города идём по каждому его коду, и если код занят, следующий слой — город, который его держит. Как только встретился свободный код, кратчайшая длина известна. Затем от каждого свободного города идёт поиск в глубину только по слоям; указатель nxt[u] помнит, какой код города u пробовать дальше, а город, у которого коды кончились, помечается тупиком до конца фазы. Найденный путь переворачивается: каждый город на нём забирает код, через который пришёл поиск.

Фаз на всех городах мира — пять. В Go коды удобно считать числами 676 · первая + 26 · вторая + третья, тогда вместо словаря хватает массива на 17 576 элементов.

4+Решение
5Сложность

Рёбер столько, сколько пар «название — код»: на всех городах мира около миллиона. Каждая фаза — O(E), фаз O(√V), на деле пять. Эталон на Python укладывается в секунду с небольшим.

6Типичные ошибки
  • По одному пути за обход. Обход в ширину ищет один увеличивающий путь, путь переворачивается, обход начинается заново — так работает Эдмондс — Карп. Это wrong.py: каждый выданный код стоит обхода всего графа, а кодов выдать надо почти пятнадцать тысяч. На всех городах он не укладывается во время.
  • Кун. Поиск в глубину от каждого города по очереди тоже верен, но город, которому кода не досталось, обходит перед отказом всё, до чего дотягиваются чередующиеся пути, а таких городов тридцать тысяч. На всех городах мира Кун на Python работает почти минуту.
  • Жадно. Если давать каждому городу первый свободный код, на всех городах коды получат 14 049 вместо 14 864: ранний город может занять единственный код позднего.
  • Повторы. У названия вроде SANTAANA одна и та же тройка букв получается из разных позиций. Это одно ребро, и если не убрать повторы, граф распухнет.

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

GRA Алгоритм Алгоритм Диница Наибольший поток фазами: слоистая сеть, блокирующий поток, указатели; O(V²E), а в единичных сетях O(E√V). O(V² E) 2 задачи GRA Алгоритм Паросочетания в двудольном графе Наибольшее число пар в двудольном графе: Кун, Хопкрофт — Карп, теоремы Кёнига и Холла. O(E √V) 2 задачи
Каталог алгоритмов