Hello Codeforces,

I have seen multiple blogs on iterative digit DP. In this blog, I would like to share my recursive implementation of digit dp related problems.

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;
}

Adding memoisation to this recursive function gives polylog complexity in most cases. Note that $$$j$$$ is initialised to $$$1$$$ for $$$i == 0$$$ since our numbers can't have leading zeroes.

Some examples

Consider ARC173 A. This problem can be solved with binary search. Here we have to find the number of numbers less than or equal to $$$mid$$$ that no two consecutive digits are the same. Here I get the following function.

map<string,int> mp;
int get(string s){
	if(mp.find(s) != mp.end()){
		return mp[s];
	}
	
	int n = s.size();
	int &ans = mp[s];
	
	bool ok = true;
	
	for(int i = 0; i < n; i++){
		
		for(int j = (i == 0); j < s[i] - '0'; j++){
			if(i != 0 && s[i-1] == j + '0')continue;
			ans += power(9,n-i-1);
		}
		
		if(i != 0 && s[i] == s[i-1]){
			ok = false;
			break;
		}
	}
	
	ans += ok;
	
	if(n > 1){
		ans += get(string(n-1,'9'));
	}
	
	return ans;
}