Arithmetic as Graph
Someone hands you a number theory problem. No nodes. No edges. Just integers and divisibility. You stare at it for twenty minutes, then realize: the remainders are the nodes, and arithmetic operations are the edges.
This is the core pattern of implicit graphs. The problem never says "graph." You build one from scratch.
Problem: ARC084-B Small Multiple
Given an integer \(K\), find the minimum digit sum among all positive multiples of \(K\).
Constraints: \(2 \le K \le 10^5\).
At first this looks like pure number theory. Enumerate multiples of \(K\) and check digit sums? The smallest multiple could be astronomically large. Brute force is hopeless.
The Key Remodeling
Think about how you build a number digit by digit. You start with nothing, and at each step you either:
- Append a zero — multiply the current number by 10. Digit sum unchanged. Cost: 0.
- Increment the last digit — add 1. Digit sum increases by 1. Cost: 1.
Every positive integer can be built by some sequence of these two operations starting from 1. The number 203 is: start at 1 (cost 1), multiply by 10 (cost 0) twice to get 100, add 1 twice to get 102 (cost 2), multiply by 10 to get 1020 (cost 0), add 3 to get 1023... wait, that gives 1023 not 203.
Actually, start at 2 (that's: start at 1, then +1, cost 2). Then ×10 to get 20 (cost 0). Then ×10 to get 200 (cost 0). Then +1 three times to get 203 (cost 3). Total cost = 2 + 3 = 5, which is the digit sum of 203.
💡 Key insight. The total cost of building a number through ×10 and +1 operations equals its digit sum. We want the cheapest way to build any multiple of K.
Building the Graph
We don't care about the actual number — only its remainder mod \(K\). Two numbers with the same remainder behave identically for divisibility.
Nodes: \(\{0, 1, 2, \ldots, K-1\}\) — remainders modulo \(K\).
Edges:
- \(r \to (r \times 10) \bmod K\), cost 0 (append zero).
- \(r \to (r + 1) \bmod K\), cost 1 (increment digit).
Source: Node 1 with initial cost 1. We start from the number 1, which has digit sum 1 and remainder \(1 \bmod K\).
Target: Node 0. Any number with remainder 0 is a multiple of \(K\).
The answer is the shortest path from node 1 to node 0.
Why 0-1 BFS
Edge weights are only 0 or 1. Standard BFS doesn't handle weighted edges. Dijkstra works but is overkill. 0-1 BFS is the perfect fit: use a deque, push cost-0 edges to the front and cost-1 edges to the back.
#include <bits/stdc++.h>
using namespace std;
int main() {
int K;
cin >> K;
vector<int> dist(K, INT_MAX);
deque<int> dq;
dist[1] = 1;
dq.push_back(1);
while (!dq.empty()) {
int r = dq.front();
dq.pop_front();
// Append zero: cost 0
int nxt0 = (r * 10LL) % K;
if (dist[r] < dist[nxt0]) {
dist[nxt0] = dist[r];
dq.push_front(nxt0);
}
// Increment: cost 1
int nxt1 = (r + 1) % K;
if (dist[r] + 1 < dist[nxt1]) {
dist[nxt1] = dist[r] + 1;
dq.push_back(nxt1);
}
}
cout << dist[0] << endl;
return 0;
}
Complexity: \(O(K)\) nodes, each with exactly 2 edges. Total: \(O(K)\) time and space.
Trace: K = 6
Nodes: {0, 1, 2, 3, 4, 5}. Start at node 1, cost 1. Target: node 0.
Edge table (computed once):
| From r | ×10 → (r·10)%6 | +1 → (r+1)%6 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 4 | 2 |
| 2 | 2 | 3 |
| 3 | 0 | 4 |
| 4 | 4 | 5 |
| 5 | 2 | 0 |
0-1 BFS trace:
| Step | Pop | dist[pop] | ×10 edge | +1 edge | Deque after | dist[] |
|---|---|---|---|---|---|---|
| init | — | — | — | — | [1] | dist[1]=1, rest ∞ |
| 1 | 1 | 1 | 1→4, cost 1 < ∞ ✓ | 1→2, cost 2 < ∞ ✓ | [4, 2] | dist[4]=1, dist[2]=2 |
| 2 | 4 | 1 | 4→4, cost 1 = 1 ✗ | 4→5, cost 2 < ∞ ✓ | [2, 5] | dist[5]=2 |
| 3 | 2 | 2 | 2→2, cost 2 = 2 ✗ | 2→3, cost 3 < ∞ ✓ | [5, 3] | dist[3]=3 |
| 4 | 5 | 2 | 5→2, cost 2 = 2 ✗ | 5→0, cost 3 < ∞ ✓ | [3, 0] | dist[0]=3 |
| 5 | 3 | 3 | 3→0, cost 3 = 3 ✗ | 3→4, cost 4 > 1 ✗ | [0] | — |
| 6 | 0 | 3 | 0→0, ✗ | 0→1, cost 4 > 1 ✗ | [] | — |
Answer: 3. The multiple of 6 with minimum digit sum is 12 (digit sum 3) or 30 (digit sum 3).
Problem: AGC020-C — Simple Calculator (Variant)
You have a calculator starting at some integer \(X\) and want to reach integer \(Y\). Available operations: +1, −1, and negate (multiply by −1). Find the minimum number of button presses.
The trick: model this as BFS on states \((|value|, sign)\). The sign flips with negation. Moving toward zero by −1 is sometimes faster than incrementing. The graph has \(O(|X| + |Y|)\) states, and BFS finds the answer directly.
⚠ Gotcha. Don't model the state as just the integer value — the search space is unbounded. Bound it by observing you never need to go more than 1 past max(|X|, |Y|).
Problem: LC 752 — Open the Lock
A lock has 4 circular dials, each showing digits 0–9. Each move turns one dial up or down by 1 (9 wraps to 0 and vice versa). Given a list of "deadend" combinations and a target, find the minimum moves from "0000" to the target.
Implicit graph:
- Nodes: All 10,000 four-digit combinations.
- Edges: Each node connects to 8 neighbors (4 dials × 2 directions).
- Blocked nodes: Deadend combinations.
Plain BFS from "0000" to target, skipping deadends.
int openLock(vector<string>& deadends, string target) {
unordered_set<string> dead(deadends.begin(), deadends.end());
if (dead.count("0000")) return -1;
queue<pair<string, int>> q;
unordered_set<string> visited;
q.push({"0000", 0});
visited.insert("0000");
while (!q.empty()) {
auto [code, steps] = q.front();
q.pop();
if (code == target) return steps;
for (int i = 0; i < 4; i++) {
for (int d : {-1, 1}) {
string next = code;
next[i] = '0' + (next[i] - '0' + d + 10) % 10;
if (!visited.count(next) && !dead.count(next)) {
visited.insert(next);
q.push({next, steps + 1});
}
}
}
}
return -1;
}
The state space is fixed at 10,000 nodes. BFS runs in \(O(10^4 \times 8)\) — essentially instant.
💡 Key insight. The "lock" is never described as a graph. But every combination is a node and every dial turn is an edge. The moment you see "minimum moves" on a finite state space, think BFS.
The Pattern
When the problem gives you numbers and arithmetic operations:
- Identify the state. What matters? Often a remainder, a digit configuration, or a bounded value.
- Identify the transitions. Each operation is an edge. Assign costs based on what you're minimizing.
- Choose the algorithm. Costs all 1 → BFS. Costs 0 and 1 → 0-1 BFS. Arbitrary non-negative → Dijkstra.
The graph is never given. You synthesize it from the problem's arithmetic.
Common Mistakes
Unbounded state space. If you model "the current number" as the state, you get infinitely many nodes. Use remainders, digit sums, or other bounded invariants instead.
Forgetting the starting cost. In the Small Multiple problem, node 1 starts at cost 1 (digit sum of the number 1), not cost 0. The "source" has a nonzero initial cost because you're already committed to starting with a nonzero digit.
Using Dijkstra when 0-1 BFS suffices. Both give correct answers, but 0-1 BFS is \(O(V + E)\) while Dijkstra is \(O((V + E) \log V)\). For \(K = 10^5\), this matters.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ARC084-B Small Multiple | atcoder.jp/contests/arc084/tasks/arc084_b | Medium |
| LC 752 — Open the Lock | leetcode.com/problems/open-the-lock | Medium |
| LC 127 — Word Ladder | leetcode.com/problems/word-ladder | Hard |