10860 - Many a Little makes a Mickle

[cypressx]

Hello. This looks like a pretty easy DP problem , but is there any nasty corner case ? I can`t find the mistake in my code. Thank you in advance for your replies.

Code: Select all

[stubbscroll]

You should erase the V array between each input. Your code returns wrong answer on the second case of this input:

Code: Select all

2
abc
3
a
b
c
abc
3
a
b
d

On the last case, your code outputs 3 instead of "Not possible".

[cypressx]

Thank you for your prompt reply

Unfortunately , this seems not to be the only problem in my code

Sometimes it`s really hard to get AC in uva

[stubbscroll]

From the problem statement:

c. Each use of a short string or its reverse would be counted as one occurance of that short string

You are not checking the reverse of the strings. I didn't see this bug in your code earlier.

Try this test case:

Code: Select all

1
ab
1
ba

Answer should be 1, your code outputs "Not possible."

[cypressx]

Thank you very much !
This was the last error in my code and now it is AC

[Tomislav Novak]

Hi.
What is the complexity of the DP algorithm for this problem? Only thing I can think of would be O(length(P)*N*length(Pi)), which seems too much for the given constrains. Is there something I haven't considered?

[sohel]

Eventhough, O(length(P)*N*length(Pi)) is too high, but unfortunately there isn't any judge data where all three( P, N, Pi) are to the limit.

That means your method should pass the time limit !!

The contest was held almost a year ago, and it's kinda surprising that this kind of post arrived after a very long time.

[Moha]

It seems that this problem is very easy, But i can`t get it.
this is my code can anybody tell me what is wrong with it?

Code: Select all

Code removed

EDIT: ! didn't print '.' after the answer!!