11548  Blackboard Bonanza
Moderator: Board moderators

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
11548  Blackboard Bonanza
Hi everybody...
I submitted this program on the online contest. i thing i got the correct algorithm(longest common substring). but i get WA. can anyone pls give some test case so that i can test my code.
M H Rasel
CUET OLD SAILOR
I submitted this program on the online contest. i thing i got the correct algorithm(longest common substring). but i get WA. can anyone pls give some test case so that i can test my code.
M H Rasel
CUET OLD SAILOR
Re: 11548  Blackboard Bonanza
It does not have to be contiguous!! You can skip letters. LCS is not the right algo!!!
Code: Select all
1
2
BOBALICALICBBBOBALICALICBBBOBALICALICBB
BOBALICEALICBOBALICEALICBOBALICEALICBOBALICEALICBOB
Code: Select all
15
Re: 11548  Blackboard Bonanza
My complexity for each case is N^4 and this just passes the time limit!
Does anyone have any solution with N^3?
Does anyone have any solution with N^3?
Re: 11548  Blackboard Bonanza
i found i can't understand this problem.
Re: 11548  Blackboard Bonanza
Sorry to hear that, it wasn't our intention at all. We had a simple statement initially, then it changed as testers were finding ambiguities... and ended up being the mess it is right now.wahaha wrote: i found i can't understand this problem.
The original statement was something like: Given N strings, find two that can give you the largest number of matched characters between them if you write one underneath the another. You can see that there are so many problems with that statement but, in retrospect, it would have been less confusing if we just left it that way.
@Sohel: Intended solution was O(n^4), I think that the time limits on UVa are set at twice the running times of our Java solutions (plenty of time for everyone).
Re: 11548  Blackboard Bonanza
First of all. Nice problem. However the problem statement is not completely correct, or the solution/ test cases are not.
"What is the maximum number of candies that one of Alice and Bob will get in a turn?"
"WILL GET" implies that no matter how the randomness of the words in the bag occurs
they have a strategy which can ensure that they get this maximum number !!!
Even worse, is the sample cases fits this direct reading of the problem, which
is you draw randomly. So you have to solve for worst case scenario, not best.
I don't want to be harsh. It is a good problem, but requires more guessing.
If it's just a simple statement, it will be easier to understand.
"What is the maximum number of candies that one of Alice and Bob will get in a turn?"
"WILL GET" implies that no matter how the randomness of the words in the bag occurs
they have a strategy which can ensure that they get this maximum number !!!
Even worse, is the sample cases fits this direct reading of the problem, which
is you draw randomly. So you have to solve for worst case scenario, not best.
I don't want to be harsh. It is a good problem, but requires more guessing.
If it's just a simple statement, it will be easier to understand.
Last edited by baodog on Sun Nov 02, 2008 11:45 pm, edited 1 time in total.
Re: 11548  Blackboard Bonanza
I agree that it is a different problem. I guess things got "lost in translation" along the way, I had this in my original problem statement: "For each test case, print the maximum number of candies either Alice or Bob can get in a single turn."
Now I understand why people complained during our local contest
We caught a couple of these during the contest, but missed this one.
Sorry about that  problem statement should be changed, for sure.
Now I understand why people complained during our local contest
We caught a couple of these during the contest, but missed this one.
Sorry about that  problem statement should be changed, for sure.
Re: 11548  Blackboard Bonanza
Darko wrote:Sorry to hear that, it wasn't our intention at all. We had a simple statement initially, then it changed as testers were finding ambiguities... and ended up being the mess it is right now.wahaha wrote: i found i can't understand this problem.
The original statement was something like: Given N strings, find two that can give you the largest number of matched characters between them if you write one underneath the another. You can see that there are so many problems with that statement but, in retrospect, it would have been less confusing if we just left it that way.
@Sohel: Intended solution was O(n^4), I think that the time limits on UVa are set at twice the running times of our Java solutions (plenty of time for everyone).
hi, i think that if there are ambiguities, we should give out some more sample input & output , even some hints. i think it requires more for problem author than problem solver.
i think we could do something better.

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
Re: 11548  Blackboard Bonanza
some one can tell me about the algorithm that can solve this problem.....?
Re: 11548  Blackboard Bonanza
Simple bruteforce is enough to pass the time limit!Master wrote:some one can tell me about the algorithm that can solve this problem.....?

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
Re: 11548  Blackboard Bonanza
can anyone give me some test case. i am getting WA....

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
11548  Blackboard Bonanza
Hi can anyone give me some input. i am using a N^3 solution (for solving a single case) but i am getting WA.......
Thanks in advance
Thanks in advance
Re: 11548  Blackboard Bonanza  some critical input require...
Search the board first, and use existing thread.
Ami ekhono shopno dekhi...
HomePage
HomePage

 Experienced poster
 Posts: 136
 Joined: Sat Nov 29, 2008 8:01 am
 Location: narayangong,bangladesh.
 Contact:
11548  Blackboard Bonanza
Can anyone explain the problem in clear statement??What is needed to find out??
plz someone help.longest non contiguious common substring between string[1]<>string[2], string[2]<>string[3],string[3]<>string[4],..........string[n1]<>string[n] and then take the maximum matching among them??Or what??
Life is more complicated than algorithm.
http://felixhalim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
http://felixhalim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
Re: 11548  Blackboard Bonanza
Find the longest common substring between every pair of strings and then report the maximum amongst these!