11259 - Coin Changing Again

All about problems in Volume 112. 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
coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

11259 - Coin Changing Again

Post by coolguy » Sat Aug 04, 2007 4:09 pm

I tried DP but got TLE.
what could a better algorithm for this problem?
please help.
the complexity of my algorithm for each query is O( 4 * v + 4 * v ) .
In good company

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

Post by RoBa » Sat Aug 04, 2007 5:55 pm

I think there needs something like Generating Function, but I don't know how. :(

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Sat Aug 04, 2007 6:23 pm

Hmm... I don't know either... The only thing I am pretty sure about is that
DP probably won't pass no matter how hard you try. :)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Aug 04, 2007 7:44 pm

I thought about generating function, but I don't see how to compute it fast enough.

For example, we have 3 $1, 2 $2, 3 $5 and 1 $10, then we can represent it as the polynomial (1+x+x^2+x^3)*(1+x^2+x^4)*(1+x^5+x^10+x^15)*(1+x^10). And the coefficient of x^d in the expanded form is the number of ways to make $d .

Well, the idea is to represent the polynomial as a difference of 2 infinite series. The dp solution will be able to find the coefficient for an infinite series easily.

Inclusion-exclusion finishes off the problem.
Last edited by sclo on Sun Aug 05, 2007 7:18 am, edited 2 times in total.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Aug 04, 2007 10:29 pm

A little hint: You should be able to answer each query in O(2^W) based on the result of a DP, where W is the number of coins, which is always 4 in this problem.

i.e. After running a DP, you should answer each query in almost constant time.
I code, therefore I am.

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

Post by RoBa » Sun Aug 05, 2007 6:53 pm

Cho wrote:A little hint: You should be able to answer each query in O(2^W) based on the result of a DP, where W is the number of coins, which is always 4 in this problem.

i.e. After running a DP, you should answer each query in almost constant time.
I still can't understand. Could you please explain in more details?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Aug 05, 2007 7:00 pm

Use principle of inclusion-exclusion to answer queries.

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

Post by RoBa » Sun Aug 05, 2007 7:10 pm

mf wrote:Use principle of inclusion-exclusion to answer queries.
er... Is it something like this :

If we call 4 kinds of coins A, B, C and D. Then for each query, we calcuate (the number of ways using A) + (the number of ways using B) + (the number of ways using C) + (the number of ways using D) - (the number of ways using A and B) - (the number of ways using A and C) - ... + (the number of ways using A and B and C) + ... - (the number of ways using A and B and C and D)

But how to find these (the number of ways using A and B), (the number of ways using B and C and D)...?
Let it be

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Aug 05, 2007 7:28 pm

For two coins it's something like this:

Let N be the total number of ways of obtaining value v using the given coin denominations,
let N1 and N2 be the number of ways, in which the first or second coin is used more than d[1] or d[2] times, respectively,
let N12 be the number of ways in which the first coin is used more than d[1] times, and the second coin is used more than d[2] times.
Then the number of ways in which no coin is used more times than necessary is: N - N1 - N2 + N12.

How to compute these N's:
N1 = number of ways in which the first coin is used more than d[1] times, by definition. So, use the first coin d[1]+1 times, and find the number of ways to obtain the remaining value.

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

Post by RoBa » Sun Aug 05, 2007 7:46 pm

Got it. Thanks very much! :)
Let it be

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Sun Sep 09, 2007 7:26 am

I get too many WR.
Sample I/O plz.........

Thanks
keep posting.

Sapnil.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Sep 09, 2007 7:40 am

Did you use long long int?

It's necessary for solving it.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Mon Sep 10, 2007 3:23 am

Thanks chen,I don't think about this case.........
But there are some mistake in my code.

Thanks
keep posting.

Sapnil.

Post Reply

Return to “Volume 112 (11200-11299)”