Iremia's blog

Why does just changing the base in hashing gets accepted?
By Iremia, 3 years ago, In English

I was trying to solve the problem 1200E - Compress Words using polynomial hashing , but the solution failed on test 136.

First I was using 257 as the base. Here is the submission : 117819925 .

Then I just changes the base to 311 and it got accepted. Here is the accepted one : 117820736 .

As you can see , I have only changed the base (on 7 th line in the submissions) and nothing else. Please could someone help me out and tell me whats wrong?

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

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

Because Siberian hacked msatskevich (submission: 58615000), who had also used 257 as a base and the same primes as moduli, making sure that a collision would occur when the strings are hashed with that base and those primes. That hack got added to the test set, and now everyone who uses this hash will fail. But luckily to you, no one used 311 as a base.

In a contest with hacks, always randomize the base (and don't use rand, and seed the RNG with a precise time). It is easy to write a test that will fail for a particular base/modulo, but you can't do that if you don't know and can't guess the base. (I'm not a veteran hacker, smarter people can probably give you more tips).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not a dfa player but...

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Actually randomly generating strings is enough to hack a particular seed and 2 modulos, because if you generate $$$O(\sqrt{p_{1}p_{2}})$$$ strings a collision will happen w.h.p. by birthday paradox.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But in that case, you can use larger primes, like maybe $$$998\ 244\ 353$$$ and $$$1\ 000\ 000\ 007$$$, and calculate it mod $$$1\ 000\ 000\ 009$$$. Maybe that could cause problems because there's $$$10^9+7$$$ and $$$10^9+9$$$, but you could pick some other large prime instead.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, if you choose 3 large primes it will simply take too much time to create a collision.

        → Reply