Reverse BFS

You're standing at 0 and need to reach \(10^{18}\). Each step, you can multiply by 2, 3, or 5, or add or subtract 1. Each operation has a different cost. Find the cheapest way.

Forward BFS? The state space is \(10^{18}\). Your computer doesn't have that much memory. Or time. Or patience.

---

The Problem: AGC044-A Pay to Win

Given target \(N\) (up to \(10^{18}\)) and four costs:

• Multiply current value by 2: cost \(A\)
• Multiply current value by 3: cost \(B\)
• Multiply current value by 5: cost \(C\)
• Add or subtract 1: cost \(D\)

Start at 0. Find the minimum total cost to reach exactly \(N\).

---

Why Forward Search Fails

From 0, you multiply up toward \(N\). The values you visit could be anything between 0 and \(10^{18}\). You can overshoot and subtract. You can multiply by 5 and then subtract 3. The reachable set is enormous and unpredictable.

No BFS or Dijkstra can explore \(10^{18}\) states.

Key insight. When the forward state space is infinite or astronomical, try reversing the direction. Start at the target and work backwards toward 0.

---

The Reverse Trick

Instead of building \(N\) from 0, decompose \(N\) toward 0.

From value \(v\), the reverse operations are:

• Divide by 2 (cost \(A\)): only if \(v\) is divisible by 2. Otherwise, round \(v\) to the nearest multiple of 2 first, paying \(D\) per unit.
• Divide by 3 (cost \(B\)): same idea with rounding.
• Divide by 5 (cost \(C\)): same idea with rounding.
• Walk to 0: just pay \(v \times D\).

At each step, \(v\) shrinks by a factor of at least 2. So the recursion depth is at most \(\log_2(10^{18}) \approx 60\). Each level branches into at most 6 subproblems (divide by 2/3/5, each with round-down or round-up). Total states visited: roughly \(6^{60}\)?

No. Most branches overlap. With memoization, each unique value of \(v\) is computed once. The number of unique values is small because each division collapses the space.

---

Branching at Each Value

For a value \(v\) and a divisor \(d\) (2, 3, or 5):

• Round down: go to \(\lfloor v/d \rfloor\), pay cost of division + \((v \bmod d) \times D\).
• Round up: go to \(\lfloor v/d \rfloor + 1\), pay cost of division + \((d - v \bmod d) \times D\).

If \(v\) is already divisible by \(d\), only round-down applies.

// For divisor d with operation cost op_cost:
ll rem = v % d;
best = min(best, solve(v / d) + op_cost + rem * D);        // round down
if (rem > 0)
    best = min(best, solve(v / d + 1) + op_cost + (d - rem) * D); // round up

Gotcha. Don't forget the round-up branch. If \(v = 7\) and \(d = 5\), rounding up to 10 costs \(3D\) but might lead to a much cheaper path through \(10/5 = 2\).

---

Trace: N = 11, A = 1, B = 2, C = 4, D = 8

Let's trace the recursive calls from \(v = 11\).

Call	\(v\)	Try /2	Try /3	Try /5	Walk to 0	Best
solve(11)	11	solve(5)+1+8, solve(6)+1+8	solve(3)+2+16, solve(4)+2+8	solve(2)+4+8, solve(3)+4+32	88	...
solve(5)	5	solve(2)+1+8, solve(3)+1+8	solve(1)+2+16, solve(2)+2+8	solve(1)+4+0	40	...
solve(1)	1	—	—	—	8	8
solve(2)	2	solve(1)+1+0	solve(0)+2+16, solve(1)+2+8	solve(0)+4+16, solve(1)+4+24	16	...
solve(1)	1	(memo)	—	—	8	8
solve(0)	0	—	—	—	0	0

Working upward:

• solve(0) = 0
• solve(1) = \(1 \times D = 8\)
• solve(2) = min(solve(1)+1, solve(0)+18, solve(1)+10, solve(0)+20, solve(1)+28, 16) = min(9, 18, 18, 20, 36, 16) = 9
• solve(3) = min(solve(1)+1+8, solve(2)+1+8, solve(1)+2+0, solve(0)+4+16, solve(1)+4+8, 24) = min(17, 18, 10, 20, 20, 24) = 10
• solve(5) = min(solve(2)+9, solve(3)+9, solve(1)+18, solve(2)+10, solve(1)+4, 40) = min(18, 19, 26, 19, 12, 40) = 12
• solve(6) = min(solve(3)+1, solve(2)+2, solve(1)+4+8, 48) = min(11, 11, 20, 48) = 11
• solve(4) = min(solve(2)+1, solve(1)+2+8, solve(2)+2+8, solve(0)+4+32, solve(1)+4+8, 32) = min(10, 18, 19, 36, 20, 32) = 10

Finally: solve(11) = min(solve(5)+9, solve(6)+9, solve(3)+18, solve(4)+10, solve(2)+12, solve(3)+36, 88) = min(21, 20, 28, 20, 21, 46, 88) = 20

---

Full Solution Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int T;
    cin >> T;
    while (T--) {
        ll N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;

        map<ll, ll> memo;
        function<ll(ll)> solve = [&](ll v) -> ll {
            if (v == 0) return 0;
            if (v == 1) return D;
            if (memo.count(v)) return memo[v];

            ll best = v * D;  // walk to 0

            auto tryDiv = [&](ll d, ll cost) {
                ll rem = v % d;
                best = min(best, solve(v / d) + cost + rem * D);
                if (rem > 0)
                    best = min(best, solve(v / d + 1) + cost + (d - rem) * D);
            };

            tryDiv(2, A);
            tryDiv(3, B);
            tryDiv(5, C);

            return memo[v] = best;
        };

        cout << solve(N) << "\n";
    }
    return 0;
}

---

Complexity Analysis

Each recursive call produces values by dividing by 2, 3, or 5 and possibly adding 1. The recursion tree has depth at most \(O(\log N)\). At each level, each value spawns at most 6 children, but memoization collapses duplicates.

In practice, the number of unique values visited is roughly \(O(\log^3 N)\). For \(N = 10^{18}\), that's a few thousand states at most. The map operations add a \(\log\) factor, giving total complexity around \(O(\log^4 N)\).

Key insight. The reverse direction exploits a fundamental asymmetry. Forward: each state has unbounded successors (multiply can go anywhere). Backward: each state has at most 6 predecessors (divide by 2/3/5, rounded two ways). Always search from the side with fewer branches.

---

Second Problem: ABC342-E Last Train

\(N\) cities, \(M\) train lines. Line \(i\) departs from city \(a_i\) at times \(l_i, l_i + d_i, l_i + 2d_i, \ldots, l_i + (k_i - 1)d_i\), arriving at city \(b_i\) after \(c_i\) time. Find the latest departure time from each city that still reaches city \(N\).

Forward Dijkstra finds earliest arrivals. We want latest departures. That's a maximization problem, and time flows backwards from the destination.

Reverse Dijkstra: process from \(N\) backwards.

• \(\text{dist}[N] = +\infty\) (you're already at the destination).
• For each edge \(a \to b\) with schedule, if you must arrive at \(b\) by time \(\text{dist}[b]\), the latest departure from \(a\) is the largest scheduled time \(t\) such that \(t + c \leq \text{dist}[b]\).
• Use a max-heap. Relax edges in reverse.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;

    // Store edges by destination (reverse adjacency)
    vector<vector<array<ll,5>>> radj(N + 1); // radj[b] = {l, d, k, c, a}
    for (int i = 0; i < M; i++) {
        ll l, d, k, c, a, b;
        cin >> l >> d >> k >> c >> a >> b;
        radj[b].push_back({l, d, k, c, a});
    }

    vector<ll> dist(N + 1, -1);
    priority_queue<pair<ll,int>> pq;  // max-heap
    dist[N] = LLONG_MAX;
    pq.push({dist[N], N});

    while (!pq.empty()) {
        auto [t, u] = pq.top(); pq.pop();
        if (t < dist[u]) continue;

        for (auto& [l, d, k, c, a] : radj[u]) {
            // Latest arrival at u is dist[u].
            // Need departure + c <= dist[u].
            ll deadline = (dist[u] == LLONG_MAX) ? LLONG_MAX : dist[u] - c;
            if (deadline < l) continue;  // can't catch any train

            ll last_sched = l + (k - 1) * d;
            ll latest_dep;
            if (last_sched <= deadline) {
                latest_dep = last_sched;
            } else {
                // Binary search: largest l + i*d <= deadline
                ll i = (deadline - l) / d;
                latest_dep = l + i * d;
            }

            if (latest_dep > dist[a]) {
                dist[a] = latest_dep;
                pq.push({dist[a], (int)a});
            }
        }
    }

    for (int i = 1; i < N; i++) {
        cout << (dist[i] == -1 ? "Unreachable" : to_string(dist[i])) << "\n";
    }
    return 0;
}

Gotcha. Be careful with LLONG_MAX arithmetic. When dist[u] is LLONG_MAX, computing dist[u] - c overflows. Guard with a special case or use a sentinel that's large but safe.

---

The Reverse Search Pattern

Both problems share the same core idea:

1. Forward is intractable. The state space explodes or the objective is backwards.
2. Reverse is sparse. Working from the target collapses the branching factor.
3. Use the right search algorithm. Dijkstra if costs vary. BFS if costs are uniform. DFS with memo if the graph is a DAG.

---

Exercises

1. In Pay to Win, what happens if \(D = 0\)? How does that simplify the recursion?

2. For Last Train, why does a max-heap (not min-heap) work? What invariant does it maintain?

3. Suppose Pay to Win also allowed \(\times 7\) with cost \(E\). How does this change the branching factor and complexity?

---

Problems

Problem	Link	Difficulty
AGC044-A -- Pay to Win	atcoder.jp/contests/agc044/tasks/agc044_a	Hard
ABC342-E -- Last Train	atcoder.jp/contests/abc342/tasks/abc342_e	Hard