How to solve a problem of type "Counting from A to B"

Правка en1, от joaquimnt_, 2017-10-09 23:16:58

I am trying to solve this problem: https://www.urionlinejudge.com.br/judge/pt/problems/view/1138

At first, my references was these posts:

https://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property/22394258#22394258 and http://mirror.codeforces.com/blog/entry/8221

But i am getting problems when i try to save the results into a dp table. Can someone tell what are the states of my memoization?

My code (the parts with memoization are commented): https://ideone.com/AOwBpQ

My strategy is: for each digit, compute the number of its occurrences in F(B) and in F(A — 1). The answer (for that digit) is computed by F(B) - F(A - 1). Without dynamic programming techniques, it solves the problem, despiste the slowness. Some problems that i solved earlier got accepted with the following states: dp[current_digit][number_formed][leftmost_lo][leftmost_hi], but in this particular problem, the number formed might be to high.

Теги dynamic programming, counting, digit dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский joaquimnt_ 2017-10-09 23:16:58 1045 Initial revision (published)