Safrout's blog

By Safrout, 9 years ago, In English

I am trying to solve this problem for a long time https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=588&page=show_problem&problem=4450

obviously the brute force will TLE, any O(n^2) algorithm will TLE and any use of suffix array will also TLE.

So what I need actually is to find a way to hash the string from left and right and this requires a hashing function that hashes a string as it hashes his reverse.

Is this possible or there is another way to solve the problem.

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

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

    It's either the hashing function is wrong or there is a bug in my code http://ideone.com/d1ADUG

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

      your hasing function seems wrong and careful with integer overflow or big-integer because it's slow.

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

        I didn't get it because even if I do change the the prime number to 3 or 73 or any small prime the code still fails.

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

          even if you change to smallest prime = 2; 2^10000 is also very big integer.

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

            Then what should I do. I just followed that editorial

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

              Of course, that editorial exclude modulo operation ;) You can use modulo to avoid large integer.

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

                Actually I know this. But I usually have problems in how to choose the prime that I will multiply with and the prime that I will take it's modulo.

                Actually 1000000007 and 1000000009 will fail because they are not far from each other.

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

                refresh the code link. I have chosen 73 and 1000000009.

                I really have a problem with choosing the primes.

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

                  well, because it's hash function, you can try any prime combination, and see if the code getting AC or not. and btw, there is a mistake in that editorial, "L = L * P + S[i]" should be "L = L * x + S[i]".

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

                  I believe there is a problem in the function itself.

                  Because when we enter a string like paspas it gives 1 (Actually 3 characters will not lead to any overflows or big numbers) when it should give 2.

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

    Got it accepted by the help of one of my university coaches. There is a bug in the editorial. L should be multiplied with x not p.