Highway Tolls
We are given a connected undirected graph with N vertices and M edges. Two hidden vertices s t were chosen. For each query we assign every edge weight A or B (A < B), and the grader returns the shortest-path distance...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
We are given a connected undirected graph with $N$ vertices and $M$ edges. Two hidden vertices $s \neq t$ were chosen. For each query we assign every edge weight $A$ or $B$ ($A < B$), and the grader returns the shortest-path distance between $s$ and $t$ in that weighted graph. We must recover $s$ and $t$ using few queries.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observation
Let $W$ be the answer when every edge has weight $A$. Then $W/A$ is the length of a shortest $s$--$t$ path in the unweighted graph.
Now fix any ordering of the edges. If we turn a prefix of that order from weight $A$ to weight $B$, the answer stays equal to $W$ until the prefix first hits an edge that belongs to some shortest $s$--$t$ path. From that point on the answer becomes larger than $W$.
Lemma.
For any fixed edge order, binary search on the prefix length finds the smallest-indexed edge that belongs to some shortest $s$--$t$ path.
Proof.
If the prefix contains no edge from any shortest path, one shortest path still has total weight $W$. Once the prefix contains an edge from some shortest path, every shortest path using that edge becomes more expensive, hence the minimum distance increases. This is a monotone predicate, so binary search applies.
Finding One Shortest-Path Edge
First, use the original edge indices as the ordering and apply the lemma above. This yields one edge $e = (u, v)$ that lies on a shortest $s$--$t$ path.
Compute unweighted distances from $u$ and from $v$: \[ d_u(x), \qquad d_v(x). \]
Define two regions: \[ S = \{x \mid d_u(x) < d_v(x)\}, \qquad T = \{x \mid d_v(x) < d_u(x)\}. \]
Because $e$ lies on a shortest path, one hidden endpoint is in $S$ and the other is in $T$. Intuitively, before crossing edge $e$ the path is strictly closer to $u$, and after crossing it the path is strictly closer to $v$.
Recovering One Endpoint Inside a Region
Consider region $S$ rooted at $u$; the same argument is applied symmetrically to region $T$ rooted at $v$.
Build a BFS tree of the subgraph induced by vertices in $S$. Order its tree edges by nondecreasing depth from the root. We want to binary search for the last tree edge on the shortest-path segment from $u$ to the hidden endpoint inside $S$.
To make this valid, every edge that could create an alternative shortest path must be forced to weight $B$:
every edge leaving the region,
every edge between the two regions (except the already-known critical edge $e$),
every non-tree edge that still goes from depth $d$ to depth $d+1$ inside the BFS layering, because such an edge can also belong to a shortest path from the root.
After that, any path of cost $W$ must use the BFS-tree path from the root to the hidden endpoint inside the region. Therefore the predicate
\centerline{``does the set of tree edges with order at least $\texttt{mid}$ intersect the hidden path segment?''}
is monotone, so another binary search finds the last tree edge on that segment. If no such edge exists, the root itself is the hidden endpoint.
Algorithm
Query all edges with weight $A$ and store the baseline distance $W$.
Binary search on the original edge order to find one edge $e = (u, v)$ on a shortest $s$--$t$ path.
Run BFS from $u$ and from $v$ to obtain $d_u$ and $d_v$.
In the region $S = \{x \mid d_u(x) < d_v(x)\}$, build the BFS tree, force all other candidate edges to weight $B$, and binary search for the last tree edge on the hidden path segment. This gives one endpoint.
Repeat symmetrically in region $T$ to obtain the other endpoint.
Complexity
Queries: $1 + \lceil \log_2 M \rceil + 2\lceil \log_2 N \rceil$.
Time: $O(N + M)$ preprocessing for BFS plus $O((N + M)\log N)$ total local work.
Space: $O(N + M)$.
This comfortably fits the official query limit.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// Grader functions:
long long ask(vector<int> w);
void answer(int s, int t);
namespace {
int m_edges;
int numbered_edges;
long long base_distance;
vector<int> weights;
vector<int> edge_order;
vector<int> edge_child;
vector<vector<pair<int, int>>> adj; // (edge id, neighbor)
int get_first_edge() {
int lo = 0, hi = m_edges - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
for (int e = 0; e < m_edges; e++) {
weights[e] = (edge_order[e] <= mid);
}
if (ask(weights) != base_distance) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
int get_last_edge() {
int lo = -1, hi = numbered_edges - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
for (int e = 0; e < m_edges; e++) {
weights[e] = (edge_order[e] >= mid);
}
if (ask(weights) != base_distance) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
vector<int> bfs_dist(int root, int n) {
vector<int> dist(n, -1);
queue<int> q;
dist[root] = 0;
q.push(root);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto [edge_id, to] : adj[v]) {
if (dist[to] == -1) {
dist[to] = dist[v] + 1;
q.push(to);
}
}
}
return dist;
}
int find_endpoint(int root, int other_root, int critical_edge,
const vector<int>& dist_root,
const vector<int>& dist_other,
int n) {
edge_order.assign(m_edges, -1);
edge_child.assign(m_edges, -1);
numbered_edges = 0;
vector<int> tree_dist(n, -1);
queue<int> q;
tree_dist[root] = 0;
q.push(root);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto [edge_id, to] : adj[v]) {
if (dist_root[to] < dist_other[to]) {
if (tree_dist[to] == -1) {
tree_dist[to] = tree_dist[v] + 1;
edge_child[numbered_edges] = to;
edge_order[edge_id] = numbered_edges++;
q.push(to);
} else if (tree_dist[to] == tree_dist[v] + 1) {
// A shortest-path edge inside the region, but not the chosen BFS-tree edge.
edge_order[edge_id] = n;
}
} else if (edge_id != critical_edge) {
// Keep all cross-region edges heavy so shortest paths are forced through the tree.
edge_order[edge_id] = n;
}
}
}
int last = get_last_edge();
return (last == -1 ? root : edge_child[last]);
}
} // namespace
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
(void)A;
(void)B;
m_edges = (int)U.size();
adj.assign(N, {});
for (int e = 0; e < m_edges; e++) {
adj[U[e]].push_back({e, V[e]});
adj[V[e]].push_back({e, U[e]});
}
weights.assign(m_edges, 0);
base_distance = ask(weights);
edge_order.resize(m_edges);
iota(edge_order.begin(), edge_order.end(), 0);
int critical_edge = get_first_edge();
array<int, 2> roots = {U[critical_edge], V[critical_edge]};
array<vector<int>, 2> dist = {
bfs_dist(roots[0], N),
bfs_dist(roots[1], N)
};
int ans0 = find_endpoint(roots[0], roots[1], critical_edge, dist[0], dist[1], N);
int ans1 = find_endpoint(roots[1], roots[0], critical_edge, dist[1], dist[0], N);
answer(ans0, ans1);
}
int main() {
// Grader handles I/O.
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.