11259 - Coin Changing Again

coolguy · 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 ) .

RoBa · 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 · 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 · 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.

Cho · 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.

RoBa · 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 · Post by mf » Sun Aug 05, 2007 7:00 pm

Use principle of inclusion-exclusion to answer queries.

RoBa · 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)...?

mf · 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 · Post by **RoBa** » Sun Aug 05, 2007 7:46 pm

Got it. Thanks very much!

sapnil · 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 · 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 · 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.