Rare
 0/8

Digit DP

Author: Jesse Choe

Contributors: Nathan Wang, Chuyang Wang, Daniel Ge

Finding the number of integers in a range that have a property.

Edit This Page

Focus Problem – try your best to solve this problem before continuing!

General Resources

Digit DP is a technique used to solve problems that asks you to find the number of integers within a range that satisfies some property based on the digits of the integers. Typically, the ranges are between large integers (such as between 11 to 101810^{18}), so looping through each integer and checking if it satisfies the given property is too slow. Digit DP uses the digits of the integers to quickly count the number of integers with the given property in the range of integers.

Solution - Odometer

Without Dynamic Programming

We can solve this problem in O(YX)\mathcal{O}(Y - X) time by looping through XYX \ldots Y and checking whether a given number is an interesting number. However, since YXY - X can be large, the naive solution is too slow, requiring us to optimize it.

With Dynamic Programming

One way to optimize the brute force approach of looping from XX to YY and counting interesting numbers is by using dynamic programming. The DP approach involves considering all 9 digits one at a time to occupy at least half of the number.

Let dp[pos][k][under][started]\texttt{dp[pos][k][under][started]} where pos\texttt{pos} is the current position, k\texttt{k} is a counter to see if you have at least half of the same digit, under\texttt{under} is whether you have gone below the actual number, and started\texttt{started} is a boolean if you still have leading zeros. The transition involves looping through 9 digits to add to the current location and comparing with the digit we want to occupy at least half of the number.

Given the current state dp[pos][k][under][started]\texttt{dp[pos][k][under][started]}, we loop through all digits from 0 to 9 and consider adding each of them to the current position. If we add the digit dd to the current position, we update our state as follows:

  • If dd is less than the ii-th digit of the actual number YY, then we set under\texttt{under} to true.
  • If dd is not zero or started\texttt{started} is already true, then we set started\texttt{started} to true.
  • If dd is equal to the digit we are interested in, then we increment kk.
  • If kk is greater than i+12\lfloor \frac{i+1}{2} \rfloor, then we increment our count of interesting numbers by 1.
  • We move on to the next position by setting ii to i+1i+1 and transitioning to the next state.

This algorithm is fast enough as the number of digits is small and there are only nine digits.

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[19][50][2][2]; // dp[pos][k][under][started]
string num;
/** Reset the dp array to its initial values. */
void reset() {

Java

import java.io.*;
import java.util.*;
public class Odometer {
// dp[pos][count][under][started]
static long[][][][] dp = new long[19][50][2][2];
static String num;
/** Reset the dp array to its initial values. */
public static void reset() {

Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBinary Search, DP
CFEasy
Show TagsDP
SPOJEasy
Show TagsDP
CFNormal
Show TagsDP
CCNormal
Show TagsDP

USACO

StatusSourceProblem NameDifficultyTags
GoldNormal
Show TagsDP
GoldHard
Show TagsDP

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!