I am trying to solve this problem http://www.spoj.com/problems/NUMTSN/ on spoj. I tried to use dynamic programming. I am getting TLE. Here is my code: http://ideone.com/VnPIZp \ //
//code int dp[54][2][18][18][18];
int solve(int index, int free, int t,int s, int n) { if(t > 17 || s > 17 || n > 17) return 0;
//DBG(index);
if(index == num)
{
//DBG(index);
if(t >= 1 && (t == s) && (s == n))
return 1;
return 0;
}
int &ret = dp[index][free][t][s][n];
if(ret != -1) return ret;
ret = 0;
int nfree,nt,ns,nn;
for(int i = 0; i < 10; i++)
{
nfree = free | (i < a[index]);
nt = t + ( (i == 3) ? 1 : 0); //DBG(nt);
ns = s + ( (i == 6) ? 1 : 0); //DBG(ns);
nn = n + ( (i == 9) ? 1 : 0); //DBG(nn);
if(free)
{
ret = ((ret % MOD) + (solve(index+1, nfree, nt, ns, nn)) % MOD) % MOD;
}
else
{
if( i <= a[index])
ret = (ret % MOD + (solve(index+1, nfree, nt, ns, nn)) % MOD ) % MOD;
}
}
return (ret% MOD);
}
the time limit for this prolem is small. I solved this problem by pre calculation by dp[lenght][three][six][nine].Then for every input I iterate through the string and calculate that how many 369 number can be found remaining (say)L(length)-i position(this can be found from dp[lenght][three][six][nine]) by keeping first i position unchanged.
thanks for replying, I am not sure how you maintain that we have to count number of 369 numbers less than equal to a number (target). In my implementation i have a target number and all numbers less than it are checked by dp. What is the target number in your pre calculation? Is it like 999 for length 3? Could you give some more hints?
Yes... 999 for length 3. Here is code that i tried to explain before.
a=b=c=e=0; l=strlen(ss); for(i=l-1;i>=0;i--){ for(j=0;j<ss[l-1-i]-'0';j++) { int aa,bb,cc;aa=bb=cc=0; if(j==3)aa++; if(j==6)bb++; if(j==9)cc++; e=(e+rec(i-1,aa+a,bb+b,cc+c,j,0))%1000000007; } if(ss[l-1-i]=='3')a++; if(ss[l-1-i]=='6')b++; if(ss[l-1-i]=='9')c++; } if(a!=0&&a==b&&b==c) e++;