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

Автор Safrout, 10 лет назад, По-английски

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.

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

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

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

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

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

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

        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.

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

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

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

            Then what should I do. I just followed that editorial

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

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

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

                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.

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

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

                I really have a problem with choosing the primes.

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

                  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]".

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

                  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.

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

    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.