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 ?
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 ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
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])
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[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?
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[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 "
Prepare to rejudge
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?
It is great solution.