10860 - Many a Little makes a Mickle

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

Moderator: Board moderators

Post Reply
cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

10860 - Many a Little makes a Mickle

Post by cypressx » Mon Jun 06, 2005 1:50 am

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.
Last edited by cypressx on Wed Jul 27, 2005 7:50 pm, edited 1 time in total.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Mon Jun 06, 2005 4:09 am

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
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Thanks

Post by cypressx » Mon Jun 06, 2005 6:09 pm

Thank you for your prompt reply :wink:

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

Sometimes it`s really hard to get AC in uva

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Jun 07, 2005 3:50 pm

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
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Thanks!!!

Post by cypressx » Tue Jun 07, 2005 5:31 pm

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

User avatar
Tomislav Novak
New poster
Posts: 44
Joined: Fri Feb 20, 2004 5:52 pm

10860 Many a Little makes a Mickle - complexity

Post by Tomislav Novak » Tue Jan 10, 2006 7:44 pm

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?

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

oops

Post by sohel » Wed Jan 11, 2006 4:25 pm

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Mon Jul 31, 2006 7:53 am

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

Post Reply

Return to “Volume 108 (10800-10899)”