Tobby_And_Friends's blog

By Tobby_And_Friends, history, 8 years ago, In English

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

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

Any help is really appreciated.

| Write comment?
»
8 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it
  • 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
  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.