Две ячейки
В хеш-таблице n ячеек, и у каждого ключа есть ровно две ячейки, в которые его можно положить (они могут совпадать). В ячейке помещается один ключ. Ключи добавляются по одному, и уже положенные можно перекладывать в их другую ячейку — так делает хеширование кукушки. Выведите номер первого ключа, после добавления которого разложить все добавленные ключи по ячейкам уже невозможно, или 0, если все ключи помещаются. Среди тестов — пути файлов этого сайта, разложенные двумя хешами CRC-32.
Вход
В первой строке — n и число ключей m (1 ≤ n, m ≤ 2·105). Дальше m строк: две ячейки ключа, числа от 1 до n.
Выход
Номер первого ключа (с единицы), после которого ключи не помещаются, или 0.
В первом примере третий ключ просит те же ячейки 1 и 2, что первый, и обе заняты. Но второй ключ можно переложить из ячейки 2 в ячейку 3 — и всё помещается. А пятый ключ уже не влезает никак: пять ключей на ячейки 1–4, и каждый просит ячейки только из них.
Примеры
Пример 1
4 6 1 2 2 3 1 2 3 4 4 1 2 4
5
Пример 2
3 4 1 1 2 3 3 2 2 2
4
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Нарисуйте граф: ячейки — вершины, ключ — ребро между своими двумя ячейками. Что значит «разложить ключи по одному в ячейку» на языке этого графа?
2Подсказка 2
В связном куске графа с V вершинами и E рёбрами каждое ребро должно получить свою вершину. Сколько рёбер можно разместить, если кусок — дерево? А если в нём есть цикл?
3Идея
Разложить ключи — значит каждому ребру назначить один из его концов так, чтобы никакая вершина не досталась двум рёбрам. В связном куске это возможно тогда и только тогда, когда рёбер не больше, чем вершин. Если E > V, вершин просто не хватит. Если кусок — дерево (E = V − 1), подвесим его за любую вершину и отдадим каждое ребро нижнему концу. Если E = V, в куске ровно один цикл: рёбра цикла отдаём по кругу — каждому следующую вершину, а деревья, растущие из цикла, — как раньше. Петля (обе ячейки одинаковы) — это цикл из одного ребра.
4Разбор
Ключи приходят по одному, поэтому куски графа только сливаются — работа для системы непересекающихся множеств. В корне каждого множества храним число вершин и рёбер. Ребро внутри множества добавляет одно ребро, ребро между двумя множествами сливает их и добавляет одно ребро. Как только в каком-то множестве рёбер стало больше вершин, ответ — номер этого ключа.
Самое интересное — где это происходит. В шестом тесте 200 000 ячеек и случайные пары; ломается на ключе 100 020 — ровно когда таблица заполнена наполовину. Это известный порог хеширования кукушки с двумя хешами: случайный граф с m рёбрами на n вершинах при m < n/2 почти наверняка состоит из деревьев и кусков с одним циклом, а за этим порогом в нём появляется большой кусок со многими циклами. На путях файлов сайта то же: в 8000 ячеек помещается 4186 ключей. А жадное размещение без перекладки — класть в свободную из двух ячеек и сдаваться, когда обе заняты, — на тех же случайных парах ломается уже на 4506-м ключе.
4+Решение
5Сложность
O((n + m)·α(n)) — почти линейно.
6Типичные ошибки
- Жадность без перекладки. Свободной ячейки среди двух может не быть, а место всё же есть — если подвинуть уже лежащие ключи по цепочке. Первый пример: жадность сдаётся на третьем ключе, а сломается только пятый.
- Петля. Ключ с двумя одинаковыми ячейками — тоже ребро, и оно занимает свою вершину.
- Граница. Кусок с рёбрами, равными вершинам, ещё помещается: один цикл — это нормально.
Алгоритмы задачи
O(d) на решение: узнать нагрузку d серверов
2 задачи
DS
Структура данных
Система непересекающихся множеств
Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма.
O(α(n))
2 задачи