## 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

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada

### 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.
Last edited by broderic on Fri Aug 02, 2002 5:29 pm, edited 1 time in total.

shahriar_manzoor
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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
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
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada
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
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
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``````
Last edited by Revenger on Tue Jul 02, 2002 5:29 pm, edited 1 time in total.

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada
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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
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
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
It's my mistake... sorry

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
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.

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Location: Canada
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
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:
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?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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?