Cirno and Number (Hard Version)

Observation 1 — only the neighbors matter

We need

$$\min_b |a-b|.$$

If we know the closest valid number from below and from above,

$$\text{lo}=\max\{b\mid b\le a,\ b\text{ is valid}\}, \qquad \text{hi}=\min\{b\mid b\ge a,\ b\text{ is valid}\},$$

then the answer is simply

$$\min(a-\text{lo},\ \text{hi}-a),$$

ignoring a side if it does not exist. So the whole problem is: build $\text{lo}$ and $\text{hi}$ greedily.

Observation 2 — same length candidates

Let $s$ be the decimal representation of $a$, with length $L$.

Consider a valid number $b$ with the same length as $a$ and $b<a$. Let $i$ be the first position where $b$ differs from $s$. Then

$$b_0=s_0,\ b_1=s_1,\ldots,\ b_{i-1}=s_{i-1}, \qquad b_i<s_i.$$

For this fixed first differing position $i$, the best possible smaller number is obvious:

$$b_i=\max\{x\in d\mid x<s_i\},$$

and every later digit should be as large as possible:

$$b_j=\max(d) \quad (j>i).$$

That gives the largest valid number below $a$ with first difference at $i$.

The upper side is the exact mirror. For $b>a$ with first difference at $i$:

$$b_i=\min\{x\in d\mid x>s_i\}, \qquad b_j=\min(d) \quad (j>i).$$

Of course, this only works while the prefix $s_0\ldots s_{i-1}$ itself consists of allowed digits. If the prefix is already invalid, it cannot be equal to a valid number's prefix. No magic, no DP monster, just first-difference bookkeeping.

Also: no leading zero for multi-digit numbers. This is the tiny annoying detail that eats wrong submissions for breakfast.

Observation 3 — different lengths

Any valid number with fewer than $L$ digits is automatically smaller than $a$. We can just generate the maximum valid number for every length $1,2,\ldots,L-1$ and take the maximum.

Any valid number with more than $L$ digits is automatically larger than $a$. The smallest such useful length is $L+1$, so we generate the minimum valid number of length $L+1$ if it fits the constraints.

For a fixed length:

• maximum valid number: all digits are $\max(d)$, except this is impossible for length $>1$ if there is no nonzero digit;
• minimum valid multi-digit number: first digit is the smallest nonzero allowed digit, the rest are $\min(d)$;
• length $1$ is special because $0$ is a valid representation of the number zero.

Since $a\le 10^{17}$, $L\le 18$. All useful candidates have at most $18$ digits. If $L=18$, we do not need to build a $19$-digit upper candidate: if a nonzero digit exists, some same-length valid number is already at least $a$; otherwise the only possible valid number is $0$.

Algorithm

For each test case:

1. Store the allowed digits and a boolean array $\text{allowed}[0\ldots 9]$.
2. Let $s=\text{toString}(a)$ and $L=|s|$.
3. Scan positions $i=0\ldots L-1$, maintaining whether the prefix before $i$ is valid.
4. If the prefix is valid:
   • try the largest allowed digit smaller than $s_i$ for a floor candidate;
   • try the smallest allowed digit larger than $s_i$ for a ceiling candidate;
   • fill the suffix greedily with $\max(d)$ or $\min(d)$ respectively.
5. If the whole string $s$ is valid, then $a$ itself is both a floor and a ceiling candidate.
6. Add candidates of shorter lengths for the floor.
7. Add the candidate of length $L+1$ for the ceiling when needed.
8. Output the better difference.

Correctness proof

Lemma 1

The algorithm finds the greatest valid number of the same length as $a$ that is at most $a$.

Proof. If $a$ itself is valid, the algorithm includes it. Otherwise, take any valid same-length number $b<a$. Let $i$ be the first position where $b$ differs from $a$. Then all earlier digits must equal $a$ and must be allowed, so the algorithm considers this $i$. Since $b<a$, we must have $b_i<a_i$. For this same $i$, choosing the largest allowed digit below $a_i$ and filling the rest with $\max(d)$ produces a valid number at least as large as $b$. Therefore, taking the maximum over all considered $i$ gives the best possible same-length floor. $\square$

Lemma 2

The algorithm finds the smallest valid number of the same length as $a$ that is at least $a$.

Proof. Symmetric to Lemma 1. For any valid same-length $b>a$, at the first differing position $i$ we have $b_i>a_i$. The algorithm chooses the smallest allowed digit above $a_i$ and fills the suffix with $\min(d)$, producing a valid number no larger than $b$ for that $i$. Taking the minimum over all $i$ gives the best same-length ceiling. $\square$

Lemma 3

The algorithm correctly handles valid numbers of different lengths.

Proof. Every valid number with fewer digits than $a$ is smaller than $a$, so the best such number is the maximum valid number among those lengths; the algorithm checks them. Every valid number with more digits than $a$ is larger than $a$, and among longer lengths the shortest possible length gives the smallest value, so checking length $L+1$ is enough when it can matter. $\square$

Theorem

The algorithm outputs the minimum possible value of $|a-b|$.

Proof. By Lemmas 1 and 3, the computed $\text{lo}$ is the greatest valid number not exceeding $a$. By Lemmas 2 and 3, the computed $\text{hi}$ is the smallest valid number not less than $a$. Any valid $b<a$ is no better than $\text{lo}$, and any valid $b>a$ is no better than $\text{hi}$. Therefore the optimal answer is exactly

$$\min(a-\text{lo},\ \text{hi}-a).$$

$\square$

Complexity

Let $L$ be the number of digits of $a$, so $L\le 18$, and let $n\le 10$.

For each position we scan the digit set, and building candidate strings is tiny:

$$O(L(n+L))$$

per test case, which is effectively constant. Memory usage is

$$O(1).$$