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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Jan 02, 2007 8:08 am

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
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Handling empty strings

Post by MAK » Tue Jan 02, 2007 1:24 pm

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

aha

Post by sohel » Tue Jan 02, 2007 6:31 pm

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
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

asd

Post by darkos32 » Thu Jan 04, 2007 9:11 am

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.

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

Re: asd

Post by emotional blind » Thu Jan 04, 2007 10:53 am

darkos32 wrote: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.
Last edited by emotional blind on Fri Jan 05, 2007 7:09 am, edited 1 time in total.

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

asd

Post by darkos32 » Fri Jan 05, 2007 3:22 am

thanks...i got accepted...

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

Re: asd

Post by emotional blind » Fri Jan 05, 2007 7:11 am

darkos32 wrote:thanks...i got accepted...
Now remove your code please.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Fri Mar 30, 2007 7:56 am

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Mar 30, 2007 8:10 am

mukeshtiwari wrote: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
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Fri Mar 30, 2007 9:01 am

thnkx a lot for help...

PVM
New poster
Posts: 7
Joined: Mon Apr 09, 2007 7:40 am
Contact:

TLE

Post by PVM » Mon Apr 09, 2007 7:04 pm

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]
Last edited by PVM on Tue Apr 10, 2007 7:07 am, edited 1 time in total.

ExUCI
New poster
Posts: 14
Joined: Sat Aug 12, 2006 3:31 am
Location: USA

Post by ExUCI » Tue Apr 10, 2007 2:14 am

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

:lol:

PVM
New poster
Posts: 7
Joined: Mon Apr 09, 2007 7:40 am
Contact:

Post by PVM » Thu Apr 12, 2007 7:05 am

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

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");
	}
    }
}


Thanks 4 Alice
New poster
Posts: 1
Joined: Fri May 11, 2007 6:25 am

handling time limit on judge (I'm newbie)

Post by Thanks 4 Alice » Fri May 11, 2007 6:36 am

solving #11151 problem...

I completed source code
found none of any faulty in my view
using only stdin(cin.getline), stdout(cout)...

like this...

while(true) {
- type input - (cin.getline)
- processing input - (algorithm for #11151)
- print output - (cout)
}

online judge system only gives me "Time Limit" msg repeatedly
like... 10.035 secs (I know the limit is 10 secs)

I think this is not a time limit exceed problem.
Maybe I need to modify "while ~ code" for this problem

anyone help me to handle this time limit?...

have a lucky day !

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

Post by rossi kamal » Thu Sep 20, 2007 9:26 am

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

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

Post Reply

Return to “Volume 111 (11100-11199)”