11259  Coin Changing Again
Moderator: Board moderators
11259  Coin Changing Again
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 ) .
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
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.
Inclusionexclusion finishes off the problem.
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.
Inclusionexclusion finishes off the problem.
Last edited by sclo on Sun Aug 05, 2007 7:18 am, edited 2 times in total.
I still can't understand. Could you please explain in more details?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.
er... Is it something like this :mf wrote:Use principle of inclusionexclusion to answer queries.
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
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.
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.

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