У алгоритмов, использующих хеширование, есть один неприятный недостаток: недетерминированность. Если мы сгенерируем бесконечное количество примеров, то когда-нибудь нам не повезет, и программа отработает неправильно. На CodeForces даже иногда случаются взломы решений, использующих хеширование — можно в оффлайне сгенерировать тест против конкретного решения. Есть даже гайды про то, как это делать.
Событие, когда два хеша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set $O(n^2)$ различных случайных значений в промежутке $[0, m)$. Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать $m$, чтобы не бояться такого?
Выбор констант
Практическое правило: если вам нужно хранить $n$ различных хешей, то безопасный модуль — это число порядка $10 \cdot n^2$. Обоснование — см. парадокс дней рождений.
Не всегда такой модуль можно выбрать один — если он будет слишком большой, то при умножении будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хешей параллельно.
Можно также брать «модуль» $2^{64}$. У него есть несколько преимуществ:
- Он большой — второй модуль точно не понадобится.
- С ним ни о каких переполнениях заботиться не нужно — если все хранить в
unsigned long long, процессор сам автоматически сделает эти взятия остатков при переполнении. - С ним хеширование будет значительно быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию
%.
Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако его добавляют далеко не на все контесты — имейте это в виду.
В выборе же $k$ ограничения не такие серьезные:
- Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
- Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.
Главное — чтобы значения $k$ и модуля не знал человек, который генерирует тесты.
Парадокс дней рождений
В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.
Более общее утверждение: в мультимножество нужно добавить $\Theta(\sqrt{n})$ случайных чисел от 1 до n, чтобы какие-то два совпали.
Первое доказательство (для любителей матана). Пусть $f(n, d)$ это вероятность того, что в группе из $n$ человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от $1$ до $d$.
$$ f(n, d) = (1-\frac{1}{d}) \times (1-\frac{2}{d}) \times ... \times (1-\frac{n-1}{d}) $$ Попытаемся оценить $f$: $$ \begin{aligned} e^x & = 1 + x + \frac{x^2}{2!} + \ldots & \text{(ряд Тейлора для экспоненты)} \\ & \simeq 1 + x & \text{(аппроксимация для $|x| \ll 1$)} \\ e^{-\frac{n}{d}} & \simeq 1 - \frac{n}{d} & \text{(подставим $\frac{n}{d} \ll 1$)} \\ f(n, d) & \simeq e^{-\frac{1}{d}} \times e^{-\frac{2}{d}} \times \ldots \times e^{-\frac{n-1}{d}} & \\ & = e^{-\frac{n(n-1)}{2d}} & \\ & \simeq e^{-\frac{n^2}{2d}} & \\ \end{aligned} $$Из последнего выражения более-менее понятно, что вероятность $\frac{1}{2}$ достигается при $n \approx \sqrt{d}$ и в этой точке изменяется очень быстро.
Второе доказательство (для любителей теорвера). Введем $\frac{n(n-1)}{2}$ индикаторов — по одному для каждой пары людей $(i, j)$ — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна $\frac{1}{d}$.
Обозначим за $X$ число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть $\frac{n (n-1)}{2} \cdot \frac{1}{d}$.
Отсюда понятно, что если $d = \Theta(n^2)$, то ожидание равно константе, а если $d$ асимптотически больше или меньше, то $X$ стремится нулю или бесконечности соответственно.
Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.
Бонус: «мета-задача»
Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.
«Решите» задачу.