Page 1 of 1

11196 - Birthday Cake

Posted: Wed May 23, 2007 7:46 am
by ayeshapakhi
Hello..

I'm trying to solve the prob birthday cake... used backtracking to find the radii and heights.. My procedure's taking huge time.. abt 2:45 mins in my machine for the input 100000 10.. :oops: :(

In a particular level i calculated the maximum remaining volume and the minimum remaining volume and avoided impossible one...
It seems that for all choices i can't reach to target volume but i don't have any idea how to avoid these redundant calculations....
:oops: :oops: :oops: :oops: :oops: :oops: :cry:

Here my code is given.... I'll be highly obliged if anyone share any idea of further pruning...

Regards.... waiting for reply...

Code: Select all

#include <stdio.h>
#include <math.h>
#define N 12
#define inf 100000000L
long n,m,s;
void backtrack(long curv,long curs,long k,long r[],long h[],bool *f1);
int main(void)
{
       long a[N],b[N],test=0;
       bool f1;
       while( scanf("%ld",&n) == 1 && n)
       {
               test++;
               scanf("%ld",&m);
               s=inf;
               a[0]=(long)sqrt(n)+1;
               b[0]=n/(a[0]-1)*(a[0]-1) +1;
               f1=false;
               backtrack(0,0,0,a,b,&f1);
               printf("Case %ld: ",test);
               if(s >= inf) s=0;
               printf("%ld\n",s);
       }
       return 0;
}
void backtrack(long curv,long curs,long k,long r[],long h[],bool *f1)
{
       if(k == m)
       {
               curs+= r[1]*r[1];
               if(curs < s ) s=curs;
               *f1=true;
               return;
       }
       if(curv >= n)return;
       if( k > 1 && curs+r[1]*r[1] >= s)return;

       long maxr,maxh,maxvol,minvol,i,j,restl,restv,l,mins;

       restl=m-k;
       restv=n-curv;
       k++;
       minvol=(restl*restl*(restl+1)*(restl+1))/4;
       if( minvol + curv > n) return;

       mins=restl*(restl+1)*(2*restl+1)/3;
       if(k>1 && mins + curs +r[1]*r[1] > s)return;

       maxr = (long)sqrt(n/k);
       if(k > 1 && (maxr >= r[k-1])) maxr=r[k-1]-1;
       for(i= maxr; i>=restl; i--)
       {
               if(2*restv/i+1>= s) return;

               maxh = restv/(i*i);
               if(k > 1 && (maxh >= h[k-1])) maxh=h[k-1]-1;
               r[k]=i;

               *f1=false;
               for(j=maxh; j>=restl; j--)
               {
                       maxvol=0;
                       for(l=0; l<restl; l++) maxvol+=(i-l)*(i-l)*(j-l);
                       if( curv + maxvol < n) break;

                       h[k]=j;
                       backtrack(curv+i*i*j,curs+2*i*j,k,r,h,f1);
                       if(*f1 && k==m-1)break;
               }
       }
       return;
}

Posted: Sat May 26, 2007 6:59 am
by rujialiu
look at the formulae of S and V. They look similar. This leads to another useful pruning based on inequality. good luck

Re: 11196 - Birthday Cake

Posted: Wed Jun 16, 2010 5:41 pm
by roticv
Thank for the hint. Managed to solved it after so long.

A hint from me is that the order you search matters too. I just changed the order and my code which probably takes hours to run manage to solve the largest test case in a short time.