Page 1 of 3

### 10313 - Pay the Price

Posted: Tue Jul 02, 2002 6:01 am
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.

Posted: Tue Jul 02, 2002 6:43 am
long is not enough, use long long. Ofcourse u may have other mistakes

Posted: Tue Jul 02, 2002 8:17 am
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))?

Posted: Tue Jul 02, 2002 8:44 am

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 numberofcoins-1 from the last coin, and have gone
though numberofcoins-1 permutations.
The example above illustrates this.
To actually implement it, we just keep track of the last 2 coins.
we subtract numberofcoins-1 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...

Posted: Tue Jul 02, 2002 12:54 pm
Your algorithm seems quite correct to me, but I think there are some critical points:

In how many ways can 0\$ be made up by 0 coins? 0 or 1?
In how many ways can more than 0\$ be made up by 0 coins? 0 or 1?

Posted: Tue Jul 02, 2002 1:07 pm
I'm not sure (haven't solve this problem yet) but I think that broderic's algorithm is wrong. For this input:
100 10 10

Broderic's programs outputs:
82

But I think that correct output must be 2977866...

Posted: Tue Jul 02, 2002 1:38 pm
Ok.I posted some correct test cases (as I and Judge think )
InPut

Code: Select all

``````100 10 10
100
200
200 30 75
200 111 199
300
299 88 1000
47 7 709``````
OutPut

Code: Select all

``````2977866
190569292
3972999029388
1147203119198
409038375
9253082936723602
122368041480637
117650``````

Posted: Tue Jul 02, 2002 5:13 pm
hehe, well, i'm obviously wrong.
not only that, i'm apparently waaay wrong.

could anybody give me a hint as to how i should

(for some reason, that 2977866 looks like a really familiar number.
I can't remember where i've seen it before though )

Posted: Tue Jul 02, 2002 6:01 pm
2Revenger: Can you recheck your output? I've got same results as yours except fourth case, my (rejected) solution outputs 2347163627458 but yours 1147203119198. I can't understand is this my bug or just your mistype?

Posted: Tue Jul 02, 2002 6:08 pm
i think Ivan Golubev is right about the '200 30 75'
input:

Code: Select all

``````0
0 0
0 1
0 0 0
0 0 1
0 1 1
0 1 2
200 30 75
``````
output:

Code: Select all

``````1
1
1
1
1
0
0
2347163627458
``````

Posted: Tue Jul 02, 2002 7:12 pm
It's my mistake... sorry

Posted: Tue Jul 02, 2002 9:11 pm
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))?
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.

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.

Posted: Tue Jul 02, 2002 11:54 pm
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

Posted: Wed Jul 03, 2002 2:03 am
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?

Posted: Wed Jul 03, 2002 11:28 am
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?