## 11196 - Birthday Cake

Moderator: Board moderators

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

### 11196 - Birthday Cake

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

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;
}``````

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am
look at the formulae of S and V. They look similar. This leads to another useful pruning based on inequality. good luck

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

### Re: 11196 - Birthday Cake

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.