Page 1 of 1

### 11196 - Birthday Cake

Posted: Wed May 23, 2007 7:46 am
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..  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....       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=(long)sqrt(n)+1;
b=n/(a-1)*(a-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*r;
if(curs < s ) s=curs;
*f1=true;
return;
}
if(curv >= n)return;
if( k > 1 && curs+r*r >= 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*r > 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
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
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.