11404 - Palindromic Subsequence

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

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

help plz

Post by ani_mitr86 » Thu Mar 20, 2008 9:56 am

can anybody tell me the problem with my programs? I solve dit by two methods.but both are giving TLE

first i jaust implemented the LCS On^2 algo for the string and its reverse to find the palindrome

Code: Select all

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

string c, rc, a[1024][1024];

int main(){
	while(cin>>c){
		rc=c; reverse(rc.begin(), rc.end());
		int sz=c.size();
		for(int i=0; i<=sz; i++) for(int j=0; j<=sz; j++){
			if(i==0 || j==0) a[i][j]="";
			else if(c[i-1]==rc[j-1]) a[i][j]=a[i-1][j-1]+c[i-1];
			else{
				int f=a[i-1][j].size(), s=a[i][j-1].size();
				if(f>s) a[i][j]=a[i-1][j];
				else if(s>f) a[i][j]=a[i][j-1];
				else if(s==f){
					if(a[i-1][j]<a[i][j-1]) a[i][j]=a[i-1][j];
					else a[i][j]=a[i][j-1];
				}
			}
		}
		cout<<a[sz][sz]<<endl;
	}
	return 0;
}
second i use d the idea suggested by robert to solve it in On

Code: Select all

#include<iostream>
#include<cstring>

using namespace std;

char c[1024];
int sz;

void palin(int f, int s, char* ans){
	char ani[1024]; ans[0]=ani[0]='\0';
	if(f>s) return;
	for(int ch='a'; ch<='z'; ch++){
		int x=-1, y=-1;
		for(int i=f; i<=s; i++) if(c[i]==ch){ x=i; break;}
		if(x<0) continue;
		for(int i=s; i>=f; i--) if(c[i]==ch){ y=i; break;}
		if(y<0) continue;
		if(x==y){ if(ans[0]=='\0'){ ans[0]=c[x]; ans[1]='\0';}}
		else{
			palin(x+1, y-1, ani);
			if(strlen(ani)+2>strlen(ans)){
				ans[0]=c[x];
				int i;
				for(i=0; i<strlen(ani); i++) ans[i+1]=ani[i];
				ans[i+1]=c[y]; ans[i+2]='\0';
			}
		}
	}
	return;
}

int main(){
	while(cin>>c){
		sz=strlen(c);
		char ans[1024];
		palin(0,sz-1,ans);
		cout<<ans<<endl;
	}
	return 0;
}
[/code]

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: help plz

Post by Robert Gerbicz » Thu Mar 20, 2008 12:22 pm

ani_mitr86 wrote:can anybody tell me the problem with my programs? I solve dit by two methods.but both are giving TLE

first i jaust implemented the LCS On^2 algo for the string and its reverse to find the palindrome
In the second code:
Please note that the time complexity for asking a single strlen(w) is O(L), where L is the length of w, so doing

Code: Select all

for(i=0; i<strlen(ani); i++) ans[i+1]=ani[i]; 
makes it slow, compute strlen(ani) only once:

Code: Select all

int LENGTH=strlen(ani);
for(i=0; i<LENGTH; i++) ans[i+1]=ani[i]; 
And this gives still TLE. Please note that in my code there was only one strlen call for one input word, and you do lots of strlen for one word. And it seems for me a recursive implementation for the problem not dp in your second code.

ps. I've checked som input/output and it looks like good (the second code).

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

Post by ani_mitr86 » Thu Mar 20, 2008 1:06 pm

thanks

it does pass the input in the board

probably u r right......I will try to implement it in better way

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 11404 - Palindromic Subsequence

Post by Ron » Sun Aug 24, 2008 12:30 pm

My On^2 code gives WA....why ??
Please help ...!!

Code: Select all

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a[1001][1001],b[1001][1001];
string x,y;
void print(int i,int j){
	if(i==0||j==0)	return ;
	if(b[i][j]==1){
		print(i-1,j-1);
		cout<<x[i-1];
	}
	else if(b[i][j]==2)
		print(i-1,j);
	else
		print(i,j-1);
}

void LCS(){
	int i,j,m=x.length(),n=y.length();
	char ch[1001][1001],cc='z';
	cc++;
	for(i=0;i<=m;i++){
		a[i][0]=0;
		ch[i][0]=cc;
	}
	for(j=1;j<=n;j++){
		a[0][j]=0;
		ch[0][j]=cc;
	}
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(x[i-1]==y[j-1]){
				a[i][j]=a[i-1][j-1]+1;
				b[i][j]=1;
				ch[i][j]=x[i-1];
				if(a[i-1][j]>=a[i][j]&&ch[i-1][j]<ch[i][j]){
					b[i][j]=2;
					ch[i][j]=ch[i-1][j];
				}
				if(a[i][j-1]>=a[i][j]&&ch[i][j-1]<ch[i][j]){
					b[i][j]=3;
					ch[i][j]=ch[i][j-1];
				}
				a[i][j]=max(a[i][j],max(a[i-1][j],a[i][j-1]));
			}
			else if(a[i-1][j]==a[i][j-1]){
				if(ch[i-1][j]<=ch[i][j-1]){
					a[i][j]=a[i-1][j];
					ch[i][j]=ch[i-1][j];
					b[i][j]=2;
				}
				else{
					a[i][j]=a[i][j-1];
					ch[i][j]=ch[i][j-1];
					b[i][j]=3;
				}
			}
			else if(a[i-1][j]>a[i][j-1]){
				a[i][j]=a[i-1][j];
				ch[i][j]=ch[i-1][j];
				b[i][j]=2;
			}
			else{
				a[i][j]=a[i][j-1];
				ch[i][j]=ch[i][j-1];
				b[i][j]=3;
			}
		}
	}
	print(m,n);
	cout<<endl;
}

int main(){
	while(cin>>x){
		y=x;
		reverse(y.begin(),y.end());
		if(x==y)	cout<<x<<endl;
		else{
			if(x<y)	swap(x,y);
			LCS();
		}
	}
	return 0;
}


Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11404 - Palindromic Subsequence

Post by Chirag Chheda » Sat Apr 11, 2009 9:31 am

Now I have recoded it again to get a WA. I pass all the inputs in this forum. can someone please help me. :cry: :cry: :cry:

Code: Select all

#include<iostream>
#include<vector>

using namespace std;

char ss[1008],ch[1008][1008];
int len[1008][1008],pos[1008][1008],fw[1008],re[1008],st,en;
bool vis[1001][1001];

int rec(int i,int j)
{
    if(i>j) return 0;
    if(i==j)
    {
        len[i][j]=1;
        ch[i][j]=ss[i];
        return len[i][j];
    }
    
    if(!vis[i][j])
    {
         vis[i][j]=1;
         if(ss[i]==ss[j])
         {
              len[i][j] = rec(i+1,j-1)+2;
              ch[i][j]=ss[i];
              pos[i][j]=1;
         }
         
         else
         {
              len[i][j] = rec(i+1,j);
              pos[i][j]=2;
              ch[i][j]=ch[i+1][j];
              
              int x = rec(i,j-1);
              
              if(x > len[i][j])
              len[i][j]=x,pos[i][j]=3,ch[i][j]=ch[i][j-1];
              
              else if(x == len[i][j])
              {
                    ch[i][j]=min(ch[i+1][j],ch[i][j-1]);
                    if(ch[i][j]==ch[i+1][j]) pos[i][j]=2;
                    else pos[i][j]=3;
              }
         }
    }
    
    return len[i][j];
}

void gen(int i,int j)
{
     if(i>j) return;
     if(i==j)
     {
         fw[st++]=ss[i];
     }
     
     else if(pos[i][j]==1)
     {
          fw[st++]=ch[i][j];
          re[en++]=ch[i][j];
          gen(i+1,j-1);
     }
     
     else if(pos[i][j]==2)
     {
          gen(i+1,j);
     }
     
     else if(pos[i][j]==3)
     {
          gen(i,j-1);
     }
     return;
}

int main()
{
    int i,j,length;
   
    while(gets(ss))
    {
        length = strlen(ss);
        memset(vis,0,sizeof(vis));

        rec(0,length-1);
        
        st = en = 0;
        
        gen(0,length-1);
        
    	for(i = 0; i<st; i++) printf("%c",fw[i]);
    	for(i = en-1; i>=0; i--) printf("%c",re[i]);

    	printf("\n");        
    }
    return 0;
}


Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11404 - Palindromic Subsequence

Post by Chirag Chheda » Sun Apr 12, 2009 2:36 pm

Can someone please reply.

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Re: 11404 - Palindromic Subsequence

Post by roticv » Thu Jul 02, 2009 9:20 am

You are using the wrong method. It does not give you the smallest lexicographical palindrome.

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

11404 - Palindromic Subsequence

Post by BUET » Sun Jul 03, 2011 12:19 am

Code: Select all

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<cstdio>

using namespace std;

#define MAX 10005
char com1[10005];
char com2[10005];
int ind1,ind2;
int m,n;
int coun;
int i,j,c[MAX][MAX],b[MAX][MAX];
int len;

int LCSlength() 
{
		m=len;
		n=len;
		for (i=1;i<=m;i++) 
			c[i][0]=0;
		for (j=0;j<=n;j++) 
			c[0][j]=0;
		for (i=1;i<=m;i++)
		for (j=1;j<=n;j++)
		{
			if (com1[i-1] == com2[j-1]) 
			{
				c[i][j]=c[i-1][j-1]+1;
				b[i][j]=1; /* from north west */
			}
			else if (c[i-1][j]>c[i][j-1]) 
			{
					c[i][j]=c[i-1][j];
					b[i][j]=2; /* from north */
			}
			else if(c[i-1][j]<c[i][j-1])
			{
				
					c[i][j]=c[i][j-1];
					b[i][j]=3; /* from west */

			}
			else 
			{
				
				if(int(com1[i-1] - 'a') > int(com2[j-1] - 'a'))
				{
					c[i][j]=c[i-1][j];
					b[i][j]=2; /* from north */
					
					
				}
				else
				{
					c[i][j]=c[i][j-1];
					b[i][j]=3; /* from west */
				
								
				}
			}
		}

		

		return c[m][n];
}

void printLCS(int i,int j) 
{
       if (i==0 || j==0) return;
       if (b[i][j]==1) 
	   {
			printLCS(i-1,j-1);
			if( coun > 1)
			{
			   printf("%c",com1[i-1]);
			   coun--;
			}
			else
			{
				printf("%c\n",com1[i-1]);
				
			}

	   }
	   else if (b[i][j]==2)
	   {
		     
	         printLCS(i-1,j);
	   }
	   else
			 printLCS(i,j-1);
}

int main()
{

	string s,s1,s2;
	int check = 1;

	int tr = 0;
    

	char in[10009];
	
	

	ind1 = ind2 = 0;

	//(scanf("%s",in)) == 1
	while(gets(in))
	{
		len = strlen(in);
		strcpy(com1,in);
		reverse(in,in+strlen(in));
		strcpy(com2,in);

		if(strcmp(com1,com2) > 0)
		{
			s = com1;
			s1 = com2;
			swap(s,s1);

			strcpy(com1,s.c_str());
			strcpy(com2,s1.c_str());

		}


		coun = LCSlength();

		//if(tr == 0)
		//	tr = 1;
	//	else
			//cout << "\n";
  
		printLCS(len,len);

		
	}


   		 
	
   return 0;
}
what is wrong in my code?

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11404 - Palindromic Subsequence

Post by Imti » Thu Jul 21, 2011 2:52 pm

My code passed all the Input found here and I also tested this with lot of hand made inputs which it passed...but judge giving me WA...could anyone
please give me some more tests or check whats wrong in my code?

Code: Select all

#include<stdio.h>
#include<string.h>
long len[2000][2000];
char s[2000][2000],ch[2000][2000];
void print(long i,long j)
{
     if(i>j)
      return;
     if(i==j)
     {
       printf("%c",ch[i][j]);
       return;
     }
     if(s[i][j]=='1')
     {
       printf("%c",ch[i][j]);
       print(i+1,j-1);
       printf("%c",ch[i][j]);
     }
     else if(s[i][j]=='2')
       print(i,j-1);
     else
       print(i+1,j);
}
int main()
{
    char str[2000];
    long i,j,k,n;
    while(gets(str))
    {       
       n=strlen(str);
       for(i=0;i<n;i++)
          for(k=0,j=i;j<n;j++,k++)
          {
            if(k==j)
            {
              len[k][j]=1;
              ch[k][j]=str[k];
             s[k][j]='4';
            }
            else if(str[k]==str[j])
            {
             len[k][j]=2+len[k+1][j-1];
             ch[k][j]=str[k];
             s[k][j]='1';
            }
            else
            {
                if((len[k][j-1]>len[k+1][j])||(len[k][j-1]==len[k+1][j]&&ch[k][j-1]<=ch[k+1][j]))
                {
                 len[k][j]=len[k][j-1];
                 ch[k][j]=ch[k][j-1];
                 s[k][j]='2';
                }
                else
                {
                 len[k][j]=len[k+1][j];
                 ch[k][j]=ch[k+1][j];
                 s[k][j]='3';
                 }
            }
          }
       print(0,n-1);
       printf("\n");
    }
    return 0;
}

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

Re: 11404 - Palindromic Subsequence

Post by forthright48 » Sun Feb 10, 2013 11:06 pm

I am getting WA.
My code matches with all the inputs from the forum.

Code: Select all

 AC Thanks to lbv :)
Is there any blank before, after or in the middle of string? I handled blank lines as inputs but still WA.
Last edited by forthright48 on Mon Feb 11, 2013 6:42 am, edited 2 times in total.
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11404 - Palindromic Subsequence

Post by lbv » Mon Feb 11, 2013 12:11 am

forthright48 wrote:I am getting WA.
My code matches with all the inputs from the forum.
Try these:

Input

Code: Select all

kfclbckibbibjccbej
hoiqftxkudvytoyityrq
dcbadbaddcccbbbcccbadcd
effcgefbhbefcdigiaiidhgieg
fjvewlqunhflqvrehansfbctxkacdl
jglkniogmnhpjinhbiinjbcfdcnplh
Output

Code: Select all

bcibbicb
qtyoytq
dcabcccbbbcccbacd
eghdiiaiidhge
felflef
hpjniinjph
forthright48 wrote:Is there any blank before, after or in the middle of string? I handled blank lines as inputs but still WA.
As far as I can tell, there are no whitespaces in the middle of a word (the problem statement is clear that each word has only letters from [a-z]). I don't know if there are any blank lines or leading/trailing whitespaces, but if there are, ignoring them worked for me.

Post Reply

Return to “Volume 114 (11400-11499)”