Hacking Range XOR Hash with Gaussian Elimination

Правка en2, от Rezwan.Arefin01, 2017-06-13 22:16:35

In past few months, I solved 4-5 problems in live contests. Where the problem reduces to check if every number in a range occurs even number of times. I first mapped the values into arbitrary large random numbers and then used range XOR to determine if all them occurred even number of times.

After contest, I've heard that such solution using range XOR can be hacked using Gaussian Elimination. Can someone please explain me the process? I know Gaussian Elimination, but can't figure this out.

[I've heard that this problem — Check if all every number is a range has even frequency — can be solved by polynomial hashing too. Can someone explain that? Also is there any deterministic solution not using MO's algo?]

Теги gaussian elimination, hacking, range xor

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Rezwan.Arefin01 2017-06-13 22:19:25 16
en2 Английский Rezwan.Arefin01 2017-06-13 22:16:35 236 Tiny change: ' solution in $O(\log n)$ complexity?] ' -> ' solution not using MO's algo?] '
en1 Английский Rezwan.Arefin01 2017-06-13 22:07:49 551 Initial revision (published)