10788 - Parenthesizing Palindromes
Moderator: Board moderators
10788 - Parenthesizing Palindromes
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
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
Re: 10788
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.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
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
(())()()
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.
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.
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.
K M Hasan
http://www.cs.umanitoba.ca/~kmhasan/
http://www.cs.umanitoba.ca/~kmhasan/
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
Hi
I wonder if there are blank lines in the input? What is the expected output for those cases:
I wonder if there are blank lines in the input? What is the expected output for those cases:
Is this right?14
aaabba
aabb
bbababba
aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb
abcdefgabcdefg
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvww
accffbbaccxxpqqrrp
aa
a
aba
abba
dddddddddddddddddddd
ddddddddddddddddddddd
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
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
-
- 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 ?
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.
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/
http://groups.yahoo.com/group/acm_solver/
-
- Experienced poster
- Posts: 151
- Joined: Tue Nov 16, 2004 7:23 pm
- Location: Norway
- Contact:
Try this case, I used it to debug my program:
Code: Select all
1
abaaba
Code: Select all
Case 1: Valid, Unique