10313 - Pay the Price

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post by Joe Smith » 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.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » 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[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
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post by Joe Smith » 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[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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » 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 :wink:

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post by Joe Smith » 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 :wink:
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

Post by Revenger » Fri Jul 05, 2002 10:16 am

Thank you very much :D Now I get Accepted for 1 second :D :D :D

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Fri Jul 05, 2002 11:15 am

Thank you! :)

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » 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

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

10313 Pay the price.

Post by 20571KJ » 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

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » 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)

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

Explanation

Post by scythe » 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).

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

Right solution, BUT...

Post by Dmytro Chernysh » 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
answer in 1???
or
30 0 0
answer in 1???

Help me please

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

Right solution, BUT...

Post by Dmytro Chernysh » 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
answer in 1???
or
30 0 0
answer in 1???

Help me please

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Tue May 06, 2003 8:31 am

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

User avatar
GreenPenInc
Learning poster
Posts: 53
Joined: Sat May 01, 2004 9:31 pm
Contact:

Post by GreenPenInc » Thu Jul 15, 2004 9:47 pm

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!"

Post Reply

Return to “Volume 103 (10300-10399)”