PROBLEM LINK:Author: Ankit Srivastava PREREQUISITES:String processing, string polynomial hashing PROBLEM:You are given a string $S$, and you have to answer $Q$ queries. Each query consists of four integers $(i,j,k,l)$, and you need to tell whether the substring from the $k$th position to the $l$th position is a palindrome assuming the substring from the $i$th position to the $j$th position is reversed temporarily (i.e. reversals are only applied per query and do not persist for further queries). QUICK EXPLANATION:Fix a (prime) modulus $M$ (preferably between $10^9$ and $2\cdot 10^9$), and a base $B$ (preferably a generator modulo $M$) and define the polynomial hash of the string $S = S_0S_1\cdots S_{n1}$ as the following: $$\text{hash}(S) = \left(\sum_{i=0}^{n1} H[S_i]B^i\right) \bmod M$$ where $H[c]$ is some fixed value from $0$ to $M1$ assigned to $c$. If $M$ and $B$ are chosen well, two strings $S$ and $T$ are equal if and only if $\text{hash}(S) = \text{hash}(T)$ with high probability, and $S$ is a palindrome iff $\text{hash}(S) = \text{hash}(S^R)$ with high probability ($S^R$ is the reversal of $S$). If we are given two strings $S$, $T$ and their hashes, then the hash of $ST$ (their concatenation) can easily be computed in $O(1)$ time (assuming we have precomputed the powers of $B$). Preprocess $S$ so that we can compute the polynomial hash of any substring and reversal of any substring in $O(1)$ time. Next, to answer the query $(i,j,k,l)$, first check if $[k,l]$ intersects with $[i,j]$. If not, we can simply compute the hash of $S[k,l]$ and its reverse. Otherwise, split $[k,l]$ into three parts, where the middle part is contained completely in $[i,j]$. The hashes of the three parts (and their reverses) can be computed separately (with the middle one requiring special care), and can be concatenated in $O(1)$ time and compared. If the hash of the string and its reverse match, then the answer is "Yes", otherwise it is "No". EXPLANATION:When faced with a problem, there are a couple of helpful general tips and strategies that might help you solve it:
There are times when these tips do not apply, and those cases usually require a lot more thinking and thus are usually more interesting. But let's try to apply these strategies in the problem at hand. Solve a simpler versionHow can we simplify the problem? Well, of course we can reduce the bounds of $S$ and $Q$ to, say, $\le 10^3$, but in that case the answer is easily bruteforceable, so it doesn't get us closer to a fast solution. Well, we can simplify the problem by removing the "reversal" operation for each query, i.e. each query consists of two integers $(k,l)$, and you need to tell whether the substring from the $k$th position to the $l$th position is a palindrome. (You can view this simplified problem as a special case of the original problem with $i = j = 1$, for example) Now this simplification is more interesting :) In this case, one can apply standard palindrome algorithms like Manacher's algorithm to determine the longest palindrome centered at each position. This takes $O(S)$ preprocessing and $O(1)$ query time. However, this solution doesn't adapt well once we add in the reversal operations, so let's try to find another solution. Use a standard algorithmAt this point, we try to find what else can be done to check for palindromes. Well, what else are standard algorithms for this task? Hashing, of course! In fact, in many occasions one might prefer a hashing algorithm instead of Manacher's algorithm because it's more flexible, and easier to implement (whereas Manacher's algorithm can be tricky to implement, and is not as flexible). A string is palindromic if and only if it is equal to its reversal. However, the reversal of any substring of a string $U$ is a specific substring of the reversal of $U$. In more detail, if we denote the reversal of a string $S$ by $S^R$, then we're saying that if $U[i..j]$ is a substring, then $U[i..j]^R = U^R[N+1j..N+1i]$, where $N$ is the length of $U$. Therefore, we have reduced a query into a case of comparing whether substrings of two strings are equal. But substring comparisons can be done quickly using polynomial hashing! Polynomial HashingA hash is simply a function that maps an object of an arbitrary size (such as a string) into an value of fixed size (such as a bounded integer). There will inevitably be pairs of objects that will be mapped to the same value (in fact, infinitely many of them). We call a situation where two different objects are mapped to the same hash value a collision. Collisions are inevitable, however we desire hash functions such that it is "random" enough so that for any string we will hash, it will be assigned a hash value with equal "probability" among all possible hash values, and that it is not particularly easy to generate different strings with the same hash value. One application of hash values is in comparing strings: If our hash function is good enough, then two different strings have hashes with high "probability". Let's be a bit more specific. Suppose that our hash function maps strings to integers from $0$ to $M1$. Suppose that we have two different strings $(S,T)$. If we assume that the hash function is "random" enough, then the "probability" that $S$ and $T$ have different hashes is $\approx 1  1/M$, which is pretty close to $1$ assuming $M$ is large. If we want to compare $K$ pairs of different strings $(S_1,T_1), \ldots (S_K,T_K)$, then the probability that every pair have different hashes is $\approx (1  1/M)^K$. In our case, we will need to compare $K \approx 10^5$ pairs of strings, so if we choose $M$ to be around $10^9$, then the probability that no collision will occur is approximately $(1  1/10^9)^{10^5} \approx .9999$. Therefore, our chances of succeeding are pretty high! One common hash function is the polynomial hash. To compute polynomial hashes, we first fix two integers $M$ and $B$. Also, for every character $c$ alphabet, we assign a fixed value $H[c]$ (for example, the ASCII value of $c$). Then the polynomial hash of the string $S = S_0S_1\cdots S_{n1}$ is the following: $$\text{hash}(S) = \left(\sum_{i=0}^{n1} H[S_i]B^i\right) \bmod M$$ Clearly the result is a number in $[0,M1)$, but to minimize potential easy "collisions", we ensure that $M$ is prime, and that the order of $B$ modulo $M$ is reasonably large. Why did we choose the polynomial hash? Because it has other advantages that will be useful in our case:
This is great, because this gives us an $O(1)$time algorithm to answer our query: preprocess the string $S$ and its reversal $S^R$ as above, and simply check if the hashes of $S[k..l]$ and $S[k..l]^R = S^R[N+1l..N+1k]$ are equal! The overall algorithm runs in $O(S + Q)$. Solving the problem with reversalsNow, we go back to the original problem, where each query has a reversal operation. Let's try to answer the query $(i,j,k,l)$, where the substring $S[i..j]$ is reversed temporarily. Our goal is to be able to compute hashes of substrings assuming that $S[i..j]$ has been reversed. Let's handle the simple cases first:
Therefore, we only have two remaining cases to handle:
But in these cases, we can split the string $S[k..l]$ into at most three parts, where each part is either completely contained in $S[i..j]$, or completely outside. We have just described above how compute the hashes of each of the parts quickly, and we can compute the hash of the concatenation of two strings quickly (using the identity in the previous part). Therefore, we now have an algorithm to compute the hash of any substring $S[k..l]$ assuming some substring $S[i..j]$ is reversed temporarily! Since we only compute hashes of a fixed, bounded number of parts, this operation takes $O(1)$. Since we can now compute hashes of substrings even when some substring is temporarily reversed, we can now answer queries $(i,j,k,l)$ in $O(1)$ time! Further readingsHere are some other links about polynomial hashing that might be useful to you: Time Complexity:$O(S + Q)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 12 Jun '15, 05:46

Answer is hidden as author is suspended. Click here to view.
answered 24 Jun '15, 15:19

Can somebody please help me find out where this solution is giving WA. I have tested it on many cases but can't find out why it gives WA. I have used the exact technique as in the editorial. Link: link text answered 13 Jun '15, 03:20

I thought of a different way, but was not able to implement it in time. What I thought was to do kind of Countsort on the string S and instead of frequencies ..remember the positions of occurrence in a 2D array. Done in O(S) time. Later for each query, we map the given reversed k to l index to original string's i to j in constant time.Then find out the mid and use binary search on each of the 26 columns of the 2D matrix to find out if the occuring places are mirrored around the fixed middle point in O( Qlog(n)) time at worst. Leading to O(S+Qlog(S)) time complexity .. although little weaker but was easier to think for me..:) answered 13 Jun '15, 03:58

Can you please explain this point "Next, if [k,l] is completely contained in [i,j], then a simple adjustment can be done: The hash of S[k..l] in the updated string is just the hash of SR[i+j−l..i+j−k]" ??
link
This answer is marked "community wiki".
answered 22 Jun '15, 20:17
2
I modified the formula because it was incorrect, but the idea used is similar. Now it's $S^R[N+1ij+k,N+1ij+l]$. Suppose $S$ is
Note that $[N+1ij+k,N+1ij+l]$ = $[5,7]$.
(22 Jun '15, 21:59)

Can you please do something about the broken solution links @admin. Also, does anyone know what M and B values we should use ? answered 03 Feb, 20:06
