11404 - Palindromic Subsequence

[ani_mitr86]

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]

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]

thanks

it does pass the input in the board

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

[Ron]

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]

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

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]

Can someone please reply.

[roticv]

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

[BUET]

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]

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]

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.

[lbv]

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

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.