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

Post by Master » Sun Nov 02, 2008 9:51 am

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

Post by baodog » Sun Nov 02, 2008 9:54 am

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

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

Re: 11548 - Blackboard Bonanza

Post by sohel » Sun Nov 02, 2008 1:36 pm

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

Post by wahaha » Sun Nov 02, 2008 4:10 pm

:o i found i can't understand this problem.

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

Re: 11548 - Blackboard Bonanza

Post by Darko » Sun Nov 02, 2008 9:32 pm

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

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

Re: 11548 - Blackboard Bonanza

Post by baodog » Sun Nov 02, 2008 10:28 pm

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
Location: Calgary, Canada

Re: 11548 - Blackboard Bonanza

Post by Darko » Sun Nov 02, 2008 11:30 pm

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

Post by wahaha » Mon Nov 03, 2008 1:06 pm

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:

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Re: 11548 - Blackboard Bonanza

Post by Master » Tue Nov 04, 2008 7:47 am

some one can tell me about the algorithm that can solve this problem.....?

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

Re: 11548 - Blackboard Bonanza

Post by sohel » Tue Nov 04, 2008 10:16 am

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

Post by Master » Tue Nov 04, 2008 12:53 pm

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

Post by Master » Tue Nov 18, 2008 7:46 pm

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

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

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

Post by Jan » Mon Dec 22, 2008 1:40 pm

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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

11548 - Blackboard Bonanza

Post by sazzadcsedu » Fri Apr 16, 2010 9:15 am

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
For Hints: http://salimsazzad.wordpress.com

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

Re: 11548 - Blackboard Bonanza

Post by sohel » Fri Apr 16, 2010 11:18 am

Find the longest common substring between every pair of strings and then report the maximum amongst these!

Post Reply

Return to “Volume 115 (11500-11599)”