10313  Pay the Price
Moderator: Board moderators
10313  Pay the Price
can anybody give me a case where this fails, or help me
find the bug?
I'm pretty sure my algorithm is correct. however, what's the output
for n=0 supposed to be? (i tried 0 and 1, but got WA both times. )
Thanks for any help.
find the bug?
I'm pretty sure my algorithm is correct. however, what's the output
for n=0 supposed to be? (i tried 0 and 1, but got WA both times. )
Thanks for any help.
Last edited by broderic on Fri Aug 02, 2002 5:29 pm, edited 1 time in total.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Reply
long is not enough, use long long. Ofcourse u may have other mistakes
well, what i did was this.
say you want to sum to 10 with 4 coins.
you can do it this way: (1,1,1,7), (1,1,2,6),(1,2,2,5),(2,2,2,4),(2,2,3,3).
every other way is just a permutation of the above. (from the
example given in the problem i assumed we don't count permutations).
so in this case there are 5 ways to do it.
my code above simulates this by noting that if we add 1 to all the
coins except the last in turn, while subtracting 1 from the last coin each time, we've subtracted numberofcoins1 from the last coin, and have gone
though numberofcoins1 permutations.
The example above illustrates this.
To actually implement it, we just keep track of the last 2 coins.
we subtract numberofcoins1 from the last and add 1 to the
second last until the
difference between the 2nd last and last coin is small
(ie, < numberofcoins 1), then we figure out how many are
actually left.
i think this is correct, but I keep getting WA.
one reply above implied that the number of ways is too large for an int. The largest number my code generates is ~40000.
Maybe somebody who got there's accepted could post some
cases with the correct output?
The code runs in 0.5 seconds.
If my algorithm is wrong, somebody please tell me now.
any input would be appreciated. I feel like i've made a really
dumb mistake...
say you want to sum to 10 with 4 coins.
you can do it this way: (1,1,1,7), (1,1,2,6),(1,2,2,5),(2,2,2,4),(2,2,3,3).
every other way is just a permutation of the above. (from the
example given in the problem i assumed we don't count permutations).
so in this case there are 5 ways to do it.
my code above simulates this by noting that if we add 1 to all the
coins except the last in turn, while subtracting 1 from the last coin each time, we've subtracted numberofcoins1 from the last coin, and have gone
though numberofcoins1 permutations.
The example above illustrates this.
To actually implement it, we just keep track of the last 2 coins.
we subtract numberofcoins1 from the last and add 1 to the
second last until the
difference between the 2nd last and last coin is small
(ie, < numberofcoins 1), then we figure out how many are
actually left.
i think this is correct, but I keep getting WA.
one reply above implied that the number of ways is too large for an int. The largest number my code generates is ~40000.
Maybe somebody who got there's accepted could post some
cases with the correct output?
The code runs in 0.5 seconds.
If my algorithm is wrong, somebody please tell me now.
any input would be appreciated. I feel like i've made a really
dumb mistake...

 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
Ok.I posted some correct test cases (as I and Judge think )
InPut
OutPut
InPut
Code: Select all
100 10 10
100
200
200 30 75
200 111 199
300
299 88 1000
47 7 709
Code: Select all
2977866
190569292
3972999029388
1147203119198
409038375
9253082936723602
122368041480637
117650
Last edited by Revenger on Tue Jul 02, 2002 5:29 pm, edited 1 time in total.

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
i think Ivan Golubev is right about the '200 30 75'
input:
output:
input:
Code: Select all
0
0 0
0 1
0 0 0
0 0 1
0 1 1
0 1 2
200 30 75
Code: Select all
1
1
1
1
1
0
0
2347163627458
If your algorithm is really O(n^3) then you must be doing something inefficiently, because 300^3 is only 27 million, which should easily run in way less than 30s if each of the 27m operations are simple enough.Revenger wrote:I just wonder how the program can work less than 2 seconds. My program work 29.530 seconds and get Accepted. But I have no idea how to optimaze it. Can anyone give me a hint to make a good fast program?
P.S. I use DP. My algorithm is O(n^3). May be exist a algorithm O(n^2 (log n))?
But, you can solve it in O(n^2)... you only need to fill a 300x300 array, where A[j] is the # of ways of getting $i total dollars where all the coins are of value at most j.
heh, i don't know what i was thinking earlier.
the algorithm i posted above misses all sorts of possible ways...
for instance: (1,1,1,10),(1,1,2,9),(1,2,2,8),(2,2,2,7)...but this misses (1,1,3,8),(1,1,4,7),... doh!
anyway, i know how to do it now.
Sheesh, seems like i've been making a lot of mistakes like this lately. :)
Broderick
the algorithm i posted above misses all sorts of possible ways...
for instance: (1,1,1,10),(1,1,2,9),(1,2,2,8),(2,2,2,7)...but this misses (1,1,3,8),(1,1,4,7),... doh!
anyway, i know how to do it now.
Sheesh, seems like i've been making a lot of mistakes like this lately. :)
Broderick
Joe Smith wrote: But, you can solve it in O(n^2)... you only need to fill a 300x300 array, where A[j] is the # of ways of getting $i total dollars where all the coins are of value at most j.
I have a problem...
I did use O(n^2) space complexity, but although I maintain A[300][300],
I still need to use O(n^3) time complexity to compute all the values in A[][]..can you tell me how did you fill the array in O(n^2) time?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany