Reslan's blog

Help with digit DP problem
By Reslan, history, 10 years ago, In English

Hello codeforces :D

I was trying to solve this problem

and I got TLE , I tried to solve it using DP.

my approach for this problem , first I find how many 369 are there in the interval [ 1 , B ] , let this value be right

then I find how many 369 are there in the interval [ 1 , A ] , let this value be left

my final answer will be right — left , if A is not 369 number

else it will be : right — left + 1

here is my code

can I do some pre calculations to avoid TLE ?

thank in advance :D

  • Vote: I like it
  • -4
  • Vote: I do not like it

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

What are you asking for is not clear. you solved it or tried to solved it by dp and got TLE? And first describe you approach or give a link of your code. without this how can anyone tell you that what are you missing !!!!

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

it's better to use memo[20][7][7][7][2] because the length will not be greater than 20 and you shouldn't make the number of (3's , 6's , 9's ) more than 6 during calculation because it will not lead to positive result .

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

    What should I do if the test case is: 1 333333333366666666669999999999 ?

    In this case, the number of each digit appears more than 6 times. Is my approach incorrect?

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    sorry I didn't noticed that it's up to 50 digits .

    → Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Immagine you have a accumulative array sum[N]:

sum[1] = sum[0] + C1;

sum[2] = sum[1] + C2;

....

sum[n] = sum[n-1] + C;

If you want to a sub-interval [L, R], you get it by sum[R] — sum[L-1]. You should do something similar as 369[B] — 369[A-1].

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You can do a dp over the the length of a string ( for example string of length 50 ) but how to do it for a specific number ( ex : s = "123456" ), that's the tricky part i think .

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

I think, it's not solvable by this dp. 50*16*16*16*2*100*10 = 409600000 is too high number of operations. Try to do it with combinatorics instead of dp. Now complexity is O(10·T·len4 / 27), I think, you can achieve O(10·T·len2 / 3) with combinatorics.

Solution is: Take first x digits from number A, iterate (x+1)-th digit from 0 to A[x+1]-1 and count by combinatorics, how many numbers with such starting x + 1 digits can have exactly y threes, sixes and nines, where y is in range (1, len / 3). We have first x+1 digits, and last digits can be every number from 0 to 9, so we can count for every y the amount of possible numbers by combinatorics easily.

UPD: Code

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it -8 Vote: I do not like it

    We just need a dp[lenght][lenght / 3][lenght / 3][lenght / 3] that leads to ~ 3 * 105 operations.

    → Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have just solved it. My time is 0.0 :D

I found this blog which gives a nice tutorial on how to solve this kind of problems.

here is my code.

→ Reply