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

Data Transmission

Back to problem

Editorial

Use a length-7 Hamming code, numbering positions from 1 on the left. Put the four original bits in positions 3,5,6,73,5,6,73,5,6,7 in order.

Let xxx be the XOR of the position numbers among those four positions whose bits are 1. Write x=(b2b1b0)2x=(b_2b_1b_0)_2x=(b2​b1​b0​)2​ and place b0,b1,b2b_0,b_1,b_2b0​,b1​,b2​ at positions 1,2,41,2,41,2,4, respectively. The XOR of all positions containing 1 is then x⊕x=0x\oplus x=0x⊕x=0.

Suppose position kkk is flipped. XORing the positions containing 1 in the received string adds or removes exactly one occurrence of kkk, so the result is exactly kkk. Flip that bit again and read positions 3,5,6,73,5,6,73,5,6,7. Because exactly one bit is flipped, the received syndrome for this strategy is always between 1 and 7.

The transmitted length is always 7, within the limit. The same procedure handles errors in parity positions 1,2,4 and data positions 3,5,6,7.

A naive decoder may encode all 16 original strings and find the codeword at distance exactly one from the received string. Distinct codewords have distance at least 3: a distance of one contradicts their equal zero syndromes, while a distance of two would require two distinct position numbers to XOR to zero. Thus the candidate is unique. Since the input size is fixed, this naive solution also passes the full task.

The main solution takes O(1)O(1)O(1) time and auxiliary space. The naive decoder makes at most 16⋅7=11216\cdot7=11216⋅7=112 bit comparisons, also O(1)O(1)O(1). Position XOR values are at most 7, original numeric values at most 15, and an 8-bit mask at most 255. All arithmetic fits signed 64-bit integers.

Solution written by GPT6