## 11259 - Coin Changing Again

Moderator: Board moderators

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

### 11259 - Coin Changing Again

I tried DP but got TLE.
what could a better algorithm for this problem?
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
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
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
Contact:
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.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
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:
Use principle of inclusion-exclusion to answer queries.

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 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:
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 or d times, respectively,
let N12 be the number of ways in which the first coin is used more than d times, and the second coin is used more than d 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 times, by definition. So, use the first coin d+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
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:
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
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: