Блог пользователя Iremia

Автор Iremia, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    not a dfa player but...

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.