Do Not Believe T's Story

This is an encoding problem: agree in advance on a family of candidate subsets, find one contained in the input set $S$, and transmit its identifier. The second execution reconstructs the selected subset from that identifier alone.

Let $N=1\,000\,000$ and $K=10\,000$. Subtract $1$ from every input value, so that the universe is $\{0,\ldots,N-1\}$.

Shared permutations and buckets

Prepare $T=12$ permutations $f_0,\ldots,f_{T-1}$, reproducible in both executions. The implementation initializes with a fixed seed, repeatedly shuffles the same array, and stores a copy after each shuffle. The seed is fixed independently of the input and test data.

For each permutation, map every $x\in S$ to $y=f_t(x)$, and divide the universe into buckets of size $B=400$. There are

$$G=N/B=2\,500$$

buckets. A mapped value is represented by its bucket and its position inside that bucket:

$$b=\left\lfloor y/B\right\rfloor,\qquad p=y\bmod B.$$

If a bucket contains at least $9$ input elements, consider its $9$-element subsets. For sorted positions

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

define the colexicographic combination rank

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

This is a bijection between the $9$-element subsets of a bucket and the integers $0,\ldots,L-1$, where

$$L=\binom{400}{9}=659\,797\,329\,990\,167\,600.$$

Fitting the message into 64 bits

Encoding the permutation, bucket, and unrestricted combination rank would require $TGL$ codes, which exceeds the available range. We therefore allow only some combinations in each permutation--bucket pair.

Reserve messages $1,\ldots,N$ for directly transmitting one original input value. Message $0$ is unused. Allocate the remaining space equally among the $TG$ pairs, with

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

codes per pair. Combine the two indices as $u=tG+b$.

For each $u$, deterministically generate coefficients from a second fixed seed and $u$. Choose

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

The implementation uses SplitMix64 and retries the choice of $\alpha_u$ until it is coprime to $L$. Both executions reproduce the same coefficients, so they need not be transmitted.

Transform a combination rank by

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

This map is invertible modulo $L$. Accept the candidate only when $c<A$, and transmit

$$X=N+1+uA+c.$$

Consequently,

$$N+1\le X\le N+TGA\le2^{64}-1.$$

The invertible affine filter distributes the permitted ranks more broadly than simply accepting the smallest original ranks.

The encoder visits permutations and buckets in order. In each bucket containing $k\ge9$ input elements, it enumerates all $\binom{k}{9}$ subsets if necessary, stopping immediately when one passes the filter. There is no cutoff on the number of combinations examined. If every candidate in all $12$ permutations fails, transmit one element of in its original, one-based form. This is the one-element fallback.

Decoding

For a message produced by the encoder, $1\le X\le N$ identifies the fallback value directly. Otherwise, recover

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

and then

$$t=\left\lfloor u/G\right\rfloor,\qquad b=u\bmod G.$$

Regenerate the coefficients for $u$, and invert the filter:

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

The inverse is taken modulo $L$, not modulo $A$. Normalize the subtraction before multiplying by the inverse.

Unrank the combination in reverse order, from $j=9$ down to $1$. Choose the largest permitted $p_j$ satisfying

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

subtract this binomial coefficient from $r$, and restrict the next position to values smaller than $p_j$. Binary search finds each position. Finally, map each $bB+p_j$ through and add to restore the original numbering.

Invertibility of the rank and affine maps ensures that a successful search reconstructs exactly the selected $9$ distinct input elements. The fallback reconstructs one input element. Thus every reconstructed value belongs to $S$.

Precompute the binomial coefficients up to $\binom{400}{9}$. These coefficients, ranks, and messages fit in unsigned 64-bit integers. Products such as $\alpha_u r+\beta_u$, modular multiplication during decoding, and message construction use intermediates. The extended Euclidean algorithm for the modular inverse uses signed 128-bit intermediates.

Estimated frequency of recovering nine elements

For an estimate, idealize the shared permutations as independent uniform random permutations. Also approximate each affine permutation of combination ranks by a uniform random permutation of all $L$ ranks. The latter is an approximation: the affine family does not contain every permutation of the rank space.

Under the uniform-shuffle model, the number $Y$ of input elements in a particular bucket has the hypergeometric distribution

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

If the bucket contains $k$ elements, it offers $m_k=\binom{k}{9}$ candidate subsets; take for . In the uniform-rank-permutation model, the probability that all candidates fail is

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

Hence the estimated probability that a particular bucket provides an encodable subset is

$$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) \approx0.0004094405.$$

If we additionally ignore dependencies between buckets and trials, the estimated failure probability over all $TG=30\,000$ pairs is

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

giving an estimated nine-element recovery rate of about

$$\boxed{99.99954\%}.$$

This numerical estimate relies on the uniformity and independence approximations above. With fixed seeds, the implementation is deterministic; the estimate is not a worst-case guarantee of recovering nine elements for every valid $S$. When no candidate passes the filter, the encoder uses the valid one-element fallback.