10626 - Buying Coke

[..]

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
Thanks in advance.

[sohel]

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.

[Adrian Kuegel]

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)

[..]

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!

[Yarin]

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.

[..]

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.

[miras]

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]

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

[epsilon0]

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

[Yarin]

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]

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

[anupam]

Please help. frustated. WA 5 times. what is to check more??

[Yarin]

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]

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.

[Yarin]

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.