해싱을 사용하는 알고리즘에는 한 가지 불쾌한 단점이 있습니다. 바로 비결정성입니다. 무한히 많은 예제를 생성하면 언젠가는 운이 나빠서 프로그램이 잘못 동작하게 됩니다. CodeForces에서는 해싱을 사용하는 풀이가 해킹당하는 일도 가끔 있습니다. 특정 풀이를 겨냥한 테스트를 오프라인에서 미리 생성할 수 있기 때문입니다. 이를 어떻게 하는지에 대한 가이드까지 있습니다.
두 해시가 일치해서는 안 되는데 일치하는 사건을 충돌(collision)이라고 합니다. 서로 다른 부분 문자열의 개수를 구하는 문제를 푼다고 합시다. 이때 우리는 set에 구간 $[0, m)$의 서로 다른 무작위 값 $O(n^2)$개를 추가합니다. 충돌이 일어나면 어떤 문자열을 세지 못하게 되어 WA를 받게 된다는 것은 자명합니다. 이런 일을 걱정하지 않으려면 $m$을 얼마나 크게 잡아야 합니까?
#상수 선택
경험 법칙: $n$개의 서로 다른 해시를 저장해야 한다면, 안전한 모듈러는 $10 \cdot n^2$ 정도 크기의 수입니다. 근거는 생일 역설을 참고하십시오.
이런 모듈러를 항상 하나만 고를 수 있는 것은 아닙니다. 모듈러가 너무 크면 곱셈을 할 때 오버플로가 발생하기 때문입니다. 대신 모듈러를 두 개 또는 세 개까지 사용하여 여러 해시를 병렬로 계산할 수 있습니다.
$2^{64}$을 “모듈러"로 사용할 수도 있습니다. 여기에는 몇 가지 장점이 있습니다:
- 이 모듈은 충분히 크므로 두 번째 모듈은 전혀 필요하지 않습니다.
- 이 모듈러를 사용하면 오버플로에 대해 전혀 신경 쓸 필요가 없습니다. 모든 값을
unsigned long long에 저장하면 오버플로가 발생할 때 프로세서가 자동으로 나머지 연산을 수행합니다. - 이 모듈을 사용하면 해싱이 훨씬 빨라집니다. 오버플로가 프로세서 수준에서 일어나므로 시간이 오래 걸리는
%연산을 수행하지 않아도 되기 때문입니다.
이 모듈은 이를 노린 테스트가 고안되기 전까지는 아무런 문제가 없었습니다. 하지만 이 테스트가 모든 대회에 추가되는 것은 결코 아니라는 점을 염두에 두십시오.
반면 $k$를 선택할 때의 제약은 그다지 엄격하지 않습니다:
- 이 값은 사전 크기보다 약간 커야 합니다. 그렇지 않으면 인접한 두 글자를 바꾸어 충돌을 일으킬 수 있습니다.
- 이 값은 모듈러와 서로소여야 합니다. 그렇지 않으면 어느 순간 모든 값이 0이 될 수 있습니다.
중요한 것은 테스트를 만드는 사람이 $k$와 모듈러의 값을 모르게 하는 것입니다.
#생일 역설
23명 이상으로 이루어진 집단에서 적어도 두 사람의 생일이 같을 확률은 50%를 넘습니다.
더 일반적인 명제는 다음과 같습니다. 어떤 두 수가 일치하려면 멀티셋에 1부터 n까지의 무작위 수를 $\Theta(\sqrt{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)$마다 하나씩이며, 각 지시 변수는 두 사람의 생일이 같으면 1이 됩니다. 각 지시 변수의 기댓값과 확률은 $\frac{1}{d}$입니다.
일치한 생일의 수를 $X$라고 합시다. 이 값의 기댓값은 이 지시 변수들의 기댓값의 합과 같으며, 곧 $\frac{n (n-1)}{2} \cdot \frac{1}{d}$입니다.
이로부터 $d = \Theta(n^2)$이면 기댓값이 상수가 되고, $d$가 점근적으로 더 크거나 더 작으면 $X$는 각각 0 또는 무한대로 수렴한다는 것을 알 수 있습니다.
참고: 엄밀히 말하면, 이로부터 확률 역시 0과 1로 수렴한다는 사실이 바로 도출되지는 않습니다.
#보너스: «메타 문제»
임의의 문자열이 주어지며, 이 문자열로부터 문제 출제자만 아는 방식으로 yes/no 답이 생성됩니다. 문제에는 테스트가 100개 있습니다. 여러분에게는 풀이를 제출할 기회가 20번 있습니다. 피드백으로는 각 테스트에 대한 판정 결과를 볼 수 있습니다. 판정은 OK(답이 일치함)와 WA, 단 두 가지뿐입니다. 0으로 나누거나 테라바이트 단위의 메모리를 할당하는 등의 시도도 WA로 간주됩니다.
문제를 「풀어」 보십시오.