Digit DP: How do I further optimize my solution for SPOJ NUMTSN

Tobby_And_Friends's blog

Digit DP: How do I further optimize my solution for SPOJ NUMTSN — 369 Numbers?

By Tobby_And_Friends, history, 10 years ago, In English

Problem Link: http://www.spoj.com/problems/NUMTSN/

My solution: http://ideone.com/7fKLqx

Any help is really appreciated.

digit dp, spoj

-5

Tobby_And_Friends
10 years ago
7

Comments (4)

Show archived | Write comment?

tenshi_kanade

10 years ago, hide # |

← Rev. 4 →

I used bottom-up DP instead of recursive with memoization. First I fixed the length of my strings to 51, decreased A by 1 and increased B by 1, so that I could work with an exclusive range (easier to do digit DP this way). My DP was DP[i][a][b][c][sa][sb], that is how many numbers can I create up to position i with a 3's, b 6's and c 9's. The flags sa and sb indicate whether the number is bigger than A and smaller than B respectively. This solution got TLE.
I then realized that I don't need the exact amount of each digit, but only the difference between them, so I removed one dimension from my DP by storing only how many more 6's than 3's I have, and how many more 9's than 3's I have. My DP changed to DP[i][b][c][sa][sb][u], that is how many numbers can I create up to position i with b more 6's than 3's, and c more 9's than 3's. Flag u indicates if I have used any 3, 6 or 9 so far. The answer will be in DP[51][0][0][1][1][1]. I got AC with this improvement.

Here's my code.

C++ Code

#include <bits/stdc++.h>
#define f(i,a,b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MOD = 1e9 + 7;
int DP[55][34][34][2][2][2], T;
string A, B;

void dec(string &s)
{
    int pos = s.length() - 1;
    s[pos]--;
    while(s[pos] < '0')
    {
        s[pos] = '9';
        s[--pos]--;
    }
}

void inc(string &s)
{
    int pos = s.length() - 1;
    s[pos]++;
    while(s[pos] > '9')
    {
        s[pos] = '0';
        s[--pos]++;
    }
}

int main()
{
    cin >> T;
    while(T--)
    {
        cin >> A >> B;

        reverse(A.begin(), A.end()), reverse(B.begin(), B.end());
        while(A.length() < 51) A += '0';
        while(B.length() < 51) B += '0';
        reverse(A.begin(), A.end()), reverse(B.begin(), B.end());
        inc(B), dec(A);

        f(i,0,51) f(b,0,32) f(c,0,32) f(sa,0,1) f(sb,0,1) f(u,0,1) DP[i][b][c][sa][sb][u] = 0;
        DP[0][16][16][0][0][0] = 1;

        f(i,0,50) f(b,0,32) f(c,0,32) f(sa,0,1) f(sb,0,1) f(u,0,1)
        {
            if(DP[i][b][c][sa][sb][u] == 0) continue;

            f(nx,'0','9')
            {
                if(nx < A[i] && !sa) continue;
                if(nx > B[i] && !sb) continue;

                int nx_sa = sa | (nx > A[i]);
                int nx_sb = sb | (nx < B[i]);

                int nx_b = b;
                int nx_c = c;
                int nx_u = u | (nx == '3') | (nx == '6') | (nx == '9');

                if(nx == '3') nx_b--, nx_c--;
                if(nx == '6') nx_b++;
                if(nx == '9') nx_c++;

                if(nx_b < 0 || nx_c < 0 || nx_b > 32 || nx_c > 32) continue;

                DP[i+1][nx_b][nx_c][nx_sa][nx_sb][nx_u] += DP[i][b][c][sa][sb][u];
                if(DP[i+1][nx_b][nx_c][nx_sa][nx_sb][nx_u] > MOD) DP[i+1][nx_b][nx_c][nx_sa][nx_sb][nx_u] -= MOD;
            }
        }

        cout << DP[51][16][16][1][1][1] << "\n";
    }
}

→ Reply

ffao

10 years ago, hide # ^ |

← Rev. 2 →

A common trick for multi-test problems: if you reverse the direction of your DP (such that DP[...] is in how many ways you can finish the number if your current state is [...]), then the value of states with sa=sb=1 does not depend on either A or B. This allows you to precompute the value of those states for all test cases, and for a specific case you only need to care about states with sa or sb equal to 0 (which should be very few).

Sometimes (and in this specific problem), formulating the DP in reverse should also allow you to find a faster solution for the single-test case.

→ Reply

Eddagdeg

6 years ago, hide # ^ |

← Rev. 2 →

can you explain this trick more?

→ Reply

shourov

8 months ago, hide # ^ |

Oh my god.....Nice observation. I have been trying this problem the whole day with many editorials.But only after seeing your solution finally I understood it.Thanks a lot[user:tenshi-kanade]

→ Reply