Блог пользователя Not-Afraid

Автор Not-Afraid, история, 5 лет назад, По-английски

I was solving this problem from CSES. I used modulo $$$2$$$31-1 and was using % operator while calculating hash. It took $$$540ms$$$. Then i tried using unsigned int for calculating hash which implicitly uses modulo $$$2$$$32 if the calculation overflows or underflows and the runtime reduced to 240ms. So, i want to know if i can use my Rolling hash with unsigned int(and is it safe to use) in CF rounds(because i am always afraid of getting hacked while using Rolling Hash).
I uses Rolling Hash more often than string algorithms(if problem can be solved by Rolling hash). Even i use Rolling Hash + binary search to find longest palindromic substring because i don't really understand Manacher's Algorithms.
So, can anyone hack my solution or tell me how much probability this hash has of being hacked during a CF round?

Solution using $$$mod$$$ = $$$2$$$32.
Solution using $$$mod$$$ = $$$2$$$31-1.

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

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

Since you are using randomization it is very hard to hack the solution with $$$mod=2^{31}-1$$$

But the solution with $$$mod=2^{32}$$$ can be hacked very easily. A countercase of length $$$2048$$$ can be generated which will work on all bases simultaneously. Simple Verdict: Do not use hash with overflow.

Zlobober has described how you can generate the anti-hash test in his blog

(He has described it for $$$mod=2^{64}$$$ but it is obvious that if 2 strings are congruent modulo $$$2^{64}$$$ they are also congruent modulo $$$2^{32}$$$.)

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

    Oh, now i see my solution's (with $$$mod$$$ = $$$2$$$32) verdict changed from AC to WA on Cses.
    Thank you for your response. I got your point.

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

    can we do this question using KMP?

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

      Yes, it is a possible to solve this using KMP:

      Link to code: https://cses.fi/paste/91785ee2b5f0dd262517f4/

      HINT:

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

      You can use Z-function also.