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

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

11151 - Longest Palindrome

Post by soyoja » Sat Dec 30, 2006 10:14 pm

hmm.. It's so tricky. It just looks like an easy problem, but I received WA repeatedly... Is there any critical input?
I love Problem Solving!!! :) :) :)

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 » Sat Dec 30, 2006 10:25 pm

soyoja wrote:Is there any critical input?
My code takes emtpy string as input.
What about yours?

Karim
New poster
Posts: 7
Joined: Sun Sep 24, 2006 4:11 pm

11151 WA

Post by Karim » Sun Dec 31, 2006 3:03 am

I am getting wrong answer but i dont know why

can anyone tell me

Here is the code

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string s,t1,t2;

int main()
{
//freopen("d.in","rt",stdin);
int t;
int i,j;

cin>>t;
getline(cin,s);
for(i=0;i<t;i++)
{
getline(cin,s);
if(s=="")
{
cout<<"0"<<endl;
continue;
}
for(j=0;j<s.length();j++)
{
t1 = s.substr(0,s.length()-j);
t2 = s.substr(0,s.length()-j);
reverse( t1.begin() , t1.end() );
if(t1 == t2)
{
cout<<t1.length()<<endl;
break;
}
t1 = s.substr(j);
t2 = s.substr(j);
reverse( t1.begin() , t1.end() );
if(t1 == t2 )
{
cout<<t1.length()<<endl;
break;
}
}
}
return 0;
}

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Dec 31, 2006 4:52 am

Try this input :

Code: Select all


1
qweqweqwedadqweqweqwe

I think the output should be :

Code: Select all


3

CMIW...

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

Post by emotional blind » Sun Dec 31, 2006 5:39 am

jan_holmes wrote:Try this input :

Code: Select all


1
qweqweqwedadqweqweqwe

I think the output should be :

Code: Select all


3

CMIW...
Oput should be

Code: Select all

13

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

I still got WA

Post by FAQ » Sun Dec 31, 2006 6:40 am

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?

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Take the entire line as input

Post by MAK » Sun Dec 31, 2006 10:17 am

Yes, instead of taking a string (cin>>line in C++), take the entire line as input (use cin.getline). That way, even if the line is empty, it is still considered as valid input.

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

Post by emotional blind » Sun Dec 31, 2006 11:05 am

Correct output

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi » Sun Dec 31, 2006 11:40 am

there is no critical input. what algorithm did you use?

artie
New poster
Posts: 8
Joined: Sun Dec 31, 2006 11:56 am
Location: Russia

Post by artie » Sun Dec 31, 2006 12:02 pm

Giorgi wrote:there is no critical input. what algorithm did you use?
Hi. I am newcomer in c++ language. I got ac in the contest with pascal, but same algorithm in c++ got wa. I wish somebody explain me, what is wrong in c++ code:

Code: Select all

got AC
Last edited by artie on Mon Jan 01, 2007 5:23 am, edited 1 time in total.

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

Post by helloneo » Sun Dec 31, 2006 12:18 pm

artie wrote:Hi. I am newcomer in c++ language. I got ac in the contest with pascal, but same algorithm in c++ got wa. I wish somebody explain me, what is wrong in c++ code:
Taking input is faulty..
I don't know exactly what it is.. but try this..

Code: Select all

scanf("%d", &t);
gets(s);
while (t--) {
    gets(s);
    ...
    ...
}

artie
New poster
Posts: 8
Joined: Sun Dec 31, 2006 11:56 am
Location: Russia

Post by artie » Sun Dec 31, 2006 12:43 pm

helloneo wrote:
artie wrote:Hi. I am newcomer in c++ language. I got ac in the contest with pascal, but same algorithm in c++ got wa. I wish somebody explain me, what is wrong in c++ code:
Taking input is faulty..
I don't know exactly what it is.. but try this..

Code: Select all

scanf("%d", &t);
gets(s);
while (t--) {
    gets(s);
    ...
    ...
}
Thanks a lot!
Could anyone explain me why my input was faulty?

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sun Dec 31, 2006 1:00 pm

It is a known problem. You cannot mix scanf and gets . Use scanf or gets but not both in the same program.

What happens is scanf("%d",&t) reads an integer and then stops. So the buffer has \n . now when gets reads it gets an empty line. Also don't use gets use fgets . Don't mix fgets and scanf . Use fgets and then use strtoul for integer conversion

http://c-faq.com/stdio/scanfinterlace.html

Karim
New poster
Posts: 7
Joined: Sun Sep 24, 2006 4:11 pm

Post by Karim » Sun Dec 31, 2006 1:12 pm

Can u Explain your algorithm ..???

Thanks

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

Post by emotional blind » Sun Dec 31, 2006 1:31 pm

there is a recurence relation

largest(i,j) // largest pelindrom in between index i and j including i and j
= 1, where i=j
= largest(i+1,j-1)+2, where i!=j and string==string[j]
= max( largest(i+1,j), largest(i,j-1) )

hope it helps

Post Reply

Return to “Volume 111 (11100-11199)”