11151 - Longest Palindrome

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

Moderator: Board moderators

rossi kamal
New poster
Posts: 14
Joined: Mon Sep 03, 2007 10:11 am
Contact:

Post by rossi kamal » Thu Sep 20, 2007 10:41 am

can anyone help i am getting TLE ...

Code: Select all

//11151.cpp

//largest palindrome 
#include<stdio.h>
#include<string.h>

int largest(int xx,int yy);
int max(int zz,int kk);


char a[1005];

int main()
{
	 
	
	 //freopen("inpalindrome.txt","r",stdin);     
     int n; 
	 
	 scanf("%d\n",&n);
	// getchar();
	 int ii;
     for(ii=1;ii<=n;ii++)
	 {	
		 
			
		 
			gets(a);
			printf("%d",largest(0,strlen(a)-1) );
			
	 

	}
	 




	return 0;
}

int largest(int i,int j)
{
	
	 if(i==j)
		 return 1;
	 
	// if(i>j)
	//	return 0;
	
	 
	 else if(i!=j && a[i]==a[j])
		 return largest(i+1,j-1)+2;



     else
		 return max(largest(i+1,j) ,largest(i,j-1) );
	



}


int max(int aaa,int bbb)
{
	if(aaa>=bbb)
		return aaa;
	else 
		return bbb;

}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Sep 25, 2007 3:04 pm

You can try "memorization" or you can solve it with bottom-up DP..
Another thing.. taking input in your code is not ok.. see previous posts about that..

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Sun Oct 07, 2007 7:05 pm

To rossi kamal

YES


Thanks
keep posting
Sapnil

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Re: I still got WA

Post by bishop » Sun Aug 17, 2008 4:40 pm

FAQ wrote:Here is my trying input

Code: Select all

12
ADAM
MADAM

qweqweqwedadqweqweqwe

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abcdefghijklmnopqrstuvwxyz
abcdefhh
abcabcabc
0101010101
a
abefgba
Line with nothing is empty string

Code: Select all

3
5
0
13
0
255
1
2
5
9
1
5
some more tricky tests please?
my code gives output same output
but result WA
why?? i cannot find ..

Code: Select all

AC
Last edited by bishop on Tue Aug 19, 2008 5:51 pm, edited 1 time in total.

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

Re: 11151 - Longest Palindrome

Post by emotional blind » Tue Aug 19, 2008 4:16 pm

instead of this

Code: Select all

      if(n>0)
      {cout<<endl;}

you should simply print new line

Code: Select all

cout<<endl;

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Re: 11151 - Longest Palindrome

Post by bishop » Tue Aug 19, 2008 4:24 pm

again WA
after editing

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Re: 11151 - Longest Palindrome

Post by bishop » Tue Aug 19, 2008 4:33 pm

here my post again
about "WA"

Code: Select all

AC

Last edited by bishop on Tue Aug 19, 2008 5:50 pm, edited 1 time in total.

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

Re: 11151 - Longest Palindrome

Post by emotional blind » Tue Aug 19, 2008 4:44 pm

Code: Select all

       for(i=0; i<=m; i++)
       for(j=0; j<=n; j++)   
       {
          if(X[i]==Y[j]){c[i][j]=c[i-1][j-1]+1;}

Here is the problem
when i = 0 and j = 0, you are trying to access c[-1][-1] by c[i-1][j-1], isn't it?

I think your loop should start from 1 for each i and j.

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Re: 11151 - Longest Palindrome

Post by bishop » Tue Aug 19, 2008 4:53 pm

AC
Last edited by bishop on Tue Aug 19, 2008 5:49 pm, edited 1 time in total.

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

Re: 11151 - Longest Palindrome

Post by emotional blind » Tue Aug 19, 2008 4:56 pm

So, What do you mean by posting your code again?
Did you get accepted?

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Re: 11151 - Longest Palindrome

Post by bishop » Tue Aug 19, 2008 5:03 pm

sorry
that was for Wrong answer.......

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

Re: 11151 - Longest Palindrome

Post by bishop » Tue Aug 19, 2008 5:49 pm

arif bhai great helper............thank u :lol:

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

Re: 11151 - Longest Palindrome

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

you mean, you got accepted?

lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: handling time limit on judge (I'm newbie)

Post by lnr » Mon Oct 06, 2008 4:23 pm

To Thanks 4 Alice
Your code:

while(true) {
type input - (cin.getline)
processing input - (algorithm for #11151)
print output - (cout)
}
May be you are not checking the end of file.
You are taking input on and on and on..................................................

islam_al_aarag
New poster
Posts: 1
Joined: Tue Sep 22, 2009 9:02 pm

Re: 11151 - Longest Palindrome

Post by islam_al_aarag » Tue Sep 22, 2009 9:06 pm

hi
i wrote a code to this problem in java
but i got WA
although i get all test cases in the topic right this is my code tell me if it is illegal to post coz i am new import java.util.*;
import java.io.*;
class Main
{
static String s;
static int[][] DP = new int[1001][1001];
public static int get(int i , int j)
{
if(i==s.length() || j==-1 )
return DP[s.length()-1][0];
else
{
if(s.charAt(i)==s.charAt(j)){
if(DP[j]==0) DP[j]=1+get(i+1,j-1);
return DP[j];
}
else
{
if(DP[j]==0) DP[j]=Math.max(get(i,j-1),get(i+1,j));
return DP[j];
}
}
}
public static void main(String[] args)throws IOException
{
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(stdin.readLine());
for(int i=0;i<n;i++)
{
s=stdin.readLine();
if(s.length()!=0) System.out.println(get(0,s.length()-1));
else System.out.println(0);
for(int j=0;j<s.length()+1;j++) Arrays.fill(DP[j] , 0);
}
}
}

Post Reply

Return to “Volume 111 (11100-11199)”