Page 1 of 3

10313 - Pay the Price

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

Reply

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

Posted: Tue Jul 02, 2002 8:17 am
by Revenger
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
by broderic
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 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
by Christian Schuster
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
by Ivan Golubev
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
by Revenger
Ok.I posted some correct test cases (as I and Judge think :wink: )
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
by broderic
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
go about this problem?

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

Posted: Tue Jul 02, 2002 6:01 pm
by Ivan Golubev
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
by Picard
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
by Revenger
It's my mistake... sorry :oops:

Posted: Tue Jul 02, 2002 9:11 pm
by Joe Smith
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
by broderic
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
by dh3014
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
by Adrian Kuegel
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?