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

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;

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;
int sz;

void palin(int f, int s, char* ans){
char ani; ans=ani='\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'){ ans=c[x]; ans='\0';}}
else{
palin(x+1, y-1, ani);
if(strlen(ani)+2>strlen(ans)){
ans=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;
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

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

My On^2 code gives WA....why ??

Code: Select all

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a,b;
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,cc='z';
cc++;
for(i=0;i<=m;i++){
a[i]=0;
ch[i]=cc;
}
for(j=1;j<=n;j++){
a[j]=0;
ch[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

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,ch;
int len,pos,fw,re,st,en;
bool vis;

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

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

Re: 11404 - Palindromic Subsequence

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

Code: Select all

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

using namespace std;

#define MAX 10005
char com1;
char com2;
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;
for (j=0;j<=n;j++)
c[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;

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
Contact:

Re: 11404 - Palindromic Subsequence

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;
char s,ch;
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;
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
Contact:

Re: 11404 - Palindromic Subsequence

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

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

Input

Code: Select all

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