11151 - Longest Palindrome

[helloneo]

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]

To rossi kamal

YES


Thanks
keep posting
Sapnil

[bishop]

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


[emotional blind]

instead of this

Code: Select all

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

you should simply print new line

Code: Select all

cout<<endl;

[bishop]

again WA
after editing

[bishop]

here my post again
about "WA"

Code: Select all

AC



[emotional blind]

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]

AC

[emotional blind]

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

[bishop]

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

[bishop]

arif bhai great helper............thank u

[emotional blind]

you mean, you got accepted?

[islam_al_aarag]

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
[code][/code]
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[i][j]==0) DP[i][j]=1+get(i+1,j-1);
return DP[i][j];
}
else
{
if(DP[i][j]==0) DP[i][j]=Math.max(get(i,j-1),get(i+1,j));
return DP[i][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);
}
}
}

[receme]

I have read these discussion....Fix my code.... but still I got WA... Plz help.......Here is my code

#include<stdio.h>
#include<string.h>
//#include<conio.h>


char x[2000],y[2000];
long i,j,d,l,m,n,c[2000][2000],b[2000][2000];
long lcslength(){
m=strlen(x);
n=strlen(y);

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(x[i-1]==y[j-1]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1; }
else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
return c[m][n];
}

int main(){

gets(x);
sscanf(x,"%ld",&d);
while(d--){
gets(x);
n=strlen(x);
j=0;
for(i=n-1;i>=0;i--){
y[j]=x[i];
j++; }

printf("%ld\n",lcslength());

}
//getch();
return 0;
}

[hano2a]

Im getting TLE altough it takes no time in solving a 1000 letter palindrome,
any ideas??

Code: Select all

# include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;

string s;
const int SIZE = 10001;
int dp [SIZE][SIZE];
void Initialize ()
{
   for (int i = 0 ; i < SIZE ; i++)
      for (int j = 0 ; j < SIZE ; j++)
         dp[i][j]=-1;
}
int longestPalindrom (int i , int j)
{
   if (dp[i][j]!=-1)
      return dp[i][j];
   if (i>j )
      return 0;
   if (i == j)
      return 1;
   if (i<j  && s[i]==s[j])
   {
      dp[i][j] = 2+ longestPalindrom(i+1, j-1);
      return dp[i][j];
   }
   if (i<j && s[i]!=s[j])
   {
      dp[i][j]= max(longestPalindrom(i+1,j),longestPalindrom(i,j-1));
      return dp[i][j];
   }
}
int main()
{
   int t ;
   cin >> t;
   cin.ignore();
   while(t--)
   {
      Initialize();
      getline(cin,s);
      cout<<longestPalindrom(0,s.size()-1)<<endl;
   }
}



Thanx