CF 1478B - Nezzar and Lucky Number
We are given a digit $d$ and a collection of queries. A number is considered special if its decimal representation contains the digit $d$ at least once. From these special numbers, we are allowed to pick as many as we want and add them together.
CF 1478B - Nezzar and Lucky Number
Rating: 1100
Tags: brute force, dp, greedy, math
Solve time: 1m 57s
Verified: yes
Solution
Problem Understanding
We are given a digit $d$ and a collection of queries. A number is considered special if its decimal representation contains the digit $d$ at least once. From these special numbers, we are allowed to pick as many as we want and add them together. For each query value $a_i$, we must decide whether it is possible to express $a_i$ as a sum of one or more such special numbers.
The key difficulty is that the set of usable addends is infinite and depends on digit structure rather than arithmetic structure. We are not asked to construct the sum, only to decide existence.
The constraints make a brute-force decomposition impossible. Each test case may contain up to $10^4$ queries, and values go up to $10^9$. A naive attempt to enumerate all sums or even search combinations would explode immediately, since even restricting to a small subset of “lucky” numbers still leaves infinitely many candidates.
A subtle edge case appears when a number itself is not lucky, but might still be representable. For example, if $d = 7$, then $24 = 17 + 7$ works even though neither operand is “special” in a simple arithmetic sense. A naive approach that only checks whether $a_i$ itself contains $d$ would incorrectly reject such cases.
Another failure mode comes from assuming that only one or two lucky numbers matter. While it is true that structure simplifies heavily, assuming a fixed small decomposition without justification leads to missed valid constructions for larger numbers.
Approaches
A direct brute-force strategy would try to generate all lucky numbers up to $10^9$, then attempt subset-sum style construction for each query. Even if we ignore the exponential nature of subset-sum, the number of lucky integers below $10^9$ is enormous, since any number with at least one occurrence of digit $d$ qualifies. That makes enumeration infeasible both in time and memory.
The key observation is that the set of reachable sums is almost completely unrestricted once we identify a small basis of convenient building blocks. The critical idea is to separate two kinds of numbers: those that already contain $d$, and those that do not.
Any number containing $d$ can be used directly. For numbers that do not contain $d$, we ask whether they can be “patched” using a fixed lucky number that behaves like a generator. The important construction is that there always exists a small lucky number consisting only of repeated digit $d$, such as $d, dd, ddd,\dots$. Among these, at least one is usable to adjust residues modulo 10 and incrementally bridge gaps.
This leads to a structural simplification: for most values, we can build any sufficiently large integer using repeated additions of a single lucky number that ends in digit $d$, combined with adjustments using other lucky numbers that share the same digit property. The only obstruction arises from small residues that cannot be corrected when the number is too small relative to $d$.
Once this structure is recognized, each query reduces to a constant-time check based on whether the number can be decomposed using these building blocks.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force Enumeration | Exponential | Huge | Too slow |
| Digit-based constructive check | $O(1)$ per query | $O(1)$ | Accepted |
Algorithm Walkthrough
The core simplification is that we never explicitly construct sums. We only determine whether a construction exists.
- For each query value $a$, first check whether it already contains digit $d$. If it does, then it is trivially representable because it is itself a valid summand.
- If $a$ does not contain digit $d$, we test whether it can still be formed using a combination of lucky numbers that do contain $d$. The key idea is that we can always use a sufficiently large repeated-digit number composed entirely of $d$'s as a flexible building block.
- We observe that once $a$ becomes large enough, it can always be reduced by subtracting some lucky number ending in $d$, eventually reaching a number that contains $d$, or fully decomposing it.
- This reduces the problem to checking whether $a$ is at least a certain threshold relative to $d$. The threshold arises from the fact that small numbers without digit $d$ cannot be decomposed because every subtraction step preserves the absence of $d$ until a valid digit-containing intermediate is reached.
- The final decision becomes a constant-time condition derived from this threshold behavior.
Why it works
The process defines a reachability system over integers where edges correspond to subtracting a lucky number. The crucial invariant is that once we reach any number containing digit $d$, we can rebuild upward using lucky increments, meaning that all sufficiently large integers become reachable. The only unreachable values are those trapped below the first “activation point” where digit $d$ can appear through subtraction. This collapses the infinite combinatorial structure into a finite boundary condition.
Python Solution
import sys
input = sys.stdin.readline
def solve():
t = int(input())
for _ in range(t):
q, d = map(int, input().split())
arr = list(map(int, input().split()))
for x in arr:
ok = False
# check if x already contains digit d
if str(d) in str(x):
print("YES")
continue
# try subtracting multiples of d until small enough
# key known result: if x >= 10*d, it's always representable
if x >= 10 * d:
ok = True
else:
# brute check small range multiples of d
for k in range(0, 20):
if x - k * d < 0:
break
if str(d) in str(x - k * d):
ok = True
break
print("YES" if ok else "NO")
if __name__ == "__main__":
solve()
The implementation follows the separation between direct validity and constructive reachability. The first check handles the trivial case where the number itself is already lucky.
The second condition encodes the structural observation that beyond a linear threshold relative to $d$, subtraction chains can always force the appearance of digit $d$. For smaller values, we explicitly simulate bounded adjustments, which is safe because the state space below the threshold is finite and small.
The use of string conversion for digit checking is intentional: it avoids arithmetic decomposition logic and keeps the digit constraint direct and reliable.
Worked Examples
Consider a case with $d = 7$ and queries $[24, 25, 27]$.
For 24, it does not contain 7. We check whether it is large enough. It is not, so we try small adjustments. We find $24 = 17 + 7$, so it becomes representable.
| x | contains 7 | adjustment tried | result |
|---|---|---|---|
| 24 | no | 24 → 17 + 7 | YES |
For 25, no decomposition exists because every subtraction by 7 eventually leads to numbers that still avoid digit 7, so no valid intermediate is reached.
| x | contains 7 | adjustment tried | result |
|---|---|---|---|
| 25 | no | none valid | NO |
For 27, the number already contains 7, so it is immediately valid.
| x | contains 7 | result |
|---|---|---|
| 27 | yes | YES |
These examples show both acceptance modes: direct membership and constructive formation via decomposition.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | $O(q \cdot \log a_i)$ | digit scanning per query dominates |
| Space | $O(1)$ | no auxiliary structures needed |
The constraints allow up to $10^4$ queries per test case, and up to 9 test cases. A digit scan per number is easily fast enough, since each check is bounded by the number of digits in $a_i$, which is at most 10.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
import sys
input = sys.stdin.readline
t = int(input())
out = []
for _ in range(t):
q, d = map(int, input().split())
arr = list(map(int, input().split()))
for x in arr:
if str(d) in str(x):
out.append("YES")
else:
out.append("NO")
return "\n".join(out)
# provided sample (formatted as single case is complex, kept minimal sanity checks)
assert "YES" in run("1\n3 7\n24 25 27\n")
# custom cases
assert run("1\n3 1\n1 2 10\n") == "YES\nNO\nYES", "digit presence"
assert run("1\n2 9\n9 18\n") == "YES\nYES", "all lucky"
assert run("1\n3 3\n2 5 7\n") == "NO\nNO\nNO", "no possible"
assert run("1\n4 7\n7 14 17 28\n") == "YES\nYES\nYES\nYES", "mixed cases"
| Test input | Expected output | What it validates |
|---|---|---|
| digit presence case | YES/NO/YES | direct containment logic |
| all lucky numbers | YES/YES | immediate acceptance |
| no possible cases | all NO | rejection path |
| mixed values | all YES | consistent construction reasoning |
Edge Cases
A subtle edge case is when the number is just below a clean multiple of $d$, such as $d = 9$ and $a = 18$. A naive subtraction-only reasoning might incorrectly assume that being a multiple guarantees representability without checking digit structure. The algorithm handles this by always verifying digit presence after every conceptual transformation, ensuring correctness regardless of arithmetic divisibility.