Page 1 of 2

11548 - Blackboard Bonanza

Posted: Sun Nov 02, 2008 9:51 am
by Master
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

Re: 11548 - Blackboard Bonanza

Posted: Sun Nov 02, 2008 9:54 am
by baodog
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

Posted: Sun Nov 02, 2008 1:36 pm
by sohel
My complexity for each case is N^4 and this just passes the time limit!
Does anyone have any solution with N^3?

Re: 11548 - Blackboard Bonanza

Posted: Sun Nov 02, 2008 4:10 pm
by wahaha
:o i found i can't understand this problem.

Re: 11548 - Blackboard Bonanza

Posted: Sun Nov 02, 2008 9:32 pm
by Darko
wahaha wrote::o i found i can't understand this problem.
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.

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

Posted: Sun Nov 02, 2008 10:28 pm
by baodog
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.

Re: 11548 - Blackboard Bonanza

Posted: Sun Nov 02, 2008 11:30 pm
by Darko
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.

Re: 11548 - Blackboard Bonanza

Posted: Mon Nov 03, 2008 1:06 pm
by wahaha
Darko wrote:
wahaha wrote::o i found i can't understand this problem.
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.

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).

:P 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. :wink:

Re: 11548 - Blackboard Bonanza

Posted: Tue Nov 04, 2008 7:47 am
by Master
some one can tell me about the algorithm that can solve this problem.....?

Re: 11548 - Blackboard Bonanza

Posted: Tue Nov 04, 2008 10:16 am
by sohel
Master wrote:some one can tell me about the algorithm that can solve this problem.....?
Simple bruteforce is enough to pass the time limit!

Re: 11548 - Blackboard Bonanza

Posted: Tue Nov 04, 2008 12:53 pm
by Master
can anyone give me some test case. i am getting WA....

11548 - Blackboard Bonanza

Posted: Tue Nov 18, 2008 7:46 pm
by Master
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

Re: 11548 - Blackboard Bonanza - some critical input require...

Posted: Mon Dec 22, 2008 1:40 pm
by Jan
Search the board first, and use existing thread.

11548 - Blackboard Bonanza

Posted: Fri Apr 16, 2010 9:15 am
by sazzadcsedu
Can anyone explain the problem in clear statement??What is needed to find out??
longest non contiguious common substring between string[1]<->string[2], string[2]<->string[3],string[3]<->string[4],..........string[n-1]<->string[n] and then take the maximum matching among them??Or what??
plz someone help.

Re: 11548 - Blackboard Bonanza

Posted: Fri Apr 16, 2010 11:18 am
by sohel
Find the longest common substring between every pair of strings and then report the maximum amongst these!