A different implementation of digit DP problems

Revision en10, by shadow9236, 2024-03-11 15:01:10

Hello Codeforces, Digit dp was one of the techniques which I had the hardest time trying to learn. I have seen multiple blogs on iterative digit dp. In this blog, I would like to share my recursive implementation of digit dp.

Problem Structure

Typically, digit dp is used in problems of finding the number of values in a range $$$[l,r]$$$ which follow a certain property. Let us call this $$$f(l,r)$$$. The following method will work only when $$$f(l,r) = f(0,r) - f(0,l-1)$$$, which is true for most of the problems. We will now focus on how to calculate $$$g(n) = f(0,n)$$$.

Idea behind the algorithm

To count all numbers less than or equal to $$$n$$$ which follow a certain property, we first count all numbers with the same number of digits as $$$n$$$. Here the numerical order will be the same as lexicographical order. We can now iterate over the common prefix of the two numbers and the first character which differs after the prefix. This gives us the following template.


int g(string s){ int n = s.size(); int ans = 0; for(int i = 0; i < n; i++){ // i is the first position of difference for(int j = (i == 0); j < s[i] - '0'; j++){ // keeping digit j at position i ans += valid_strings(n-i-1); // number of valid strings of length n-i-1 } } if(valid(s)){ ans += 1; } if(n > 1){ // All numbers with less digits ans += g(string(n-1,'9')); } return ans; }

Some remarks are as follows.

  • Adding memoisation to this recursive function gives polylog complexity in most cases.
  • $$$j$$$ is initialised to $$$1$$$ for $$$i == 0$$$ since our numbers can't have leading zeroes.
  • $$$\text{valid_strings}(\cdots)$$$ may be a dp table instead of a mathematical function. It might also depend on the prefix as well as the leftover length.

Some examples

Consider CSES Counting Numbers. Here we have to find the number of numbers less than or equal to $$$n$$$ that no two consecutive digits are the same. Here I get the following function. Full solution.

Solution


CF 919B is an example where a dp table is needed to implement the $$$\text{valid_strings}(\cdots)$$$ function. There is a preparatory phase for filling the dp table. The relevant functions are provided below. Full solution.

Solution
Tags tutorial, dynamic programming, digit dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English shadow9236 2024-03-11 15:01:30 4 Tiny change: 'odeforces,\n Digit ' -> 'odeforces,<br>\n Digit '
en10 English shadow9236 2024-03-11 15:01:10 0 (published)
en9 English shadow9236 2024-03-11 15:00:29 100
en8 English shadow9236 2024-03-11 14:59:09 4 Tiny change: 'r>\n\n<br><br>\n[CF ' -> 'r>\n\n<br>\n[CF '
en7 English shadow9236 2024-03-11 14:58:31 52
en6 English shadow9236 2024-03-11 14:57:06 2
en5 English shadow9236 2024-03-11 14:56:06 989
en4 English shadow9236 2024-03-11 14:51:36 5 Tiny change: '\n</li>\n<\ul>\n' -> '\n</li>\n</ui>\n'
en3 English shadow9236 2024-03-11 14:50:25 742
en2 English shadow9236 2024-03-11 14:26:19 233
en1 English shadow9236 2024-03-11 14:22:09 2450 Initial revision (saved to drafts)