CF 331C1 - The Great Julya Calendar

Rating: 1100
Tags: dp
Solve time: 1m 48s
Verified: yes

Solution

Problem Understanding

We start with a non-negative integer n.

In one operation, we look at the decimal representation of the current number, choose any digit that appears in it, and subtract that digit from the number. The chosen digit can be zero, but subtracting zero never helps, so useful moves always subtract a positive digit that occurs in the current number.

The goal is to reach exactly zero using as few operations as possible.

For example, if the current value is 24, the available digits are 2 and 4. We may subtract either one. One optimal sequence is:

24 → 20 → 18 → 10 → 9 → 0

which uses five operations.

For the C1 version of the problem, n ≤ 10^6. This bound is small enough to consider every value from 0 to n. A dynamic programming solution with one state per number requires roughly one million states, which is easily manageable within the time and memory limits. Approaches that repeatedly explore all possible subtraction sequences would grow exponentially and become infeasible long before reaching the upper bound.

There are several edge cases that deserve attention.

If n = 0, no operations are needed at all.

Input:

Output:

A careless implementation that initializes all answers to a large value and never handles the starting state properly could incorrectly report something else.

Numbers containing zeros are another common source of mistakes.

Input:

The available digits are 1 and 0. Subtracting 0 leaves the number unchanged and creates a useless self-transition. The correct optimal sequence is:

10 → 9 → 0

so the answer is:

An implementation that blindly processes digit 0 without care may accidentally create infinite loops in recursive solutions.

Single-digit numbers have an immediate answer.

Input:

Output:

Since digit 7 appears in the number, we can subtract it directly and reach zero in one move.

Approaches

The most direct idea is to think of every subtraction sequence as a path. From a number x, we can move to x - d for every digit d appearing in x. If we recursively try all possibilities and take the minimum number of steps, we eventually obtain the correct answer.

The problem is that the same intermediate values appear repeatedly. For example, many different paths may arrive at the number 137, and recomputing its answer every time causes an explosion in work. The number of possible subtraction sequences grows exponentially.

The key observation is that the answer for a number depends only on answers of smaller numbers. If we already know the minimum operations required for every value below x, then we can compute the answer for x by trying every digit appearing in x.

Let dp[x] denote the minimum number of operations needed to reduce x to zero.

Suppose digit d appears in x and d > 0. After subtracting d, we arrive at x - d. The first move costs one operation, and then we need dp[x - d] more operations. That gives the transition

dp[x] = min(dp[x], dp[x - d] + 1).

Since every transition goes to a smaller number, we can process values in increasing order from 1 to n. When computing dp[x], all required states have already been computed.

This transforms the problem into a straightforward dynamic programming solution with one state per integer.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Exponential	Exponential recursion tree	Too slow
Optimal DP	O(n log n)	O(n)	Accepted

The log n factor comes from extracting the digits of each number.

Algorithm Walkthrough

Read the input value n.
Create an array dp of size n + 1.
Set dp[0] = 0 because zero already requires no operations.
For every number x from 1 to n, initialize dp[x] to a large value.
Extract all digits of x by repeatedly taking x % 10 and dividing by 10.
For every non-zero digit d that appears in x, consider making that subtraction as the first move.
Update

dp[x] = min(dp[x], dp[x - d] + 1).

The value dp[x - d] is already known because x - d < x. 8. After processing all digits of x, dp[x] stores the optimal answer for that number. 9. Output dp[n].

Why it works

The dynamic programming state represents the true minimum number of operations needed to reach zero from a given value.

Every valid first move from x must subtract one of its digits. After choosing digit d, the remaining work is exactly the optimal solution for x - d. Thus every valid strategy has cost 1 + dp[x - d] for some digit d appearing in x.

The algorithm checks all such first moves and keeps the minimum. Since all smaller states have already been computed correctly, the chosen minimum equals the true optimum for x. By induction on increasing values of x, every state is computed correctly, including dp[n].

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())

    dp = [0] * (n + 1)

    for x in range(1, n + 1):
        dp[x] = 10**9

        t = x
        while t > 0:
            d = t % 10
            if d != 0:
                dp[x] = min(dp[x], dp[x - d] + 1)
            t //= 10

    print(dp[n])

if __name__ == "__main__":
    solve()

The array dp stores the minimum number of operations for every value up to n.

The outer loop processes numbers in increasing order. This ordering is essential because every transition goes from x to x - d, which is strictly smaller whenever d > 0. By the time we compute dp[x], all required predecessor states are already available.

Digit extraction is performed directly with repeated modulus and division. This avoids converting every number to a string and keeps the implementation simple and efficient.

Ignoring digit 0 is important. Subtracting zero does not change the number and would create a transition from a state to itself. Such a move can never improve the answer.

The base case dp[0] = 0 anchors the entire recurrence. Single-digit numbers naturally work because one of their digits equals the number itself, allowing a direct transition to zero.

Worked Examples

Example 1

Input:

Relevant DP states:

x	Digits	Best Transition	dp[x]
1	1	dp[0] + 1	1
2	2	dp[0] + 1	1
3	3	dp[0] + 1	1
...	...	...	...
20	2, 0	dp[18] + 1	4
21	2, 1	min(dp[19]+1, dp[20]+1)	4
22	2, 2	dp[20] + 1	5
23	2, 3	min(dp[21]+1, dp[20]+1)	5
24	2, 4	min(dp[22]+1, dp[20]+1)	5

Final answer:

This example shows that the optimal solution is not always obtained by subtracting the largest digit at every step. Dynamic programming evaluates every legal first move and keeps the best one.

Example 2

Input:

x	Digits	Best Transition	dp[x]
1	1	dp[0] + 1	1
2	2	dp[0] + 1	1
3	3	dp[0] + 1	1
...	...	...	...
9	9	dp[0] + 1	1
10	1, 0	dp[9] + 1	2

Final answer:

This trace highlights why digit 0 must be ignored. The only useful move is subtracting 1, leading to 9, which then reaches zero in one more operation.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each number processes all of its decimal digits
Space	O(n)	The DP array stores one value for every number from 0 to n

For n ≤ 10^6, the DP array contains about one million entries, which comfortably fits in memory. Each state examines only a handful of digits, so the total running time remains well within the two-second limit.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def solve():
    input = sys.stdin.readline
    n = int(input())

    dp = [0] * (n + 1)

    for x in range(1, n + 1):
        dp[x] = 10**9
        t = x

        while t > 0:
            d = t % 10
            if d:
                dp[x] = min(dp[x], dp[x - d] + 1)
            t //= 10

    print(dp[n])

def run(inp: str) -> str:
    backup_stdin = sys.stdin
    backup_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    solve()

    out = sys.stdout.getvalue()

    sys.stdin = backup_stdin
    sys.stdout = backup_stdout

    return out

# provided sample
assert run("24\n") == "5\n", "sample 1"

# minimum value
assert run("0\n") == "0\n", "n = 0"

# single digit
assert run("7\n") == "1\n", "single digit reaches zero directly"

# contains zero digit
assert run("10\n") == "2\n", "must ignore digit 0"

# another small boundary case
assert run("1\n") == "1\n", "smallest positive number"

Test input	Expected output	What it validates
`24`	`5`	Official sample
`0`	`0`	Base case
`7`	`1`	Single-digit behavior
`10`	`2`	Correct handling of digit zero
`1`	`1`	Smallest positive input

Edge Cases

Consider the input:

The algorithm initializes dp[0] = 0 and performs no transitions. The output is immediately 0. This matches the fact that the number is already zero.

Consider the input:

When processing 10, the extracted digits are 1 and 0. The algorithm ignores 0 and uses only the transition through digit 1:

dp[10] = dp[9] + 1 = 2.

The resulting sequence is 10 → 9 → 0, which is optimal.

Consider the input:

The only non-zero digit is 7. The transition becomes:

dp[7] = dp[0] + 1 = 1.

The algorithm correctly recognizes that a single subtraction reaches zero.

Consider the input:

The digits are 1, 0, and 0. The algorithm ignores both zeros and considers only subtracting 1, producing the transition to 99. No invalid self-transition is introduced, and the DP continues normally. This is exactly the behavior required by the problem.