10313 - Pay the Price

[Joe Smith]

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]

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[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?

[Joe Smith]

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

[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

[Joe Smith]

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]

Thank you very much Now I get Accepted for 1 second

[Christian Schuster]

Thank you!

[xenon]

Thanx mate,

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

-xenon

[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

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

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

[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

[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

[LittleJohn]

Hi, Dmytro_Chernysh:
I think the answer of "30 0 0" should be 0.

[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?