10626 - Buying Coke

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10626 - Buying Coke

Post by .. » Wed Mar 10, 2004 3:38 pm

First of all, I am not trying to show off anything.....
I get accepted on 10626 with a O(1) solution. But from the ranklist, it seems that someone use longer runtime and large memory to solve it. Is there any DP solution to this problem?? I am really curious to know :roll:
Thanks in advance.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

10626 Buying Coke ( but using more coins)

Post by sohel » Sun Mar 14, 2004 11:56 am

I tried a simple approach and knew that I was gonna get WA. Well, I wasn't wrong.. I did get WA. But I would like to know : what is the mistake in my approach?

First I use all the 10 coins to buy as many cokes ( number of one coin increases by two for each 10 coin).

Then If the total number of 5 coins is more than the remaining coke, then i
use 2 five coins to buy a coke... this process continues until number of 5 coins left equals to the coke remaining.

then i buy coke using 5 1 1 1, until 5 finishes.

then i use 1 1 1 1 1 1 1 1, until required work is done.

Can somebody point out the mistake.

Thanks.
Last edited by sohel on Mon Mar 15, 2004 9:58 am, edited 1 time in total.

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

Post by Adrian Kuegel » Sun Mar 14, 2004 1:01 pm

A simple example where you fail is:
you want to buy 4 cokes and have 3 coins of value 10, 2 coins of value 1.
You would need to insert 11 coins. But here how you can do it with 10 coins:
insert 10 (1 x 10) get 2 x 1 back
insert 10 (1 x 10) get 2 x 1 back
insert 13 (1 x 10, 3 x 1) get 1 x 5 back
insert 8 (1 x 5, 3 x 1)

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Mar 14, 2004 8:43 pm

Few days ago I posted a message about this problem, but it suddently disappeare. (Seems the board has bug.....)

I post it again here:

I get accepted on 10626 with a O(1) solution. But from the ranklist, it seems that someone use longer runtime and large memory to solve it. It seems that there is some DP-like solution. Can anyone tell me how to do that? I am really curious to know.... Thanks!
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Mon Mar 15, 2004 12:47 am

I'm more curious about the O(1) solution...

The DP solution is this simple recurrence:

f(cokes_left,fives_left,tens_left):
ones_left=original_money-8*cokes_left-5*fives_left-10*tens_left;
min=infinity
if (ones_left>=8) min<?=f(cokes_left-1,fives_left,tens_left);
if (fives_left>=2) min<?=f(cokes_left-1fives_left-2,tens_left);
if (tens_left>=1) min<?=f(cokes_left-1,fives_left,tens_left-1);
if (fives_left>=1 && ones_left>=3) min<?=f(cokes_left-1,fives_left-1,tens_left);
if (tens_left>=1 && ones_left>=3) min<?=f(cokes_left-1,fives_left+1,tens_left-1);
return min;

ie test all combinations. There are few enough states to use memorize them all.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Mar 15, 2004 6:42 am

Oh thanks~~
At first, I try to find a DP solution, but I forget this relation
ones_left=original_money-8*cokes_left-5*fives_left-10*tens_left;
So I wonder how to use 32MB memory to hold all states.........

Here is my O(1) solution,
Warning! Spoiler


























In some case, you need to insert coins more than enough to get a change of a larger coin back. Actually, there is only one case like that:
insert 13 (1 x 10, 3 x 1) get 1 x 5 back.
And you only need to do this if you have the chance to insert 8 x 1 to buy a coke. Consider you have 1 coin of value 10, 6 coins of value 1.

Before make the change,
insert 10 (1 x 10) get 2 x 1 back
insert 8 (8 x 1)

After do the change,
insert 13 (1 x 10, 3 x 1) get 1 x 5 back
insert 8 (1 x 5, 3 x 1)

So you need to consider how many times will (8 x 1) happen, and how many extra coin of value 5 you can get back from the machine.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Fri Apr 09, 2004 12:54 pm

but what should be the output for test... which is.....

1
2 1 0 0
my output is
0

is it good ??


plz.. give me more tests.... becouse i keep WA... ;-(


Regards.
MIras

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Fri Apr 16, 2004 5:30 am

i have an O(1) solution, like .. but it got WA, i must have done an error somewhere.

what i would like to help me spot my error, is lots of input/output test cases. if someone with AC can please give me some... thanx

this problem seems very simple, but its tricky :/
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Fri Apr 16, 2004 5:54 am

haha i just got accepted, that was a silly mistake!!! i'm glad i finally solved this problem.

miras:

2 1 0 0 is not a valid input, you cannot encounter such an input, because it is guaranteed that you have enough money to buy to cokes... so for 2 cokes you'd have at least 16 units.

on a side note, i found an interesting fact about this problem. the number of coins of value 1 doesnt matter. you dont need it to solve the problem... the answer will be the same regardless the number of coins of value 1 (provided of course the input is valid, ie you have enough money)

good luck miras and everyone trying to solve this problem!!!
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Sun Apr 18, 2004 1:18 am

on a side note, i found an interesting fact about this problem. the number of coins of value 1 doesnt matter. you dont need it to solve the problem... the answer will be the same regardless the number of coins of value 1 (provided of course the input is valid, ie you have enough money
Yes, I noticed this when I created the problem... was trying to figure out a case where it DID matter, only to realize there were no such case :-/

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Jul 02, 2004 10:55 pm

Please help in this problem.
I can't find where the problem is...
checking all possible cases with dp.
so why wa?

is there any critical case??


here is the code. please check it..

Code: Select all


#include<stdio.h>
#define A 155
#define B 200
#define C 40
long a[A][B][C],m,noo,nff,ntt,nn;
long no,min,b;
main()
{
	freopen("in.txt","r",stdin);
	long cas,z,i,j,k,n,nf,nt;
	scanf("%ld",&cas);
	for(z=0;z<cas;z++)
	{
		scanf("%ld%ld%ld%ld",&nn,&noo,&nff,&ntt);
		m=noo+5*nff+10*ntt;
		for(i=0;i<A;i++) for(j=0;j<B;j++) for(k=0;k<C;k++) a[i][j][k]=0;
		for(i=0;i<A;i++) a[i][0][0]=i*8;//any no. of 1
		a[1][1][0]=4;//only one 5 + 3 1s
		for(i=2;i<B;i++) a[1][i][0]=2;//if any no. of 5
		for(i=0;i<B;i++) for(j=1;j<C;j++) a[1][i][j]=1;//any no of five+ any ten
		for(n=2;n<A;n++) for(nf=0;nf<B-11;nf++) for(nt=0;nt<C;nt++)
			{
				min=1000000;
				no=m-8*(nn-n)-5*nf-10*nt;
				if(no<0) continue;
				if (nt>=1 && no>=3) {b=a[n-1][nf+1][nt-1]+4;if(b<min) min=b;}
				if (no>=0) {b=a[n-1][nf][nt]+8;if(b<min) min=b;}
				if (nt>=1) {b=a[n-1][nf][nt-1]+1;if(b<min) min=b;}
				if (nf>=2) {b=a[n-1][nf-2][nt]+2;if(b<min) min=b;}
				if (nf>=1 && no>=3) {b=a[n-1][nf-1][nt]+4;if(b<min) min=b;}
				a[n][nf][nt]=min;
			}
		printf("%ld\n",a[nn][nff][ntt]);
	}
	return 0;
}
waiting for any kind of help... :oops: [/i][/b]
Last edited by anupam on Sat Jul 03, 2004 5:49 pm, edited 1 time in total.
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Jul 02, 2004 11:23 pm

Please help. frustated. WA 5 times. what is to check more?? :cry:
"Everything should be made simple, but not always simpler"

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Sat Jul 03, 2004 5:26 pm

Try the input

150 500 100 20

Your program will output the wrong answer due to your
arrays being to small (correct answer is 640).

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Jul 03, 2004 5:52 pm

Hello Yarin, I think my array of only five was too lttle because there is an entry like a[..][nf+1][..].

But, would you please mention what you meant by too small array? BTW, Nice problem. and, my program gives 504 after extending the array.
which means prob. I am missing something. Prob. in the init statements of DP.
Am I right?
Is there any thing wrong in the init statements?
Help please.
"Everything should be made simple, but not always simpler"

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Sun Jul 04, 2004 9:38 pm

Change the array size to 200 (and the for-loops as well) for the five crowns, and it should work (I tested changing your solution). The reason is that the number of five crowns maybe well exceed the initial values due to the 10+1+1+1 -> 5 exchange.

Post Reply

Return to “Volume 106 (10600-10699)”