Page 2 of 3
Posted: Thu Jul 04, 2002 3:40 am
Adrian Kuegel wrote:Joe, are you sure you solve it in O(n^2)? Because I thought my algorithm is O(n^3), but my program is faster than your program. Did you also sum up the values of the matrix and store them?
Yes, I only have an NxN array which I memoize on, and each value is computed from other values in O(1) time, so it's O(n^2) at most. The slowness was because of some prewritten code to read the input (I parsed each line into a vector<int>... which I allocated *inside* my loop, so lots of overhead). I just replaced that with sscanf and resubmitted and I now have the fastest time. If you're using O(n^3) but only have an O(n^2) array (like dh3014), then maybe you are probably trying to do it iteratively. For DP problems sometimes I find it's easier to come up with the best recurrence if I think about a memoization solution. Here's the recurrence I used:

*SPOILER*

ways[value][coin] = ways[value-coin][coin] + ways[value][coin-1]

Where value is the sum you're trying to make, and coin is the biggest coin you're allowed to use.

Posted: Thu Jul 04, 2002 8:12 am
Formula

Code: Select all

``Ways[i,j]=Ways[i,j-1]+Ways[i-j,j]``
is known by almost everybody (as I think). Although I wanted to use this formula in the contest, but I have a big problem: This formula only count the ways in which the biggest coin is equal to j; but how can I count the ways in which the number of coin is used. I have an idea about this, but this idea need a array of 64-bit integers. So, it is not O(n^2) but O(n^3) and program need more than 32 MB of memory.
Can you give me a hint how to use this formula in more effective way?

Posted: Thu Jul 04, 2002 5:00 pm
Revenger wrote:Formula

Code: Select all

``Ways[i,j]=Ways[i,j-1]+Ways[i-j,j]``
is known by almost everybody (as I think). Although I wanted to use this formula in the contest, but I have a big problem: This formula only count the ways in which the biggest coin is equal to j; but how can I count the ways in which the number of coin is used. I have an idea about this, but this idea need a array of 64-bit integers. So, it is not O(n^2) but O(n^3) and program need more than 32 MB of memory.
Can you give me a hint how to use this formula in more effective way?
Actually, with this formula ways[i,j] is the ways in which the biggest coin is *less than* or equal to j... not just equal. That's all you need, I'm not sure I understand the problem you're having.

Posted: Thu Jul 04, 2002 5:28 pm
You wrote :
Actually, with this formula ways[i,j] is the ways in which the biggest coin is *less than* or equal to j... not just equal. That's all you need, I'm not sure I understand the problem you're having.
I mean that,

1. Ways[i,j] - is the number of ways to pay i dollars using coins less or equal to j dollars

2. I_need[i,j] - is the number of ways to pay i dollars using j coins

And I don't know how to get I_need if I only count Ways

Hope, that you will understand me Posted: Thu Jul 04, 2002 11:20 pm
Revenger wrote:You wrote :
Actually, with this formula ways[i,j] is the ways in which the biggest coin is *less than* or equal to j... not just equal. That's all you need, I'm not sure I understand the problem you're having.
I mean that,

1. Ways[i,j] - is the number of ways to pay i dollars using coins less or equal to j dollars

2. I_need[i,j] - is the number of ways to pay i dollars using j coins

And I don't know how to get I_need if I only count Ways

Hope, that you will understand me Oops, sorry, I just realized my explanation didn't make sense... I left out the most important detail. The number of ways of making \$i with coins of value \$j or less is the same as the # of ways of making \$i with at most j coins. This is a property of integer partitions (splitting a number into a sum of smaller numbers), which is basically what we're dealing with. i.e., the number of partitions of n with <= k parts (in the sum) is equal to the number of partitions of n where each part is <= k.

The proof is to draw the partition as what's called a Ferrer's diagram. Let's take 1+1+1+3+3+4 = 13 as an example:

XXXX
XXX
XXX
X
X
X

Well, if you transpose this (like a matrix) you get:

XXXXXX
XXX
XXX
X

Which is the partition 6+3+3+1. It isn't hard to see that, in general, if all of the parts in the sum are <= j, then the transpose has <= j parts. So the ways[i,j] is all you need. For the sample input I just do this:

6
ways[6,6] = 1

6 3
ways[6,3] = 7

6 2 5
ways[6,5] - ways[6,1] = 10 - 1 = 9

6 1 6
ways[6,6] - ways[6,0] = 11 - 0 = 11

I hope this helps.
[/b]

Posted: Fri Jul 05, 2002 10:16 am
Thank you very much Now I get Accepted for 1 second   Posted: Fri Jul 05, 2002 11:15 am
Thank you! Posted: Fri Jul 05, 2002 12:40 pm
Thanx mate,

I didn't have a clue on how to bring down execution times, but your discussion is very illusive!

-xenon

### 10313 Pay the price.

Posted: Tue Jul 16, 2002 6:10 pm
i used DP to solve this problem. The complexity: n*n*V.
It's really too slow. Please show me if u have a better algorithm.
Thanks you

Posted: Tue Jul 16, 2002 6:38 pm
Please, see the previous articles in this Volumn.
Joe Smith has provided a great way to solve the problem and the complexity is O(n^2)

### Explanation

Posted: Fri Oct 11, 2002 10:03 pm
So the formula
A(i, j) = A(i, j-1) + A(i-j, j)
works both for
no of ways of making \$i with coins of maximum value \$j
and
no of ways of making \$i with maximum j coins.
Here are two different interpretation.

For the first
A(i, j) = A(i, j-1) + A(i-j, j)
so A(i, j) is either the no. of ways to of makin \$i with coins of maximum value \$j-1 -> A(i, j-1) or we force one coin to be j and add the number of ways of making i-j\$ with max value \$j. Easy

For the second
A(i, j) = A(i, j-1) + A(i-j, j)
Either we have j-1 coins -> A(i, j-1), either we have j coins in which case we substract 1\$ from the value of each coin (since there are j coins with positive values) and reduce the problem to a smaller one -> A(i-j, j).

### Right solution, BUT...

Posted: Mon Apr 28, 2003 9:50 pm
My program does passes all test cases listed in this , even these...
0
0 0
0 1
0 0 0
0 0 1
0 1 1
0 1 2
200 30 75
But still WA... May be .... this is wrong
20 20 20
300 300 300
or
30 0 0

### Right solution, BUT...

Posted: Mon Apr 28, 2003 10:16 pm
My program does passes all test cases listed in this , even these...
0
0 0
0 1
0 0 0
0 0 1
0 1 1
0 1 2
200 30 75
But still WA... May be .... this is wrong
20 20 20
300 300 300
I think the answer of "30 0 0" should be 0. 