snsokolov's blog

Modulo based hacking
By snsokolov, 9 years ago, In English

For the problem 567E - President and Roads

I think I finally got the idea what is the "modulo based hacking" is about (thread http://mirror.codeforces.com/blog/entry/19590?#comment-244040)

When counting number of ways in a graph within the given ranges we can easily get out of bounds of long long data type. Therefore we need some way to be able to count and compare numbers larger than ll. Ideally we need a full stack BigInt support, but what if we can find something simpler than that. The naive approach here is to pick some large prime number M and perform all operations modulo M. Unfortunately this approach is not working for all possible inputs and leads to collisions, since the two different numbers may still match and the solution can be exploited — i.e. modulo based hacking.

Here is the list of less exploitable approaches:

  1. Use "Modulo Hash" — i.e. use more than 1 large prime number when counting and compare numbers. Match is when all modulus are equal. see 12361537

  2. Use random prime number each time, so hacker doesn't know it ahead of time, see 12362068 ^)))

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

You can beat (1) like this: suppose the number of paths in graph A is divisible by M1 and the number of paths in graph B is divisible by M2. You can just chain A and B together and then all subsequent vertices will have 0 ways mod M1 and mod M2.

→ Reply