Page **2** of **3**

Posted: **Thu Jul 04, 2002 3:40 am**

by **Joe Smith**

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**

by **Revenger**

Formula

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[300][300][300] 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**

by **Joe Smith**

Revenger wrote:Formula

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[300][300][300] 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**

by **Revenger**

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**

by **Joe Smith**

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**

by **Revenger**

Posted: **Fri Jul 05, 2002 11:15 am**

by **Christian Schuster**

Thank you!

Posted: **Fri Jul 05, 2002 12:40 pm**

by **xenon**

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**

by **20571KJ**

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**

by **dh3014**

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**

by **scythe**

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**

by **Dmytro Chernysh**

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

answer in 1???

or

30 0 0

answer in 1???

Help me please

### Right solution, BUT...

Posted: **Mon Apr 28, 2003 10:16 pm**

by **Dmytro Chernysh**

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

answer in 1???

or

30 0 0

answer in 1???

Help me please

Posted: **Tue May 06, 2003 8:31 am**

by **LittleJohn**

Hi, Dmytro_Chernysh:

I think the answer of "30 0 0" should be 0.

Posted: **Thu Jul 15, 2004 9:47 pm**

by **GreenPenInc**

Well, *my* program passes all test cases in this thread, and still I get WA. Any ideas for other test cases? Should I post my code?