ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1792. Hamming Code

My solution
Posted by Pearl 4 Oct 2018 04:27
First, let give the bits some names, I put them inside the parentheses:
Petal 1 (p1) = II (c2) + III (c3) + IV (c4)
Petal 2 (p2) = I (c1) + III (c3) + IV (c4)
Petal 3 (p3) = I (c1) + II (c2) + IV (c4)

As p1, p2 and p3 are created from c1, c2, c3, c4, we check each change in c1, c2, c3, c4:
When c1 change: p2 and p3 won't match the value calculated using the formular above (i.e: c1 + c3 + c4 != p2 and c1 + c2 + c4 != p3)
When c2 change: p1 and p3 will go wrong
When c3 change: p1 and p2 will go wrong
As c4 contribute to the value of all three petals, if it is changed then p1, p2 and p3 will all go wrong.

In short:
Calculate ep1, ep2 and ep3 from the first 4 bits (the e in ep stand for expected), then compare them with the given p1, p2 and p3:
All three pairs do not match: c4 is changed
p1 and p2 do not match:       c3 is changed
p1 and p3 do not match:       c2 is changed
p2 and p3 do not match:       c1 is changed
Only p1 not match:            p1 is changed
Only p2 not match:            p2 is changed
Only p3 not match:            p3 is changed