### taratam's blog

By taratam, 8 years ago, 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 ? Comments (15)
 » 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 + b + ... + b[k] in case of fenvick tree — Sum[L, R] == Sum[0, R] — Sum[0, L — 1])
•  » » TL is only 0.5 sec. It can be to slow solution...
•  » » » 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.
•  » » » » what is your hash function? had you used % operation?
•  » » » » » Polinomial hash modulo 2^64.
•  » » » » » » I have got accepted using 2 RSQ queries and hash modulo 10^9 + 9
•  » » » » » » » what do you mean by "2 RSQ queries "? you used two hash functions in attempts to avoid hash collisions?
•  » » » » » » » » 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)
•  » » » » » » » » » If the first hash sum is s * x^1 + s * x ^ 2 + s * x ^ 3 + s * x^4 and reversed hash sum s * x^4 + s * x^3 + s * x^2 + s * 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*x^2 + s*x^3 + s*x^4 and reversed s*x^3+s*x^2+s*x^1 and if we multiple the first sum with x^(n-r) and reversed x^r we will have: first hash sum = s*x^2 + s*x^3 + s*x^4; reversed hash sum = s*x^7 + s*x^6 + s*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?
•  » » » » » » » » » 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
•  » » » » » » » » » also your comment contains a bug too. " the first hash sum is s*x^2 + s*x^3 + s*x^4 and reversed s*x^2+s*x^1+s*x^0 "
•  » » » » » » Prepare to rejudge
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   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 =)
•  » » How you using the sum to know if [L;R] is palindrome or not?
•  » » 8 years ago, # ^ | ← Rev. 2 →   It is great solution.