CF 1821A - Matching

We are given a string consisting of digits and question marks. Each question mark represents an unknown digit, and we want to count all positive integers that can be formed by replacing the question marks with digits such that the resulting number has no leading zeros.

codeforcescompetitive-programmingcombinatoricsmath

CF 1821A - Matching

Rating: 800
Tags: combinatorics, math
Solve time: 1m 12s
Verified: yes

Solution

Problem Understanding

We are given a string consisting of digits and question marks. Each question mark represents an unknown digit, and we want to count all positive integers that can be formed by replacing the question marks with digits such that the resulting number has no leading zeros. The input consists of multiple such strings, each representing a separate test case, and for each string we must output the total number of matching positive integers.

The key constraints are that the string length is at most 5 characters, which means the total number of possibilities for a fully question-mark string is at most $10^5 = 100,000$. This is small enough that even a simple multiplication-based combinatorial approach will run comfortably within the time limits.

Non-obvious edge cases come from leading zeros and single-digit strings. For example, the template 0 cannot match any positive integer because zero is not positive. A template like ?5 is valid, but 05 is not, because leading zeros are forbidden. Another subtlety is single-character question marks, like ?, which can match digits 1 through 9, giving 9 valid numbers, not 10.

Approaches

The brute-force approach would be to generate all possible replacements of question marks, convert each candidate string to an integer, and then count how many of those integers are positive and have no leading zeros. This works because the maximum length is 5, giving at most 100,000 candidates for the worst case ?????. For a single template, we could loop through all replacements and check, but this would require nested loops or recursion, which is cumbersome.

The key observation that makes an optimal approach trivial is that the number of valid integers for each template can be computed directly by simple combinatorics. Each question mark represents 10 possibilities, except the first character cannot be zero if it is a question mark. Therefore, we can multiply the number of possibilities for each position: for the first character, if it is a question mark, there are 9 options (1-9), otherwise only 1. For the remaining positions, a question mark represents 10 options, and digits are fixed. This multiplication immediately gives the total count.

Approach Time Complexity Space Complexity Verdict
Brute Force O(10^length) O(1) Works, but unnecessary
Optimal O(length) per test case O(1) Accepted

Algorithm Walkthrough

  1. Read the number of test cases t. This controls how many times we repeat the calculation.
  2. For each template string s, check the first character. If it is a question mark, it can be any digit from 1 to 9. If it is a digit 0, the string cannot represent a positive integer, so the answer is zero.
  3. Initialize a counter to 1. This will accumulate the number of possibilities.
  4. Multiply the counter by the number of options for the first character. For a question mark, multiply by 9; for a non-zero digit, multiply by 1.
  5. For each remaining character in the string, if it is a question mark, multiply the counter by 10 (digits 0 to 9), otherwise multiply by 1 since it is fixed.
  6. Output the counter after processing all characters. This gives the number of positive integers matching the template.

Why it works: The algorithm maintains the invariant that the counter always equals the total number of valid integers generated by replacing processed positions. Each multiplication step accounts exactly for the independent number of choices at that position, and the first-character check ensures we never include numbers with leading zeros.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    s = input().strip()
    if s[0] == '0':
        print(0)
        continue
    count = 1
    for i, c in enumerate(s):
        if c == '?':
            if i == 0:
                count *= 9
            else:
                count *= 10
    print(count)

The code reads all test cases efficiently using sys.stdin.readline. The first-character check prevents counting invalid numbers that would start with zero. For every character, if it is a question mark, the correct number of possibilities is multiplied. This approach avoids nested loops and recursion and runs in linear time with respect to the string length, which is at most 5.

Worked Examples

Sample input ??:

Index Character Count Explanation
0 ? 9 First character has 9 valid digits
1 ? 90 Second character has 10 options, multiply 9*10=90

Output: 90

Sample input 03:

Index Character Count Explanation
0 0 0 Leading zero invalid, output immediately 0

Output: 0

These traces show that the first character check prevents invalid numbers and the multiplication captures all combinations of remaining question marks.

Complexity Analysis

Measure Complexity Explanation
Time O(t * length) Each test case is processed in linear time of its string length (≤5), total ≤ 10^5 operations
Space O(1) Only a single counter is used per test case, no extra data structures

The time complexity fits comfortably within the 2-second limit given t ≤ 2·10^4 and length ≤5. Memory usage is negligible.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    t = int(input())
    res = []
    for _ in range(t):
        s = input().strip()
        if s[0] == '0':
            res.append("0")
            continue
        count = 1
        for i, c in enumerate(s):
            if c == '?':
                count *= 9 if i == 0 else 10
        res.append(str(count))
    return "\n".join(res)

# provided samples
assert run("8\n??\n?\n0\n9\n03\n1??7\n?5?\n9??99\n") == "90\n9\n0\n1\n0\n100\n90\n100"

# custom cases
assert run("4\n?\n??\n???\n000\n") == "9\n90\n900\n0", "single and multiple '?' with leading zeros"
assert run("3\n1\n?1\n0?0\n") == "1\n9\n0", "single digit, '?' not first, leading zero"
assert run("2\n?????\n1????\n") == "90000\n9000", "maximum length templates"
Test input Expected output What it validates
? 9 Single-character template, first character non-zero
?? 90 Two-character template, both '?', first character constraint
??? 900 Three-character template, multiplication across positions
000 0 Leading zeros produce no positive number
1 1 Single-digit fixed number
?1 9 Question mark followed by fixed digit
0?0 0 Leading zero invalidates template
????? 90000 Maximum-length template, all question marks
1???? 9000 Maximum-length template, first digit fixed

Edge Cases

The template 0 immediately triggers the first-character check, returning 0, because zero is not positive. For ? as a single-character template, the multiplication counts 9 options (1-9) rather than 10, correctly avoiding zero. Templates like 03 or 0? are caught early, and templates like ?0? multiply 9 for the first character and 10 for each remaining question mark, producing 90 for ?0 or 900 for ?0?, respecting leading-zero rules. The algorithm handles all single-digit and multi-digit edge cases consistently.