TACHEMIS - Editorial

I cannot see that straightforward application. Do you “decompress” the string in memory? I think no, it’s too big. So what about compressed string

A3
B3
C2
B2
A3

In compressed string the substring ABCBA is palindrome, while it’s not valid palindrome in decompressed string…

I used hashing + binary search in order to find the longest palindrome centered at each of the K groups of identical characters. This gave me an O(K*log(K)) time complexity instead of O(K) (as is the case with Manacher’s algorithm), but I personally prefer to use hashing whenever possible, because it’s a much more general technique (applicable to a wider range of problems) and it’s very easy to implement.

10 Likes

can anybody please identify why my code got SIGABRT error
http://www.codechef.com/viewsolution/2396428

I wrote a very naive solution, which as I now see should most probably get TLE. But for some reason it gets WA. It works fine on any tests I can think of. Can anybody help find the reason for this WA? http://www.codechef.com/viewsolution/2397315

http://www.codechef.com/viewsolution/2396623
plz have a look…
i know its not good enough but why wrong answer?

I would like to clarify about somethings. I know that we have to calculate the number of palindromic substrings centered at each letter. Here is what I did but it still gives me wrong answer.

Assume A[i] is a pair or char and long long after adding (#, 0) between the letters.

1- For each A[i] init P[i] = 0. (This means am not using the symmetry property)

2- init V[i] = A[i].Y * (A[i].Y + 1) / 2;

3- while I can still expand this palindrome I wrote this code:
while(A[i - P[i] - 1].X == A[i + P[i] + 1].X) {

        P[i]++;

        V[i] += min(A[i - P[i] - 1].Y, A[i + P[i] + 1].Y);

        if(A[i - P[i] - 1].Y != A[i + P[i] + 1].Y) {
            break;
        }
    }

4- When manacher’s algorithm is over I add all the values of V[i] to get the final result. What is wrong with this way? Why is it giving me a wrong answer. If you’d like to have a look at the full code here it is: CodeChef: Practical coding for everyone

I tried my code with thousands of different inputs and it always gave the exact same answer as successful submissions, but I get WA. I wonder if someone can point me to any test case where my code fails. CodeChef: Practical coding for everyone

As per my understanding, we can solve this problem by writing a c program trying to find longest palindrome string centered at a character. Let the center character is ‘x’, then we will move in both direction of x and check if this sub string or not. IF we find that it is not a palindrome string then we can stop further scan and jump to next adjacent character in the given string. I donno how to write correct program for this … but this algorithm looks good to me.

Two ‘characters’ of compressed string are equal if the corresponding (char, int) pairs are equal. No need to explicitly decompress the string, just do calculations smartly.

1 Like

I tried the same, but got WA for unknown reason. Going through your submission. :slight_smile:

In your solution, you calculate powers of 1e9+7 upto 200000 in an unsigned long long and also do the hash calculations in ULL. How is it that the ‘overflowed’ values don’t give an error and the algorithm still works ?

@sanchit_h because unsigned long long values automatically wraps around 2^64 on overflow.

1 Like

Oh. Thanks! Also, do you know why we need to a multiply the RHS value by a certain power(specifically 4*mid-2) while calculating the difference in the forward and reverse hash ?

Got my error. my hash function wasn’t good enough. using @mugurelionut’s hash func, got AC :confused:
@sanchit_h Haven’t seen that part of his code thoroughly. But I can guess that it is due to his nature of hash function. See my code if it makes any better for you.

@sanchit_h: My hash function considers that we have a sequence of 2N values: character1, count1, character2, count2, …, characterN, countN. That’s why I needed powers of P up to 2N basically (and not only up to N). Then, when computing the direct hash value for a substring (in my solution from i-mid+1 to i+mid-1) we need the “prefix” hash up to i+mid-1 from which we need to subtract the contribution of the “prefix” hash up to i-mid. But this contribution appears multiplied by P^(2 * length), where length=2*mid-1 (thus, 2 * length = 4 * mid - 2). The hash for the reverse string is similar.

2 Likes

My O(Klog(K)) solution got tle. Then, i solved it with manacher. May be because of using mods :frowning:

Change this :"(n*(n+1))/2" to “((long long) n*(n+1))/2” and you will get TLE.

1 Like

Your code would require O(10^9) memory, because it is trying to “expand” the compressed string.

1 Like

One reason is that arr is not valid after putting in all those '#'es. You should have updated arr as well.

We cannot help you to debug your code, please only ask something related to the solution in the editorial!