11151 - Longest Palindrome

[Darko]

I'm not a C programmer, but I would imagine that mixing scanf() and gets() in the same code can just lead to a trouble. In Java I have two different routines for reading input - one reads it line by line (and I have to parse a line if I want a number of test cases, for example) and the other one behaves like scanf. I never use both at the same time.

But, I agree that the first case should not be an empty string, I think that it is a plus to know what scanf() does exactly, but it shouldn't be a part of the problem. Especially because judge uses an outdated compiler.

[MAK]

Here's how I took care of input (in C++).

Code: Select all

        int T;
   cin>>T   
   cin.getline(S,MAX,'\n');
   //This is just to get the rest of the line after T

        while(T--)
   {
      cin.getline(S, MAX, '\n');
      .......
   }
   


I originally got a wrong answer with cin>>S, but all problems disappeared after I recoded it using cin.getline. Hope this helps.

[sohel]

I usually avoid scanf or cin altogether for these cases.

Code: Select all

  char str[10000];
  gets(str);
  sscanf(str, "%d", &n);
  while(n--) {
     gets(str);
     process()
  }


This is how I do it.

[darkos32]

hi,i'm still got WA...this is what i used at my code :

LCDlength -> Longest Common Sequence procedure..

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAX 1001
char X[MAX],Y[MAX];
int i,j,m,n,c[MAX][MAX],b[MAX][MAX];

void main() {
   freopen("lp.in","r",stdin);
   freopen("lp.out","w",stdout);
   int n;
   scanf("%d\n",&n);
   int i=0;
   while(i<n){
      gets(X);
      int j =0;
      int byk = strlen(X);
      int awal = byk-1;
      while(awal>=0){
         Y[j] = X[awal];
         j++;awal--;
      }
      Y[j]='\0';
      printf("%d\n",LCSlength());
      i++;
   }
}


thanks.

[emotional blind]

hi,i'm still got WA...this is what i used at my code :

LCDlength -> Longest Common Sequence procedure..

Code: Select all




thanks.

Read previous posts, and take input carefully.

[darkos32]

thanks...i got accepted...

[emotional blind]

thanks...i got accepted...

Now remove your code please.

[mukeshtiwari]

hi everybody i m trying to solve this problem but getting WA many times ...i m really frustrated ..plz help me..

my algorithm is i m trying to enumarate all the n*(n+1)/2 substrings ,where n is string size
and checking which one is palindrome ....in another post of this problem the output of string qweqweqwedadqweqweqwe is given 13 but my program gives 3 and substring is dad ...can some one explain me how is it 13 .....plz tell me my algorithm is correct or not


here is my code

Code: Select all

#include<stdio.h>
#include<string.h>
 int chkpalin(char* a,int k,int n)
   {
      int w;
      for(w=k;w<=n;w++)
       if(a[w]!=a[n+k-w])
         return(0);
      
      return(1);
   }
   main()
    {

        char str[1010],c;
        int i,j,k,n,w,v;
         
       scanf("%d",&k);
       getchar();
      for(v=0;v<k;v++)
       {
         w=0;
         gets(str);
         n=strlen(str);
         for(i=n-1;i>=0;i--)
          {
            for(j=0;j+i<n;j++)//enumarate all the n*(n+1)/2 substrings chk wheather a[j] to a[i+j] is palindrome or not
             {

               w=chkpalin(str,j,i+j);
               if(w==1)
                break;
             }
            
            if(w==1)
              break;
         }
         
         printf("%d\n",i+1);
                   /printf("palindrome is \n");
         for(int x=j;x<=i+j;x++)
           printf("%c",str[x]);
          printf("\n");*/
      }
   }

[helloneo]

my algorithm is i m trying to enumarate all the n*(n+1)/2 substrings ,where n is string size
and checking which one is palindrome ....in another post of this problem the output of string qweqweqwedadqweqweqwe is given 13 but my program gives 3 and substring is dad ...can some one explain me how is it 13 .....plz tell me my algorithm is correct or not

The answer for "qweqweqwedadqweqweqwe" is "qwqewdadweqwq"
So, the length is 13..

It doesn't need to be a consecutive substring.. so, you can remove letters at any points..

[mukeshtiwari]

thnkx a lot for help...

[PVM]

getting TLE, any idea?? :evil:



would appreciate some help on it, looking forward to write in C if it helps!![code]code removed.. even though not accepted yet!! [/code]

[ExUCI]

The only thing wrong in your code is the limit. Change 255 by 1000.
Next time put a readable code.

Now remove it from the forum!!!

[PVM]

I am getting the same output but uva judge giving me wrong answer

Code: Select all


/* @JUDGE_ID:  60332ER  11151  Java  "Easy algorithm" */

import java.io.*;
import java.util.*;

class Main{
   static int[][] result;
   static String ReadLn (int maxLg)  {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";

        try{
            while (lg < maxLg){
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e){
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null); 
        return (new String (lin, 0, lg));
    }

    static int max(int i, int j){
   
   return ( (i>=j) ? i:j);
      

    }

    static int longest(String s,int i, int j){
   
   if (i == j) return (result[i][j]=1);
   else if ( i == j-1 ){
      if(s.charAt(i) == s.charAt(j))
         return (result[i][j]=2);
      else return (result[i][j]=1); /* Main.max(Main.longest(s,i,j-1),Main.longest(s,i+1,j)); */

   }
   else if(s.charAt(i) == s.charAt(j)){
      result[i][j]=2;
      return (2+Main.longest(s,i+1,j-1));
   }
   else{
      return  Main.max((result[i][j-1]=((result[i][j-1]!=-1)? result[i][j-1] : Main.longest(s,i,j-1))),
             (result[i+1][j]=((result[i+1][j]!=-1)? result[i+1][j]: Main.longest(s,i+1,j))));
      
   }
    }

    public static void main (String args[]){
        Main myWork = new Main(); 
        myWork.Begin();           
    }

    void Begin(){
        String input;
   int t,len,mid,i,j;          
   
   input = Main.ReadLn (255);
   t=Integer.parseInt(input.trim());
   
   /*System.out.println(); */
        while (t!=0){   
      
      input = (Main.ReadLn (257)).trim();
      len = input.length();
      /* System.out.println(input+" "+input.length()); */
           


      if ( len == 0 ){
         System.out.print(0);
         t--;
      }
      else if ( len == 1){
         System.out.print(1);
         t--;
      }
      else{   
         result = new int[len][len];
         for(int m=0;m<result.length;m++){
            for(int n=0;n<result[m].length;n++){
               result[m][n] =   -1;
            }
         }
         System.out.print(Main.longest(input,0,len - 1));
         t--;
      }
      if(t != 0)
         System.out.print("\n");
   }
    }
}



[rossi kamal]

Here, we consider also the empty string as a palindrome.

The length of palindrome is 0 in that case..am i right?

[rossi kamal]

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;

}