aajjbb's blog

Rolling Hash on Live Archive — Pasti Pas!
By aajjbb, 10 years ago, In English

Hi.

I'm trying to solve this problem from Live Archive Link.

I'm receiving Wrong Answer and the test data isn't available online. To briefly explain my solution, I pre-process the hashing function for the whole string, and them take the hash of the slices I want from this array and apply it's inverse module to normalize the prime powers. Is there something wrong with this approach ?

My Code

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's my AC solution: http://ideone.com/6AVLRk

You can generate random inputs and compare with your output.

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

    What's actually happening in lines 13 and 14. I've never seen such a hashing strategy, could you explain more about it or give some sources about this technique ?

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

      Actually same as usual hashing. And since we look for palindrome, just find whether prefix and suffix match or not

      Here's the official editorial : link

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

        I got the idea of prefix and suffix hashing, but I still got the idea on how this code works. Even in the editorial it isn't clear. Do you have more information on 'suffix hash' calculation ?

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

      Line 13 — Forward hashing (left to right).

      Line 14 — Reverse hashing (right to left).

      Think about how you can convert the string "1234" in base 10 to integer, traversing from left to right and from right to left.

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

    By the way, I submitted this solution for test purposes and it returns a WA.

    → Reply