Гнёзда кукушки
В таблице кукушки m гнёзд, пронумерованных от 1 до m. У каждого из n ключей ровно два гнезда, которые для него выбрали хеш-функции: ключ может жить только в одном из них. В гнезде помещается не больше одного ключа. Ключи можно раскладывать как угодно, не обязательно по правилам вытеснения. Сколько ключей можно разместить одновременно?
Гнёзда ключа могут совпадать — тогда у него всего одно гнездо. Несколько ключей могут иметь одни и те же гнёзда. Три теста — настоящие: названия городов мира от 10 000 жителей (GeoNames), разложенные двумя хеш-функциями по двум таблицам разного размера.
В первом примере пять ключей и четыре гнезда, и каждый ключ связан с остальными через общие гнёзда: больше четырёх не разместить, а четыре можно — например, ключи 1, 2, 4, 5 в гнёзда 1, 3, 4, 2. Во втором примере две отдельные группы: в гнёзда 1, 2, 3 претендуют четыре ключа, а в гнёзда 5 и 6 — два, и всего помещается 3 + 2 = 5.
Вход
В первой строке n и m (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 106). Дальше n строк по два номера гнёзд ключа a и b (1 ≤ a, b ≤ m).
Выход
Одно число — сколько ключей можно разместить одновременно.
Примеры
Пример 1
5 4 1 2 2 3 1 3 3 4 2 4
4
Пример 2
6 8 1 2 2 3 3 1 1 3 5 6 6 6
5
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 13 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Нарисуйте граф: гнёзда — вершины, ключи — рёбра между двумя своими гнёздами. Разместить ключ — значит отдать ребро одной из его вершин, и у каждой вершины не больше одного ребра.
2Подсказка 2
Куски графа, не связанные друг с другом, не мешают друг другу. Сколько рёбер помещается в куске из V вершин, если рёбер в нём E?
3Идея
В связном куске из V гнёзд и E ключей помещается ровно min(E, V) ключей. Больше V нельзя — в каждом гнезде один ключ. Если E ≤ V, помещаются все: так доказано в статье, кусок — дерево или дерево с одним циклом, и ключи раскладываются «от цикла наружу». Если E > V, выберем остовное дерево куска — V − 1 ключ — и добавим ещё один ключ: такой кусок из V рёбер раскладывается целиком, и занятыми оказываются все V гнёзд. Ответ — сумма min(E, V) по кускам.
4Разбор
Куски находим системой непересекающихся множеств: каждый ключ объединяет свои два гнезда. Потом для каждого корня считаем рёбра — ключи, у которых этот корень, — и вершины — гнёзда, к которым приходит хоть один ключ. Гнёзда, куда не претендует никто, ни на что не влияют, их не считаем. Ключ с двумя одинаковыми гнёздами — петля: ребро в куске есть, лишней вершины нет.
На названиях городов видно то же, что в статье. Ниже порога, при заполнении 0,47, помещаются все 42 311 названий; чуть выше, при 0,53, — все, кроме восьми; когда гнёзд столько же, сколько названий, помещается 35 396 — 84 %.
4+Решение
5Сложность
O((n + m) · α(m)) — почти линейно.
6Типичные ошибки
- Вставлять по правилам кукушки. Вытеснения с ограничением на их число теряют ключи, которые на самом деле помещаются: в восьмом тесте цепочка вытеснений длиной в тысячу гнёзд обрывается на пятидесятой. Это
wrong.py. Без ограничения вставка зацикливается в переполненном куске. - Считать вершины по всем гнёздам. min(E, V) нужно брать по каждому куску отдельно, а не min(n, m) на всю таблицу: лишние гнёзда одного куска не помогают другому.
- Забыть про петли и повторы. Ключ с одинаковыми гнёздами и десять ключей на одной паре гнёзд — обычные рёбра; кусок из двух гнёзд вмещает два ключа, сколько бы их ни претендовало.
Алгоритмы задачи
поиск — не больше d проб в худшем; вставка — O(1) в среднем ниже порога
1 задача
DS
Структура данных
Система непересекающихся множеств
Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма.
O(α(n))
2 задачи