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 ?

Before contest

Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1)

09:46:04

Register now »

Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1)

09:46:04

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3627 |

4 | ksun48 | 3547 |

5 | Miracle03 | 3480 |

6 | maroonrk | 3463 |

7 | ecnerwala | 3400 |

8 | peehs_moorhsum | 3384 |

9 | sunset | 3338 |

10 | Um_nik | 3303 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 209 |

2 | Um_nik | 197 |

3 | YouKn0wWho | 192 |

4 | Errichto | 183 |

5 | sus | 181 |

5 | awoo | 181 |

7 | tourist | 175 |

8 | SecondThread | 172 |

9 | -is-this-fft- | 171 |

10 | Radewoosh | 170 |

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 ?

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2021 04:18:57 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.