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

Post by broderic » 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.
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

Post by shahriar_manzoor » Tue Jul 02, 2002 6:43 am

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

Post by Revenger » 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))?

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

Post by broderic » Tue Jul 02, 2002 8:44 am

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

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » 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?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » 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...

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Tue Jul 02, 2002 1:38 pm

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

Post by broderic » 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
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 )

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » 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? ;-)

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » 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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Tue Jul 02, 2002 7:12 pm

It's my mistake... sorry :oops:

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Post by Joe Smith » 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.

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

Post by broderic » 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

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » 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?

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

Post by Adrian Kuegel » 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?

Post Reply

Return to “Volume 103 (10300-10399)”