## 11548 - Blackboard Bonanza

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

Moderator: Board moderators

Master
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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 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
``````

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 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?

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11548 - Blackboard Bonanza

i found i can't understand this problem.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: 11548 - Blackboard Bonanza

wahaha wrote: 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).

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 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.
Last edited by baodog on Sun Nov 02, 2008 11:45 pm, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

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

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11548 - Blackboard Bonanza

Darko wrote:
wahaha wrote: 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).

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.

Master
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.....?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11548 - Blackboard Bonanza

Master wrote:some one can tell me about the algorithm that can solve this problem.....?
Simple bruteforce is enough to pass the time limit!

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

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

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

Search the board first, and use existing thread.
Ami ekhono shopno dekhi...
HomePage

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 11548 - Blackboard Bonanza

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.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359