taratam's blog

Timus — 1989
By taratam, 11 years ago, In English

Can someone explain me the idea of the solution of 1989 task from a last timus — > http://acm.timus.ru/problem.aspx?space=1&num=1989 ?

  • Vote: I like it
  • -9
  • Vote: I do not like it

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

It can be solved using hash + RSQ — Range Sum Query structure (or fenvick tree, or segment tree)
Suppose we have an array b[0..n — 1]. b[i] = a[i] * (m^i) mod P.
hash for substring [L..R] is (sum b[L] + b[L + 1] + ... B[R]) * m^(n — R) mod P
All you need is fast data structure to perform queries of two types:
1. add value x to cell b[i]
2. find sum of values b[L] + b[L + 1] + ... + b[R] (or b[0] + b[1] + ... + b[k] in case of fenvick tree — Sum[L, R] == Sum[0, R] — Sum[0, L — 1])

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

    TL is only 0.5 sec. It can be to slow solution...

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

      I used SQRT-decomposition instead of RSQ and 2 queries for getting F(l,r) (as F(1,r)-F(1,l-1)) instead of 1, and it works in 0.265. So it looks like there will be no problems with TL while using RSQ.

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

        what is your hash function? had you used % operation?

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

          Polinomial hash modulo 2^64.

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

            I have got accepted using 2 RSQ queries and hash modulo 10^9 + 9

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

              what do you mean by "2 RSQ queries "? you used two hash functions in attempts to avoid hash collisions?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it +2 Vote: I do not like it

                No. The first RSQ is used to calc hash sum: h1 = s[L] * x^L + s[L + 1] * x^(L + 1) + ... + s[R] * x^R. The second one is used to calc hash sum of reversed string: h2 = s[L] * x^(n — L) + ... + s[R] * x^(n — R). Are substrings equal = (h1 * x^(n — R) == h2 * x^R)

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

                  If the first hash sum is s[1] * x^1 + s[2] * x ^ 2 + s[3] * x ^ 3 + s[4] * x^4 and reversed hash sum s[1] * x^4 + s[2] * x^3 + s[3] * x^2 + s[4] * x^1. Your idea is equal x^i from first hash sum and from reversed hash sum? Example if we want to check if [2;4] is palindrome — the first hash sum is s[2]*x^2 + s[3]*x^3 + s[4]*x^4 and reversed s[2]*x^3+s[3]*x^2+s[4]*x^1 and if we multiple the first sum with x^(n-r) and reversed x^r we will have: first hash sum = s[2]*x^2 + s[3]*x^3 + s[4]*x^4; reversed hash sum = s[2]*x^7 + s[3]*x^6 + s[4]*x^5;

                  and the first sum is not equal to reversed but it could be equal... Is there any wrong in your formula or i miss something?

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

                  you are right, there was a bug. h1 * x^(n — R) == h2 * x^L. The main idea is to make higher power of X equal for S1 and S2

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

                  also your comment contains a bug too. " the first hash sum is s[2]*x^2 + s[3]*x^3 + s[4]*x^4 and reversed s[2]*x^2+s[3]*x^1+s[4]*x^0 "

                  → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Prepare to rejudge

            → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it +13 Vote: I do not like it

        Tried to solve this problem with SQRT-decomposition, but whatever i did I got TLE. Then, I implemented it with binary tree and AC =) Tree-implementation is way smaller (less code) and even simpler.

        P.S. and faster =)

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

    How you using the sum to know if [L;R] is palindrome or not?

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

    It is great solution.

    → Reply