ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
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