У алгоритмов, использующих хеширование, есть один неприятный недостаток: недетерминированность. Если мы сгенерируем бесконечное количество примеров, то когда-нибудь нам не повезет, и программа отработает неправильно. На CodeForces даже иногда случаются взломы решений, использующих хеширование — можно в оффлайне сгенерировать тест против конкретного решения. Есть даже гайды про то, как это делать.
Событие, когда два хеша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set
различных случайных значений в промежутке . Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать , чтобы не бояться такого?
#Выбор констант
Практическое правило: если вам нужно хранить различных хешей, то безопасный модуль — это число порядка . Обоснование — см. парадокс дней рождений.
Не всегда такой модуль можно выбрать один — если он будет слишком большой, то при умножении будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хешей параллельно.
Можно также брать «модуль» . У него есть несколько преимуществ:
- Он большой — второй модуль точно не понадобится.
- С ним ни о каких переполнениях заботиться не нужно — если все хранить в
unsigned long long
, процессор сам автоматически сделает эти взятия остатков при переполнении. - С ним хеширование будет значительно быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию
%
.
Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако его добавляют далеко не на все контесты — имейте это в виду.
В выборе же ограничения не такие серьезные:
- Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
- Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.
Главное — чтобы значения и модуля не знал человек, который генерирует тесты.
#Парадокс дней рождений
В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.
Более общее утверждение: в мультимножество нужно добавить случайных чисел от 1 до n, чтобы какие-то два совпали.
Первое доказательство (для любителей матана). Пусть это вероятность того, что в группе из человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от до .
Попытаемся оценить :Из последнего выражения более-менее понятно, что вероятность достигается при и в этой точке изменяется очень быстро.
Второе доказательство (для любителей теорвера). Введем индикаторов — по одному для каждой пары людей — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна .
Обозначим за число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть .
Отсюда понятно, что если , то ожидание равно константе, а если асимптотически больше или меньше, то стремится нулю или бесконечности соответственно.
Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.
#Бонус: «мета-задача»
Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.
«Решите» задачу.