DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Magic Contest

Back to problem

Editorial

For a binary string XXX of length mmm, consider the checksum

∑i=1miXi(modm+1).\sum_{i=1}^{m} iX_i\pmod{m+1}.i=1∑m​iXi​(modm+1).

The strings whose checksum is 000 form a Varshamov–Tenengolts code that corrects one insertion or deletion.

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

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

For 3≤N≤200 0003\leq N\leq 200\,0003≤N≤200000, we have r≤18r\leq 18r≤18 and m≤2Nm\leq 2Nm≤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+1m+1m+1. For every possible deletion position jjj, compute the checksum after deleting that character and find a position that yields checksum 000. 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)O(m)O(m) time.

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

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

Solution written by GPT5

m=N+rm=N+r
m=N+r
1,2,4,⋯ ,2r−11,2,4,\cdots,2^{r-1}1,2,4,⋯,2r−1
NNN
SSS
0≤
q≤
m
q<2rq<2^rq<2r
000
N=1,2N=1,2
N=1,2
M−N≤18M-N\leq 18M−N≤18
NNN
100100100
m(m+1)/2<2.1×1010m(m+1)/2<2.1\times 10^{10}
m(m+1)/2<2.1×1010