## 10313 - Pay the Price

Moderator: Board moderators

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 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.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
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?

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
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.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
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 Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
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]

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
Thank you very much Now I get Accepted for 1 second   Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
Thank you! xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
Thanx mate,

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

-xenon

20571KJ
New poster
Posts: 7
Joined: Sat Jul 13, 2002 6:15 pm
Contact:

### 10313 Pay the price.

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

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:
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)

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### Explanation

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

### Right solution, BUT...

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

### Right solution, BUT...

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

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Hi, Dmytro_Chernysh:
I think the answer of "30 0 0" should be 0. GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:
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?
_-(GPI)-_

"Finally I have freed myself from the clutches of the garbage fairy!"