Пары из корзин
Сервис ищет почти одинаковые файлы. Для каждого файла уже посчитана подпись MinHash — k = b·r чисел. Подпись режут на b полос по r чисел подряд: первая полоса — числа с 1-го по r-е, вторая — с (r + 1)-го по 2r-е и так далее. Два файла становятся парой-кандидатом, если хотя бы одна полоса у них совпадает целиком — все r чисел на тех же местах.
Посчитайте, сколько различных пар файлов стали кандидатами. Затем для каждого кандидата сравните подписи целиком: пара подтверждена, если числа совпадают хотя бы на половине из k мест. Сколько кандидатов подтверждено? Среди тестов — подписи 3093 файлов из исходников Go.
Вход
В первой строке — n, b и r (1 ≤ n ≤ 3·104, 1 ≤ b·r ≤ 48). Дальше n строк — подписи: по b·r целых чисел от 0 до 65 535. Если для каждой полосы разложить файлы по группам с одинаковой полосой и сложить по всем группам всех полос число пар внутри группы, выйдет не больше 5·105.
Выход
Два числа: сколько различных пар стали кандидатами и сколько из них подтверждено.
В первом примере у первого и четвёртого файлов совпадают все три полосы, но это одна пара. Второй и первый совпадают только в первой полосе — два числа из шести, — и это кандидат, которого подпись не подтвердила.
Примеры
Пример 1
5 3 2 7 1 5 5 2 8 7 1 6 2 3 3 4 4 5 5 2 8 7 1 5 5 2 8 9 9 9 9 9 9
5 3
Пример 2
4 3 1 4 8 15 4 8 16 23 8 15 42 42 42
3 2
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Пара почти одинаковых файлов совпадает не в одной полосе, а во многих. Сколько раз она попадёт в корзины?
2Идея
Для каждой полосы раскладываем файлы по корзинам — словарь «значения полосы → список файлов». Каждая корзина из s файлов даёт s(s − 1)/2 пар. Но одна и та же пара может встретиться в нескольких полосах, и считать её надо один раз. Значит, пары складываем в множество — например, числом x·n + y при x < y. Работа — сумма пар по всем корзинам, её условие и ограничивает.
3Разбор
В Python ключ корзины — кортеж из r чисел, срез подписи; в Go — строка из упакованных байт или массив фиксированной длины. После того как кандидаты собраны, проверка каждого — проход по k числам двух подписей.
Почему двойной счёт так опасен, видно на тестах из исходников Go. При 12 полосах по 4 числа сумма пар по корзинам — 8799, а различных пар — 1848: почти одинаковые файлы совпадают в среднем почти в пяти полосах. При 24 полосах по 2 сумма — 34 021 при 7457 различных. Подтверждено 1478 и 1616 кандидатов: при длинных полосах лишних кандидатов меньше, при коротких больше, но подтверждённых при коротких больше — короткие полосы ловят и пары со сходством около порога. Это та же S-кривая, что в статье, только в целых числах.
Перебор всех пар с полным сравнением подписей тоже даёт подтверждённые пары, но не кандидатов — и при 30 000 файлов это 4,5·108 пар по 16 сравнений.
3+Решение
4Сложность
O(n·b) на раскладку по корзинам, O(P) на пары, где P — сумма пар по корзинам, и O(C·k) на проверку C кандидатов.
5Типичные ошибки
- Складывать пары из всех корзин. Пара, совпавшая в нескольких полосах, посчитается несколько раз; уже в первом примере выйдет 9 вместо 5.
- Подтверждать по одной полосе. Кандидат — не подтверждённая пара: совпадение одной полосы ничего не говорит об остальных числах.
- Полосы внахлёст. Полосы идут подряд и не перекрываются: j-я полоса — числа с номерами от (j − 1)r + 1 до jr.
Алгоритмы задачи
O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов
2 задачи
DS
Структура данных
Хеш-таблица
Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива.
O(1) в среднем
2 задачи