10788 - Parenthesizing Palindromes

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

Moderator: Board moderators

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

10788 - Parenthesizing Palindromes

Post by w k » Sat Dec 04, 2004 10:24 pm

Hi,

The problem description says that the expression ``abbaddcc" has only one interpretation: ``(ab ba) (d d) (c c)". Is it true?
How about this interpretation:
(a(bb)a)(dd)(cc) ?

Wojciech

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: 10788

Post by misof » Sun Dec 05, 2004 1:04 am

w k wrote:Hi,

The problem description says that the expression ``abbaddcc" has only one interpretation: ``(ab ba) (d d) (c c)". Is it true?
How about this interpretation:
(a(bb)a)(dd)(cc) ?

Wojciech
In this problem, these two interpretations are considered to be the same. The problem statement is a little bit vague on what "interpretations" do we consider.

I offer my definition: for a string, an interpretation is a well-formed string of parenthesis of the same length, such that for each pair of parenthesis the corresponding two letters of the string are the same.

E.g. the string abbaddcc has only one interpretation:

Code: Select all

abbaddcc
(())()()
Does this help you?

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Wed Dec 08, 2004 8:50 pm

Hi,

I believe Your definition is correct.
Is Your code AC?
If yes - they should change the problem description according to Your definition, I think.

Wojciech

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Dec 09, 2004 2:57 am

Yes, my code is AC. But I think that my explanation gives away a little bit more than the author intended -- in other words, it pushes you in the right direction of thinking. And anyway, nobody has got the time to fix the problem statement. There are far worse problem statements out there that have to be fixed. And for minor details there is exactly this board. :)

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Thu Dec 09, 2004 5:48 pm

Hmm... I admit that the statement is not that clear. Md Kamruzzaman, the author of the alternate solution for this problem, had pointed out this anomaly with the statement before it was used for the contest. But I was reluctant to make any change. Misof is right, if I were too specific then it would have given away much of the problem. It was not my intent.

I think I did mention these things in the form of an example in the problem statement. It worked fine for many. But that doesn't certify the problem statement to be clear. I am aware of that.

However, I am still against changing the problem statement. I hope the sufferers would take it lightly. :)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Dec 12, 2004 6:44 pm

Hi

I wonder if there are blank lines in the input? What is the expected output for those cases:
14
aaabba
aabb
bbababba

aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb
abcdefgabcdefg
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvww
accffbbaccxxpqqrrp
aa
a
aba
abba
dddddddddddddddddddd
ddddddddddddddddddddd
Is this right?
Case 1: Valid, Multiple
Case 2: Valid, Unique
Case 3: Invalid
Case 4: Valid, Unique
Case 5: Valid, Multiple
Case 6: Invalid
Case 7: Valid, Unique
Case 8: Valid, Unique
Case 9: Valid, Unique
Case 10: Invalid
Case 11: Invalid
Case 12: Valid, Multiple
Case 13: Valid, Multiple
Case 14: Invalid

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Mon Dec 13, 2004 5:14 am

There is no empty string in the input because I use scanf("%s", s) and got AC.
And the output of your case 12(abba) should be "Valid, Unique".

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Dec 13, 2004 3:58 pm

How could it be that abba has only one interpretation? Can't we write it as (ab ba) or (a (b b) a)?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Dec 13, 2004 4:30 pm

Krzysztof Duleba wrote:How could it be that abba has only one interpretation? Can't we write it as (ab ba) or (a (b b) a)?
Try reading the previous posts on this page. 8)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Dec 13, 2004 4:49 pm

misof wrote:Try reading the previous posts on this page. 8)
Yes, that should be helpful. Somehow I didn't notice your previous post - sorry.

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Can any one give me any Critical test case ?

Post by Niaz » Sat Dec 18, 2004 2:56 pm

Can any one give me any Critical test case ?
I am trying to solve this problem and getting WA again and again. I may miss some thing from the problem. Please give me some input and output so that I can fix my BUG :(

Thanks in advance.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

sq
New poster
Posts: 3
Joined: Sun Jan 02, 2005 9:15 am

Post by sq » Sun Jan 02, 2005 9:18 am

Hi, are there any more test cases? I've tried the sample input and the test cases in this thread, but still can't get it accepted.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Jan 04, 2005 9:00 am

Hi, try these important cases:
2
abckkkkkcba
abbkkbba
the answer:
Case 1: Valid, Multiple
Case 2: Valid, Multiple

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Jan 04, 2005 9:23 am

Try this case, I used it to debug my program:

Code: Select all

1
abaaba

Code: Select all

Case 1: Valid, Unique

sq
New poster
Posts: 3
Joined: Sun Jan 02, 2005 9:15 am

Post by sq » Mon Jan 17, 2005 8:31 pm

shamim wrote:Hi, try these important cases:
2
abckkkkkcba
abbkkbba
the answer:
Case 1: Valid, Multiple
Case 2: Valid, Multiple
Hi~ Shouldn't abckkkkkcba be Invalid? (It has a singled k)

Post Reply

Return to “Volume 107 (10700-10799)”