Modular Layers

Hop. Skip. Jump. Three moves, then repeat. You can only stop at the end of a "jump." Landing mid-pattern doesn't count. You need exactly \(3k\) edges for some integer \(k\).

This constraint --- "step count must be divisible by \(k\)" --- can't be tracked by standard BFS. BFS finds the shortest path in total edges. It doesn't care whether that count is divisible by 3.

The fix: split the graph into \(k\) layers indexed by step count mod \(k\).

---

The Setup: AtCoder abc132_e (Hopscotch Addict)

Directed graph with \(N\) vertices and \(M\) edges. Find the minimum number of "hops" from \(S\) to \(T\), where each hop is exactly 3 consecutive edge traversals. If you can't reach \(T\) using a multiple of 3 edges, output \(-1\).

---

Why Standard BFS Fails

Standard BFS from \(S\) finds the shortest path to \(T\) in, say, 5 edges. But 5 isn't divisible by 3. The next shortest might be 6 edges --- that works, giving 2 hops. Or maybe no path with a multiple-of-3 edges exists at all.

You could run BFS and check if dist[T] % 3 == 0, but that only checks the shortest path. A longer path might satisfy the constraint while the shortest doesn't.

Gotcha. Shortest path to \(T\) uses 7 edges. A path using 9 edges also exists. Standard BFS returns 7, you reject it (7 % 3 != 0), and you miss 9. You can't fix this by incrementing --- you need to search systematically.

---

The 3-Layer Graph

Build three copies of the original graph, labeled layer 0, 1, and 2. Each layer represents "edges used so far, mod 3."

Edge \((u, v)\) in the original graph becomes:

• \((u, \text{layer } 0) \to (v, \text{layer } 1)\)
• \((u, \text{layer } 1) \to (v, \text{layer } 2)\)
• \((u, \text{layer } 2) \to (v, \text{layer } 0)\)

Every edge advances the layer by 1 (mod 3).

Layer 0:  S ---------> A ---------> B
                                      \
Layer 1:       A ---------> B ---------> T
                              \
Layer 2:            B ---------> T

Start at \((S, 0)\). Target: \((T, 0)\). Reaching \((T, 0)\) means you used a number of edges \(\equiv 0 \pmod{3}\).

---

BFS on the Expanded Graph

vector<vector<int>> dist(3, vector<int>(n, -1));
queue<pair<int,int>> q;
dist[0][s] = 0;
q.push({0, s});

while (!q.empty()) {
    auto [r, u] = q.front(); q.pop();
    int nr = (r + 1) % 3;
    for (int v : adj[u]) {
        if (dist[nr][v] == -1) {
            dist[nr][v] = dist[r][u] + 1;
            q.push({nr, v});
        }
    }
}

Answer: if dist[0][t] == -1, print \(-1\). Otherwise, dist[0][t] / 3.

Key insight. The BFS explores \(3N\) states, not \(N\). Each state (layer, vertex) is visited at most once. The shortest path to \((T, 0)\) automatically gives the fewest edges divisible by 3.

---

Trace: 4-Vertex Example

Directed graph: 1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 1 -> 4. Source = 1, Target = 4.

Edge	From	To
1	1	2
2	2	3
3	3	1
4	3	4
5	1	4

Shortest path 1 -> 4 uses 1 edge. But \(1 \bmod 3 \neq 0\). Path 1 -> 2 -> 3 -> 4 uses 3 edges. \(3 \bmod 3 = 0\). Answer = 1 hop.

BFS on 3-layer graph (states written as (mod, vertex)):

Step	Pop (r, u)	dist[r][u]	Push
1	(0, 1)	0	(1, 2) d=1, (1, 4) d=1
2	(1, 2)	1	(2, 3) d=2
3	(1, 4)	1	no outgoing edges from 4
4	(2, 3)	2	(0, 1) already visited, (0, 4) d=3
5	(0, 4)	3	target in layer 0!

Answer: dist[0][4] = 3 edges = 1 hop.

Notice: \((1, 4)\) was reached in 1 step (layer 1). That's the wrong layer. We need layer 0. The 3-edge path 1->2->3->4 lands in layer 0.

---

Why Not Check All Path Lengths?

You might think: run BFS, get shortest distance, then check multiples. But BFS gives only the shortest distance to each node. Longer paths satisfying the modular constraint aren't tracked.

Could you enumerate all reachable distances? That's unbounded. The layer trick encodes exactly the modular residue in \(O(kN)\) states.

Key insight. The modular layer graph doesn't enumerate all paths. It finds the shortest path with the right residue. That's precisely the question.

---

General Pattern: mod \(k\)

The construction generalizes to any modulus \(k\):

1. Create \(k\) layers of the graph.
2. Edge \((u, v)\) becomes \((u, r) \to (v, (r+1) \bmod k)\) for each layer \(r\).
3. BFS from \((S, 0)\).
4. Answer at \((T, 0)\), divided by \(k\).

Complexity: \(O(k \cdot (N + M))\) time, \(O(kN)\) space.

This works for any "step count \(\equiv 0 \pmod{k}\)" constraint. The value of \(k\) determines the layer count.

---

Variant: Reach With Specific Residue

What if you need step count \(\equiv r \pmod{k}\) instead of \(\equiv 0\)? Change the target layer:

• Start: \((S, 0)\).
• Target: \((T, r)\).
• Answer: dist[r][T], divided by \(k\) and rounded as needed.

---

Variant: Weighted Edges With Modular Constraint

If edges have weights and you need total weight \(\equiv 0 \pmod{k}\), the construction is the same but uses Dijkstra. The layer tracks cumulative weight mod \(k\), not step count.

// Dijkstra with modular layer
for (auto [v, w] : adj[u]) {
    int nr = (r + w % k + k) % k;  // weight mod k
    if (d + w < dist[nr][v]) {
        dist[nr][v] = d + w;
        pq.push({d + w, nr, v});
    }
}

Gotcha. With weighted edges, the layer transition is (r + w) % k, not (r + 1) % k. The layer tracks cumulative weight mod \(k\), not step count. Don't mix them up.

---

Connecting to Lesson 3

Lesson 3's parity layers are the special case \(k = 2\). The toggle pattern uses 2 layers; the modular pattern uses \(k\). Both encode a cyclical state that advances with each step.

Aspect	Parity (Lesson 3)	Modular (This lesson)
Layers	2	\(k\)
Transition	\((r+1) \bmod 2\)	\((r+1) \bmod k\)
Example	alternating colors	hop-skip-jump
Typical algorithm	BFS / 0-1 BFS	BFS / Dijkstra

The difference: parity layers usually have controllable transitions (toggles). Modular layers usually have forced transitions (every step advances the phase).

---

Self-Loops and Padding

What if the graph has self-loops? A self-loop at vertex \(u\) lets you "waste" a step without moving. In the layered graph, a self-loop creates an edge from \((u, r)\) to \((u, (r+1) \bmod k)\).

This can be powerful. If you reach \(T\) in the wrong layer, a self-loop at \(T\) lets you cycle through layers until you land in layer 0. Without self-loops, you might need to leave \(T\) and come back.

Key insight. If \(T\) has a self-loop (or you can add one for free), any reachable state \((T, r)\) can reach \((T, 0)\) by taking at most \(k-1\) extra steps.

---

Exercises

1. Layer count. A problem requires path length divisible by 5. How many layers? What's the state?

2. Self-loops. Vertex \(T\) has a self-loop. You reach \((T, 2)\) in the 3-layer graph. How many extra steps to reach \((T, 0)\)? What path do you take?

3. Tighter bound. You need path length \(\equiv 2 \pmod{7}\). Source = 1, Target = \(N\). What's your start state? Target state?

---

Problems

Problem	Link	Difficulty
AtCoder abc132_e --- Hopscotch Addict	atcoder.jp/contests/abc132/tasks/abc132_e	Medium
LC 1129 --- Shortest Path with Alternating Colors	leetcode.com/problems/shortest-path-with-alternating-colors	Medium