Skip to content

Parametric Search

Binary search on parameter: check graph feasibility at each value

Sometimes the graph doesn't exist yet. It depends on a parameter you're optimizing. Binary search on the parameter, build the graph for each candidate value, check if it satisfies the property.

The Pattern

  1. Parameter: a value X you want to minimize (or maximize).
  2. Graph construction: for a given X, build a graph where edges exist based on X.
  3. Property check: does the graph satisfy some property (connectivity, shortest path ≤ threshold, etc.)?
  4. Binary search: the property is monotone in X. Binary search finds the optimal X.

Problem 1: ABC257-D — Jumping Takahashi 2

Problem: N trampolines at positions (x_i, y_i) with power P_i. A person with strength S can jump from trampoline i to j if P_i × S ≥ Manhattan distance(i, j). Find minimum S such that some starting trampoline can reach all others.

Why binary search works: if strength S works, any S' > S also works. Monotone.

For a fixed S: - Build directed graph: edge i → j exists if P_i × S ≥ |x_i - x_j| + |y_i - y_j|. - Check: does any node have full reachability? BFS/DFS from each node.

Binary search on S:

ll lo = 0, hi = 4e9;
while (lo < hi) {
    ll mid = (lo + hi) / 2;
    bool ok = false;
    for (int src = 0; src < n && !ok; src++) {
        // BFS from src
        vector<bool> vis(n, false);
        queue<int> q;
        q.push(src); vis[src] = true;
        int cnt = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = 0; v < n; v++)
                if (!vis[v] && p[u] * mid >= abs(x[u]-x[v]) + abs(y[u]-y[v])) {
                    vis[v] = true;
                    q.push(v);
                    cnt++;
                }
        }
        if (cnt == n) ok = true;
    }
    if (ok) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

Complexity: O(N² × log(max_dist) × N) — feasible for N ≤ 200.

⚠ Gotcha. The edge condition P_i × S ≥ dist(i,j) can be rewritten as S ≥ dist(i,j) / P_i. This means you can enumerate all critical S values (one per edge) and binary search over them, or even sort and use the exact threshold.

Problem 2: Typical90 #87 — Chokudai's Demand

Problem: Weighted graph with some edges having weight X (unknown). Binary search on X such that shortest path from 1 to N ≤ threshold.

For each candidate X: fill in the missing weights, run Dijkstra, check if dist[N] ≤ threshold.

Problem 3: LC 1631 — Path With Minimum Effort

Problem: Grid of heights. The "effort" of a path is the maximum absolute height difference along any edge. Minimize the maximum effort.

Binary search on effort E: for a given E, edge (u,v) exists if |height[u] - height[v]| ≤ E. Check connectivity from (0,0) to (H-1, W-1) via BFS/DFS.

Alternative: Dijkstra where dist[v] = min over all paths of max-edge-weight (minimax path). This avoids binary search entirely.

// Binary search approach
int lo = 0, hi = 1e6;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    // BFS: can we reach (H-1, W-1) using only edges with diff <= mid?
    if (canReach(mid)) hi = mid;
    else lo = mid + 1;
}
Signal Example
"Minimize X such that..." Min strength for full reachability
"Is there a value X where..." Does a shortest path ≤ K exist?
The graph structure depends on a parameter Edges appear/disappear based on threshold
The property is monotone in the parameter More strength → more edges → easier to reach

💡 Key insight. If the graph changes with a parameter and the desired property is monotone, binary search on the parameter and rebuild the graph each iteration.

Parametric Search vs State Expansion

These are different tools: - State expansion (Ch 6-9): the parameter is part of the traversal state. You track it per-node. - Parametric search: the parameter is fixed for the entire graph. You binary search over it externally.

State expansion: "I have 3 coins at this node." Parametric search: "What if everyone's jump strength is 42?"

Exercises

  1. In Jumping Takahashi 2, can you avoid the inner N loop by being smarter about which starting node to try?
  2. For LC 1631, which is faster: binary search + BFS, or modified Dijkstra? Analyze the complexity.
  3. Design a problem where parametric search on a graph parameter gives a log factor improvement over brute force.

Problems

Problem Link Difficulty
ABC257-D Jumping Takahashi 2 atcoder.jp Medium
Typical90 #87 Chokudai's Demand atcoder.jp Medium
LC 1631 Path With Minimum Effort leetcode.com Medium