tortuga's blog

SPOJ — NUMTSN — 369 Numbers
By tortuga, history, 9 years ago, In English

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);

}

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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++;
      → Reply