11475 - Extend to Palindrome

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

11475 - Extend to Palindrome

Post by sonyckson » Sun Aug 03, 2008 6:07 pm

Hi!, its not the first time i see this problem, and its not the first time i dont see how to solve it... any hints? thanks! Eric.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 11475 - Extend to Palindromes

Post by hamedv » Sun Aug 03, 2008 6:23 pm

Yes, i don't know too

There were problems like this an i solved them using DP, because the input size was less than 1000 but in this problem it's so huge.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Re: 11475 - Extend to Palindromes

Post by Ivan » Sun Aug 03, 2008 6:29 pm

Hint: Rolling hash might be a viable option here.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11475 - Extend to Palindromes

Post by Leonid » Sun Aug 03, 2008 8:55 pm

Knuth-Morris-Pratt algorithm is an option to consider if you're trying to solve this task.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11475 - Extend to Palindromes

Post by baodog » Mon Aug 04, 2008 10:03 am

Hi,

I use base N representation mod M, reading forward and backward, starting from
the last symbol. I keep get WA. I have tried many cases.
Help is appreciated! Thanks.

Code: Select all

Accepted... silly index error.  Thanks!
Last edited by baodog on Mon Aug 04, 2008 11:00 am, edited 1 time in total.

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Re: 11475 - Extend to Palindromes

Post by MAK » Mon Aug 04, 2008 10:52 am

@baodog:
Your code prints an extra unprintable character at the end of each line on my machine. But it looks otherwise ok.

@hamedv:
I'm curious about the O(n^2) DP you mentioned. The simple brute force way of solving this problem is also O(n^2). Could you please post an outline of your idea?

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 11475 - Extend to Palindromes

Post by hamedv » Mon Aug 04, 2008 6:25 pm

MAK wrote:@baodog:
Your code prints an extra unprintable character at the end of each line on my machine. But it looks otherwise ok.

@hamedv:
I'm curious about the O(n^2) DP you mentioned. The simple brute force way of solving this problem is also O(n^2). Could you please post an outline of your idea?
I mean this:
http://www.comp.nus.edu.sg/~stevenha/pr ... Palindrome

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Re: 11475 - Extend to Palindromes

Post by MAK » Mon Aug 04, 2008 10:11 pm

Thanks Hamedv. That is a much harder problem. The present problem asks that you only consider adding characters at the end of the string, which simplifies matters a lot.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11475 - Extend to Palindromes

Post by emotional blind » Tue Aug 19, 2008 8:13 pm

I think that is not that hard. because the length of the string is only 1000. So O(N^2) solution will be enough.

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Re: 11475 - Extend to Palindromes

Post by MAK » Sat Aug 23, 2008 10:43 pm

IMHO the idea behind the solution (and not the implementation) of this problem is somewhat simpler that the one Hamedv referred to.

Of course, what I find find hard (or easy) can quite naturally seem easy (or hard) to someone else :-).

sijal
New poster
Posts: 9
Joined: Fri Jul 18, 2008 12:10 pm
Location: Iran-shiraz
Contact:

Re: 11475 - Extend to Palindromes

Post by sijal » Thu Oct 16, 2008 4:58 pm

i solved this using kmp string matching algorithm in 0.020 seconds
Learn to swim.

Sylpharion
New poster
Posts: 2
Joined: Thu Feb 05, 2009 5:44 pm

Re: 11475 - Extend to Palindromes

Post by Sylpharion » Thu Feb 05, 2009 5:48 pm

Anybody can help me?
I've use the KMP and I'm sure that my program run on the largest testcases. And it works.. but I have a TLE on my code.

Code: Select all

#include<iostream>
#include<stack>

using namespace std;

char text[100001], pat[100001];
int f[100001];
stack<char> tempS;

bool isPalindrome(char* T)
{
    int i;
    for(i=0;i<strlen(T)/2;i++)
        if(T[i]!=T[strlen(T)-1-i])
            return false;
    return true;
}

void reverse(char T[], char* P)
{
    int i;
    char temp;
    for(i=0;i<strlen(T);i++)
        P[strlen(T)-1-i]=T[i];
    P[strlen(T)]='\0';
}

void fFunction(char*P)
{
	int i,j,m;
	i=1;
	j=0;
	m=strlen(P);
	while(i<=m-1)
	{
		if(P[j]==P[i])
		{
			f[i]=j+1;
			i++;
			j++;
		}
		else if(j>0)
			j=f[j-1];
		else
		{
			f[i]=0;
			i++;
		}
	}
}

void KMPMatch(char* T, char*P)
{
    bool done=false;
	int i,j,m,trace=0,k;
	i=0;
	j=0;
	while(i<=strlen(T) && !done)
	{
       	m=strlen(P);
		if(P[j]==T[i])
		{
			if(j==m-1)
			{

                cout<<text;
                while(!tempS.empty())
                {
                    cout<<tempS.top();
                    tempS.pop();
                }
                cout<<endl;              
                done=true;
            }
			i++;
			j++;
		}
		else if (j>0)
		{
			trace=j;
			j=f[j-1];
			for(k=0;k<trace-j;k++)
			{
			    tempS.push(P[strlen(P)-1]);
			    P[strlen(P)-1]='\0';
            }
        }
		else
		{
			i++;
			tempS.push(P[strlen(P)-1]);
			P[strlen(P)-1]='\0';
        }
    }
}

int main()
{
	int i;
	while(cin>>text)
	{
        if(isPalindrome(text))
          cout<<text<<endl;
        else
        {
           reverse(text,pat);
    	   fFunction(pat);
	       KMPMatch(text,pat);
        }
    }
	return 0;
}

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Re: 11475 - Extend to Palindromes

Post by MAK » Wed Apr 01, 2009 2:26 pm

Try an input with a large string of the same character with a different character near the end.
e.g.
xxxxxx......xxxy
xxxxxx........xyxx

Sylpharion
New poster
Posts: 2
Joined: Thu Feb 05, 2009 5:44 pm

Re: 11475 - Extend to Palindromes

Post by Sylpharion » Tue Apr 07, 2009 3:52 am

yes, it works very fast, but it was TLE again when i submitted...
oh.. help me... :-(

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11475 - Extend to Palindromes

Post by serur » Thu May 28, 2009 12:01 pm

Consider the dual of the problem: find the largest suffix of the input text that is a palindrome.
text = abB, where B is the reverse of b. Then textTEXT = abBbBA, then you find the longest tandem repeat...
This leads to O(nlogn) solution which gets TLE + MLE.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Post Reply

Return to “Volume 114 (11400-11499)”