Dear codecheffers,
I’ve few questions to ask and the way you guys approach a problem (esp. w.r.t applying DP). I’ve just started taking competitive programming and finding application of DP tough, throw some insights (like how you approach the problem).
I tried the Stacking Pancakes, which I clearly identified as a DP based problem, but, could only manage to apply memoization . Here’s my code
#include <stdio.h>
#include <string.h>
#define MOD 1000000007
unsigned int memo[1001][1001];
unsigned int N;
unsigned int getCount(unsigned int level,unsigned int max){
register unsigned int i,total=0;
if( level == N-1 && N > 2){
memo[level][max] = max+1;
memo[level][max+1] = max+2;
return max+1;
}
if( level >= N){
return 1;
}
if( memo[level][max] != 0 ){
return memo[level][max];
}
for(i=1;i<=max+1; ++i){
if( i < max ){
if( memo[level+1][max ] != 0 ){
total = total + memo[level+1][max];
}else{
total = total + getCount(level+1,max);
}
}
else{
if( memo[level+1][i] != 0 ){
total = total + memo[level+1][i];
}else{
total = total + getCount(level+1,i);
}
}
total=total%MOD;
}
memo[level][max] = total;
return total;
}
int main() {
unsigned int T;
scanf("%d",&T);
unsigned int d=0;
memset(memo,0,sizeof(unsigned int)*1001*1001);
while(T){
memset(memo,0,sizeof(unsigned int)*1001*1001);
scanf("%d",&N);
d = getCount(1,1);
printf("%d\n", d);
T-=1;
}
return 0;
}
I know my program is still exponential ( pls check) , but, it was a great improvement over plain recursive algo. As I tried the overlapping calculations at each level ( number of digits ), but, it was not sufficient to break the 1s time limit and i got TLE.
Could someone who got AC (I know many, admins, someone) pls help! A little more than the editorial would help!
thanks