Towns
We are given distances only between the N leaves of a weighted tree. Internal vertices are the large cities. We must find the hub radius R, and for the full task also decide whether some optimal hub is balanced: after...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
We are given distances only between the $N$ leaves of a weighted tree. Internal vertices are the large cities. We must find the hub radius $R$, and for the full task also decide whether some optimal hub is balanced: after deleting it, every remaining component contains at most $N/2$ leaves.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Step 1: Find the Radius
Pick an arbitrary leaf $v$. Query all distances from $v$ and let $s$ be the farthest leaf. Then query all distances from $s$ and let $t$ be the farthest leaf from $s$. Now $d(s,t)$ is a diameter of the tree.
For any leaf $u$, define \[ p(u) = \frac{d(u,s) + d(v,s) - d(u,v)}{2}. \] This is exactly the distance from $s$ to the branching point where the path from $u$ meets the path $s \to v$. Hence the distinct values of $p(u)$ are precisely the vertices on the path $s \to v$ that matter for the answer.
If a vertex on that path is at distance $x$ from $s$, then its farthest leaf distance is \[ \max(x,\ d(s,t)-x). \] So the center(s) are the internal positions minimizing that value. There are at most two such positions.
Step 2: A Necessary Median Condition
Sort the multiset \[ B = \{\,p(u)\mid u \text{ is a leaf}\,\}. \] For a center at position $r$:
leaves with $p(u) < r$ lie in the $s$-side component;
leaves with $p(u) > r$ lie in the $v$-side component;
leaves with $p(u) = r$ branch off exactly at that center.
Therefore a balanced hub must satisfy \[ \#\{p(u) < r\} \le N/2 \quad\text{and}\quad \#\{p(u) > r\} \le N/2. \] Equivalently, $r$ must lie between the two medians of $B$. If the two medians are different, then any candidate center in that interval is automatically balanced, because one side already contains exactly $N/2$ leaves, so the group with $p(u)=r$ has size at most $N/2$.
Step 3: Unique-Median Case
The only nontrivial situation is when both medians are the same value $r$. Let \[ X = \{\,u \mid p(u) = r\,\}. \] Now we only need to know whether some component of $T-r$ inside this set has more than $N/2$ leaves.
For $x,y \in X$, the editorial observation is: \[ x,y \text{ are in the same component of } T-r \iff d(s,x) + d(s,y) - d(x,y) > 2r. \] So $X$ becomes a ``colored balls'' problem: each component is one color, and we only have an equality test.
We use the standard majority-elimination algorithm:
pair up surviving sets and compare representatives;
merge equal pairs, discard unequal pairs;
if one set survives, verify it against all discarded representatives.
This uses fewer than $3|X|/2 \le 3N/2$ extra distance queries. If no component of $X$ has size $> N/2$, the center is balanced.
Complexity
Queries: $(N-1) + (N-2)$ to find $s$ and the diameter, plus fewer than $3N/2$ in the unique-median case, for a total below $7N/2$.
Time: $O(N \log N)$ because we sort the projection values.
Space: $O(N)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// Grader-provided function.
int getDistance(int i, int j);
namespace {
int anchor_v = 0;
int anchor_s = 0;
vector<int> dist_from_v;
vector<int> dist_from_s;
unordered_map<unsigned long long, int> cached_queries;
unsigned long long make_key(int a, int b) {
if (a > b) swap(a, b);
return (static_cast<unsigned long long>(a) << 32) ^
static_cast<unsigned int>(b);
}
int query_distance(int a, int b) {
if (a == b) return 0;
if (a == anchor_v) return dist_from_v[b];
if (b == anchor_v) return dist_from_v[a];
if (a == anchor_s) return dist_from_s[b];
if (b == anchor_s) return dist_from_s[a];
unsigned long long key = make_key(a, b);
auto it = cached_queries.find(key);
if (it != cached_queries.end()) return it->second;
int value = getDistance(a, b);
cached_queries[key] = value;
return value;
}
bool same_component(int x, int y, long long pivot) {
long long shared =
static_cast<long long>(dist_from_s[x]) + dist_from_s[y] - query_distance(x, y);
return shared > 2 * pivot;
}
bool has_giant_component(const vector<int> &group, long long pivot, int total_leaves) {
struct Block {
int rep;
int size;
};
vector<Block> alive;
alive.reserve(group.size());
for (int leaf : group) alive.push_back({leaf, 1});
vector<Block> dead;
dead.reserve(group.size());
while (alive.size() > 1) {
vector<Block> next;
next.reserve(alive.size() / 2);
for (int i = 0; i + 1 < (int)alive.size(); i += 2) {
const Block &a = alive[i];
const Block &b = alive[i + 1];
if (same_component(a.rep, b.rep, pivot)) {
next.push_back({a.rep, a.size + b.size});
} else {
dead.push_back(a);
dead.push_back(b);
}
}
if (alive.size() % 2 == 1) dead.push_back(alive.back());
alive.swap(next);
}
if (alive.empty()) return false;
int majority_size = alive[0].size;
int candidate = alive[0].rep;
for (const Block &block : dead) {
if (same_component(candidate, block.rep, pivot)) {
majority_size += block.size;
}
}
return majority_size > total_leaves / 2;
}
} // namespace
int hubDistance(int N, int sub) {
anchor_v = 0;
dist_from_v.assign(N, 0);
cached_queries.clear();
for (int i = 1; i < N; ++i) dist_from_v[i] = getDistance(anchor_v, i);
anchor_s = 0;
for (int i = 1; i < N; ++i) {
if (dist_from_v[i] > dist_from_v[anchor_s]) anchor_s = i;
}
dist_from_s.assign(N, 0);
for (int i = 0; i < N; ++i) {
if (i == anchor_s) continue;
dist_from_s[i] = (i == anchor_v ? dist_from_v[anchor_s] : getDistance(anchor_s, i));
}
int diameter_endpoint = 0;
for (int i = 1; i < N; ++i) {
if (dist_from_s[i] > dist_from_s[diameter_endpoint]) diameter_endpoint = i;
}
long long diameter = dist_from_s[diameter_endpoint];
long long sv_length = dist_from_v[anchor_s];
vector<long long> projection(N);
vector<long long> positions;
positions.reserve(N);
for (int i = 0; i < N; ++i) {
projection[i] =
(static_cast<long long>(dist_from_s[i]) + sv_length - dist_from_v[i]) / 2;
positions.push_back(projection[i]);
}
sort(positions.begin(), positions.end());
positions.erase(unique(positions.begin(), positions.end()), positions.end());
long long radius = LLONG_MAX;
vector<long long> centers;
for (long long pos : positions) {
if (pos == 0 || pos == sv_length) continue;
long long eccentricity = max(pos, diameter - pos);
if (eccentricity < radius) {
radius = eccentricity;
centers.assign(1, pos);
} else if (eccentricity == radius) {
centers.push_back(pos);
}
}
if (radius == LLONG_MAX) return 0;
if (sub <= 2) return static_cast<int>(radius);
vector<long long> sorted_projection = projection;
sort(sorted_projection.begin(), sorted_projection.end());
long long median_left = sorted_projection[(N - 1) / 2];
long long median_right = sorted_projection[N / 2];
bool balanced = false;
for (long long center : centers) {
if (center < median_left || center > median_right) continue;
if (median_left != median_right) {
balanced = true;
break;
}
vector<int> attached_leaves;
attached_leaves.reserve(N);
for (int i = 0; i < N; ++i) {
if (projection[i] == center) attached_leaves.push_back(i);
}
if ((int)attached_leaves.size() <= N / 2 ||
!has_giant_component(attached_leaves, center, N)) {
balanced = true;
break;
}
}
return balanced ? static_cast<int>(radius) : -static_cast<int>(radius);
}
int main() {
// Grader handles interaction.
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.