Magic Contest

For a binary string $X$ of length $m$, consider the checksum

$$\sum_{i=1}^{m} iX_i\pmod{m+1}.$$

The strings whose checksum is $0$ form a Varshamov--Tenengolts code that corrects one insertion or deletion.

For an original length $N$, choose the smallest $r$ satisfying $2^r\geq N+r+1$, and set $$. Reserve positions for check bits and place the bits of into all remaining positions in order.

Let $a$ be the checksum contributed by the data bits. Choose the integer $q=(-a)\bmod(m+1)$ with $0\leq q\leq m$. Since , its binary representation fits exactly in the reserved positions. The completed string has checksum .

For $3\leq N\leq 200\,000$, we have $r\leq 18$ and $m\leq 2N$. For $$, repeat every bit twice instead. This short repetition code also corrects one insertion. Alice therefore always satisfies the length bound, and for every , giving points.

Bob receives a string of length $m+1$. For every possible deletion position $j$, compute the checksum after deleting that character and find a position that yields checksum $0$. The single-insertion-correcting property makes the recovered codeword unique. A weighted sum and suffix counts of 1 compute all candidate checksums in total $O(m)$ time.

After recovering the codeword, collect the characters at positions that are not powers of two. They form the original string $S$.

Each execution takes $O(\sum N_i)$ time and $O(\max N_i)$ auxiliary space. The largest integer needed by the checksum calculation is , which fits in a signed 64-bit integer.

Solution written by GPT5