## 11196 - Birthday Cake

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

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

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

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.