You are not logged in. Please login at www.codechef.com to post your questions!

×

TACHEMIS - Editorial

8
4

Problem Link:

Practice
Contest

Difficulty:

Medium

Pre-requisites:

Manacher’s Algorithm

Problem:

Given a string in "compressed notation"(see problem), find the number of substrings that are palindrome.

Explanation:

The problem was a straightforward application of Manacher’s Algorithm. This Algo was originally proposed to find the longest palindrome in a string. However, for each "center" c, it finds the length of longest palindrome "centered" at c. Therefore, we can use it to find the number of palindromes "centered" at c as well. Handling the fact that strings are given in compressed notation is relatively straightforward.

Many elegant descriptions of Manacher’s Algorithm can be found on internet.

In very short, Manacher’s Algorithm can be written as follows.
1 | int p[N+1], mx = 0, id = 0; 2 | // length of longest palindrome centred at i is 2 * p[i]-1. 3 | for (i = 1; i <= N; i++) { 4 | p[i] = mx > i ? min(p[2 * id-i], mx-i) : 1; 5 | while (s[i + p[i]] == s[i - p[i]]) p[i]++; 6 | if (i + p[i] > mx) { 7 | mx = i + p[i]; 8 | id = i; 9 | } 10| }

Let the compressed string be (c1, k1), (c2, k2), ... (cN, kN).

Assuming reader understands Manacher’s Algorithm, here is how to modify it for this problem:

  • Palindromes that contain only a single character repeated several times can be counted as:

    Σ ki * (ki +1) / 2

  • Palindromes that span over more than 1 contiguous segment of compressed string can be computed by also maintaining an array q, which stores the length of the longest "decompressed" palindrome centred at ith segment.

q[i] = ki-p[i]+1 + ki-p[i]+2 ... + ki + ... ki+p[i]-2 + ki+p[i]-1

There will also be minor changes like:
1. We need not put interleaving '#'es because center of every palindromic substring is the center of some "compressed" segment(unless it fully lies inside a segment).
2. In line no 5, compare the characters as well as the lengths of the segments.
3. If the segments i-p[i] and i+p[i] do not have same lengths, but have the same character, then q[i] would need to adjusted by adding 2*min(ki-p[i], ki+p[i]).

The final Answer is

Σ ki * (ki +1) / 2 + ⌈q[i]/2⌉ - ⌈ki/2⌉

Setter's Solution:

Can be found here

Tester's Solution:

Can be found here

This question is marked "community wiki".

asked 22 Jul '13, 00:01

utkarsh_lath's gravatar image

5★utkarsh_lath ♦♦
255385251
accept rate: 0%

edited 22 Jul '13, 10:19


10

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.

link

answered 22 Jul '13, 00:18

mugurelionut's gravatar image

7★mugurelionut
10.0k266990
accept rate: 19%

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

(22 Jul '13, 00:29) nims116★

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 ?

(22 Jul '13, 00:40) sanchit_h6★
1

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

(22 Jul '13, 00:46) nims116★

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 ?

(22 Jul '13, 00:52) sanchit_h6★

Got my error. my hash function wasn't good enough. using @mugurelionut's hash func, got AC :/ @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.

(22 Jul '13, 01:46) nims116★
2

@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.

(22 Jul '13, 01:57) mugurelionut7★

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

(22 Jul '13, 02:55) bidhan_roy6★

@mugurelionut @nims11 : I have seen hashing being used for string related problems many times, but never understood how its being implemented to solve such problems. Can you provide a brief overview of the concept used in this problem and how hashing is used coupled with a binary search ? (or a link to something similar where this has been explained?)

(22 Jul '13, 12:51) malaykeshav4★

@mugurelionut : hi,could you please explain your approach in detail,how exactly you are applying hashing ?

(22 Jul '13, 14:11) sandeepandey2★
2

@sandeepandey: In this problem hashing is used to check if a substring of the given string is a palindrome. Let's say we have the substring from position i to position j. Then we compute a hash h1 for the substring from i to j and a hash h2 for the reverse substring from j to i. If h1=h2 then we can assume that the string from i to j is a palindrome (of course, we could be wrong, but it very unlikely if the hash function is good). The important part is to be able to compute such hashes in O(1) time (after some initial preprocessing).

(22 Jul '13, 16:14) mugurelionut7★

@mugurelionut: Thankyou. I understood your idea of using hashing.Thats pretty cool.but still i dont understand why you are using Binary Search here ?

(23 Jul '13, 14:04) sandeepandey2★

@sandeepandey Binary search for determining the longest length of a palindrome centered at a point.

(23 Jul '13, 14:08) nims116★
showing 5 of 12 show all

Can Anybody Tell Why My Answer didn't got Accepted? My Solution id is :2397163 I used the Same Algorithm

link

answered 22 Jul '13, 00:10

guptaishabh's gravatar image

4★guptaishabh
12
accept rate: 0%

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

(22 Jul '13, 09:04) utkarsh_lath ♦♦5★

But I have handle them too in this part :-

int l = i - 1 - P[i]; l = l/2 - 1; int r = i+1+P[i]; r = r/2 - 1;

(22 Jul '13, 14:34) guptaishabh4★

Or could you tell me a test case where my code gives a WA?

(22 Jul '13, 14:40) guptaishabh4★

Ok, here is a test case

1
5
a 1
b 1
a 1
b 1
a 1

(22 Jul '13, 21:18) utkarsh_lath ♦♦5★

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...

link

answered 22 Jul '13, 00:13

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

1

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.

(22 Jul '13, 00:18) utkarsh_lath ♦♦5★

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

link

answered 22 Jul '13, 00:25

nitish1402's gravatar image

3★nitish1402
31115
accept rate: 0%

edited 22 Jul '13, 00:28

1

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

(22 Jul '13, 08:57) utkarsh_lath ♦♦5★
(22 Jul '13, 18:35) nitish14023★

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

link

answered 22 Jul '13, 00:46

artoemius's gravatar image

3★artoemius
11
accept rate: 0%

1

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

(22 Jul '13, 07:59) tuananh935★

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

link

answered 22 Jul '13, 09:28

vikasnitp's gravatar image

1★vikasnitp
10312
accept rate: 0%

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

(22 Jul '13, 10:49) tuananh935★
2

@tuananh93 don't be rude, of course he can ask for help

First thing is I do not understand how its possible that your code works when you read c[i] twice:

for(i=0;i<k;i++) {
    scanf("%c",&c[i]);
    scanf("%c%d",&c[i],&n[i]);
    res=res+(n[i]*(n[i]+1)/2);
}

but the problem is in n[i]*(n[i]+1)/2, try this test case:

1
1
A 1000000
(22 Jul '13, 11:31) betlista ♦♦3★

but it will be typecasted int64 since res is int64..or not?

(22 Jul '13, 12:30) vikasnitp1★

and one c[i] is just to manange new line

(22 Jul '13, 12:31) vikasnitp1★
1

No, it's not casted to long long if result is big enought, result type is depends on arguments if those are ints, result is int.

(22 Jul '13, 13:00) betlista ♦♦3★

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: http://www.codechef.com/viewsolution/2400280

link

answered 23 Jul '13, 17:31

bondoc73's gravatar image

4★bondoc73
1062410
accept rate: 10%

P[i]++ should be moved to end of loop.

(23 Jul '13, 22:27) utkarsh_lath ♦♦5★

@utkarsh Thx for that .. I saw that mistake n changed the code to

http://www.codechef.com/viewsolution/2400905

but it still gives me WA. Can you plz give me a test case where it fails?

(24 Jul '13, 00:02) bondoc734★

Thx for the repliers ... I totally understood the question n solved it correctly :) Manacher's is in my mind now :D

(24 Jul '13, 16:34) bondoc734★

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. https://www.codechef.com/viewsolution/12275159

link

answered 14 Dec '16, 23:16

edju's gravatar image

0★edju
1
accept rate: 0%

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.

link

answered 07 Apr '17, 11:58

gmiller's gravatar image

0★gmiller
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×2,657
×354
×195
×8
×5

question asked: 22 Jul '13, 00:01

question was seen: 6,488 times

last updated: 07 Apr '17, 11:58