10313 - Pay the Price

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

[shahriar_manzoor]

long is not enough, use long long. Ofcourse u may have other mistakes

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

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

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

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

[Revenger]

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

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

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

[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

[Revenger]

It's my mistake... sorry

[Joe Smith]

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.

[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

[dh3014]

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?

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