11548 - Blackboard Bonanza

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

sohel · 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 · Post by **wahaha** » Sun Nov 02, 2008 4:10 pm

i found i can't understand this problem.

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

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

Darko · 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 · Post by **wahaha** » Mon Nov 03, 2008 1:06 pm

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 · Post by **Master** » Tue Nov 04, 2008 7:47 am

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

sohel · 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 · Post by **Master** » Tue Nov 04, 2008 12:53 pm

can anyone give me some test case. i am getting WA....

Master · 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 · Post by **Jan** » Mon Dec 22, 2008 1:40 pm

Search the board first, and use existing thread.

sazzadcsedu · 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.

sohel · 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!

OJ Board