Do Not Believe T's Story

이 문제는 복원할 후보 부분집합들을 미리 정하고, 주어진 집합 $S$에 포함되는 후보 하나의 번호를 보내는 부호화 문제로 볼 수 있다. 첫 번째 실행은 후보를 찾아 번호를 출력하고, 두 번째 실행은 그 번호로부터 원소들을 복원한다. 전체 범위의 크기를 $N=1\,000\,000$, 입력 집합의 크기를 $K=10\,000$이라 하자. 이하에서는 입력값에서 $1$을 빼고 $0,\ldots,N-1$의 정수로 다룬다. 두 실행에서 동일하게 재현할 수 있는 순열 $T=12$개를 준비한다. 구현에서는 같은 배열을 고정된 시드로 차례대로 섞고, 각 결과를 복사하여 저장한다. 각 순열 $f_t$에 대해 $S$의 원소들을 변환하고, 전체 범위를 크기 $B=400$인 버킷으로 나눈다. 버킷 개수는

$$G=\frac NB=2\,500$$

이다. 변환된 값 $y$는 버킷 번호와 버킷 내부 위치

$$b=\left\lfloor\frac yB\right\rfloor,\qquad p=y\bmod B$$

로 나타낼 수 있다. 어떤 버킷에 입력 원소가 $9$개 이상 들어 있다면, 그중 $9$개를 선택하여 전송을 시도한다. 선택한 내부 위치를

$$0\le p_1<p_2<\cdots<p_9<B$$

라 할 때, 조합 순위를

$$r=\sum_{j=1}^{9}\binom{p_j}{j}$$

로 정의한다. 이 식은 $9$개짜리 조합을

$$0,\ldots,L-1,\qquad L=\binom{400}{9} =659\,797\,329\,990\,167\,600$$

에 일대일로 대응시킨다. 순열 번호, 버킷 번호, 조합 순위를 모두 그대로 보내려면 $TG L$개의 코드가 필요하므로 $64$비트 범위를 초과한다. 따라서 각 순열·버킷 쌍에서 전송 가능한 조합을 일부만 선택한다. 먼저 원소 하나를 그대로 전송하는 용도로 $1,\ldots,N$을 예약한다. 나머지 공간을 $TG$개의 순열·버킷 쌍에 나누어 할당하면, 각 쌍에서 사용할 수 있는 코드의 수는

$$A= \left\lfloor \frac{2^{64}-1-N}{TG} \right\rfloor =614\,891\,469\,123\,618$$

이다. 순열 번호가 $t$, 버킷 번호가 $b$일 때

$$u=tG+b$$

로 두 정보를 합친다. 각 $u$에 대해 고정된 시드로 계수 $\alpha_u,\beta_u$를 생성하되,

$$1\le\alpha_u<L,\qquad \gcd(\alpha_u,L)=1,\qquad 0\le\beta_u<L$$

을 만족하도록 한다. 같은 $u$에서는 항상 같은 계수가 생성되므로 계수를 따로 전송할 필요는 없다. 조합 순위 $r$를

$$c=(\alpha_u r+\beta_u)\bmod L$$

로 변환하고, $c<A$인 경우에만 전송한다. 이 변환은 전송 가능한 조합들이 작은 조합 순위에만 몰리는 현상을 줄이기 위해 사용한다. 조건을 만족하는 조합을 찾으면

$$M=N+1+uA+c$$

를 출력한다. 전송값의 범위는

$$N+1\le M\le N+TG A\le2^{64}-1$$

이므로 문제의 조건을 만족한다. 인코더는 순열들을 차례대로 적용하고, 각 버킷에서 가능한 $9$개짜리 조합들을 검사한다. 조합 검사 횟수에는 제한을 두지 않는다. 전송 가능한 조합을 발견하면 즉시 종료하고, 모든 순열과 후보 조합을 확인했는데도 찾지 못했다면 $S$의 원소 하나를 원래 값 그대로 출력한다. 두 번째 실행에서는 $M\le N$이면 원소 하나를 그대로 복원한다. 그렇지 않다면

$$u=\left\lfloor\frac{M-N-1}{A}\right\rfloor,\qquad c=(M-N-1)\bmod A$$

로 정보를 분리하고,

$$t=\left\lfloor\frac uG\right\rfloor,\qquad b=u\bmod G$$

를 구한다. 같은 $u$에서 계수들을 다시 생성하면

$$r=\alpha_u^{-1}(c-\beta_u)\bmod L$$

로 원래 조합 순위를 복원할 수 있다. 여기서 역원은 $A$가 아니라 $L$을 기준으로 계산한다. 조합 순위에서는 $j=9$부터 $1$까지 역순으로 위치를 복원한다. 현재 허용 범위에서

$$\binom{p_j}{j}\le r$$

인 가장 큰 $p_j$를 선택하고, $r$에서 해당 값을 뺀다. 다음 위치는 방금 선택한 위치보다 작은 범위에서 찾는다. 복원한 위치에 버킷의 시작점 $bB$를 더하고 역순열 $f_t^{-1}$을 적용하면 원래 원소들을 얻는다. 따라서 탐색에 성공하면 입력에 포함된 서로 다른 원소 개를, 실패하면 올바른 원소 하나를 복원한다. 성공 확률은 다음과 같이 근사할 수 있다. 공유 순열을 독립적인 균등 무작위 순열로 보고, 조합 순위의 아핀 변환을 균등 무작위 치환으로 근사한다. 특정 버킷에 들어가는 입력 원소의 수를 라 하면

$$\Pr(X=k) = \frac{\binom{B}{k}\binom{N-B}{K-k}} {\binom NK}, \qquad \mathbb E[X]=\frac{KB}{N}=4$$

이다. 버킷에 원소가 $k$개 있으면 검사할 조합은

$$m_k=\binom{k}{9}$$

개이다. $k<9$이면 $m_k=0$으로 둔다. 균등한 무작위 치환 모델에서 이 후보들이 모두 전송 조건을 만족하지 못할 확률은

$$\frac{\binom{L-A}{m_k}}{\binom{L}{m_k}} \approx(1-p)^{m_k}, \qquad p=\frac AL\approx0.00093194$$

이다. 따라서 특정 버킷에서 전송 가능한 조합을 하나 이상 찾을 확률은

$$q\approx \sum_{k=9}^{B} \frac{\binom{B}{k}\binom{N-B}{K-k}}{\binom NK} \left(1-(1-p)^{\binom{k}{9}}\right).$$

이를 수치적으로 계산하면

$$q\approx0.0004094405$$

이다. 버킷 사이의 의존성까지 무시하는 근사를 적용하면, $12$개의 순열에서 모두 실패할 확률은

$$(1-q)^{TG} \approx4.62\times10^{-6}$$

이다. 따라서 케이스 하나에서 $9$개를 복원하는 예상 성공률은 약

$$\boxed{99.99954\%}$$

이다.