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 ?
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 19:20:06 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
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.