Wiring
We have red and blue points on a line. Each point must be incident to at least one wire of the opposite color, and the cost of a wire is the distance between its endpoints.
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
We have red and blue points on a line. Each point must be incident to at least one wire of the opposite color, and the cost of a wire is the distance between its endpoints.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Minimum Edge Cover View
This is a weighted edge-cover problem on the complete bipartite graph (reds on one side, blues on the other).
For each red point $r_i$, let \[ c_r(i)=\min_j |r_i-b_j|, \] and similarly for each blue point $b_j$ let \[ c_b(j)=\min_i |r_i-b_j|. \]
If every vertex chooses its cheapest incident edge independently, we pay \[ \text{base}=\sum_i c_r(i)+\sum_j c_b(j). \] Whenever we replace the two individual cheapest choices of $(r_i,b_j)$ by a single shared edge $(r_i,b_j)$, we save \[ c_r(i)+c_b(j)-|r_i-b_j|. \] Therefore, \[ \text{answer}=\text{base}-\text{(maximum total savings of a matching)}. \]
Savings on One Boundary
Merge all points and group consecutive equal colors into blocks. Positive savings occur only across one boundary between two adjacent blocks.
Consider adjacent blocks \[ a_1 < \dots < a_p < b_1 < \dots < b_q. \] Let $u$ be the closest opposite-colored point on the left of the $a$-block (or $-\infty$ if none exists), and let $v$ be the closest opposite-colored point on the right of the $b$-block (or $+\infty$ if none exists).
For one pair $(a_i,b_j)$ the saving has the separable form \[ (b_1-a_p) + \min\!\bigl(0,\ 2a_i-(u+b_1)\bigr) + \min\!\bigl(0,\ (v+a_p)-2b_j\bigr). \]
Hence for a fixed boundary, if we choose exactly $t$ matched pairs:
we take the best $t$ vertices from the left block, which is a suffix;
we take the best $t$ vertices from the right block, which is a prefix.
So the best profit for exactly $t$ pairs across one boundary is easy to precompute with prefix/suffix sums.
DP on the Block Chain
Let $P_k(t)$ be the best profit for taking exactly $t$ matching edges across boundary $k$. If block $k$ has size $sz_k$, then the numbers of matching edges on its left and right boundaries must satisfy \[ t_{k-1}+t_k \le sz_k. \]
This gives a simple DP on the path of block boundaries: \[ dp_k(t_k)=P_k(t_k)+ \max_{t_{k-1}\le sz_k-t_k} dp_{k-1}(t_{k-1}). \] The transition is optimized with prefix maxima.
Complexity
Time: $O(N)$ after sorting the points.
Space: $O(N)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long min_total_length(vector<int> r, vector<int> b) {
vector<pair<int, int>> pts;
pts.reserve(r.size() + b.size());
for (int x : r) pts.push_back({x, 0});
for (int x : b) pts.push_back({x, 1});
sort(pts.begin(), pts.end());
int n = (int)pts.size();
vector<pair<int, int>> groups;
for (int i = 0; i < n;) {
int j = i;
while (j < n && pts[j].second == pts[i].second) ++j;
groups.push_back({i, j - 1});
i = j;
}
int g = (int)groups.size();
vector<int> block_size(g);
ll base = 0;
const ll NEG_INF = -(1LL << 60);
const ll POS_INF = (1LL << 60);
for (int id = 0; id < g; ++id) {
auto [l, rr] = groups[id];
block_size[id] = rr - l + 1;
ll prev = (id > 0) ? pts[groups[id - 1].second].first : NEG_INF;
ll next = (id + 1 < g) ? pts[groups[id + 1].first].first : POS_INF;
for (int i = l; i <= rr; ++i) {
ll best = POS_INF;
if (prev != NEG_INF) best = min(best, (ll)pts[i].first - prev);
if (next != POS_INF) best = min(best, next - (ll)pts[i].first);
base += best;
}
}
vector<ll> dp_prev(1, 0);
for (int id = 0; id + 1 < g; ++id) {
auto [l1, r1] = groups[id];
auto [l2, r2] = groups[id + 1];
int p = r1 - l1 + 1;
int q = r2 - l2 + 1;
ll u = (id > 0) ? pts[groups[id - 1].second].first : NEG_INF;
ll v = (id + 2 < g) ? pts[groups[id + 2].first].first : POS_INF;
ll a_last = pts[r1].first;
ll b_first = pts[l2].first;
ll gap = b_first - a_last;
vector<ll> left_vals(p), right_vals(q);
for (int i = 0; i < p; ++i) {
ll cur = 2LL * pts[l1 + i].first - (u + b_first);
left_vals[i] = min(0LL, cur);
}
for (int i = 0; i < q; ++i) {
ll cur = (v + a_last) - 2LL * pts[l2 + i].first;
right_vals[i] = min(0LL, cur);
}
vector<ll> best_left(p + 1, 0), best_right(q + 1, 0);
for (int t = 1; t <= p; ++t) best_left[t] = best_left[t - 1] + left_vals[p - t];
for (int t = 1; t <= q; ++t) best_right[t] = best_right[t - 1] + right_vals[t - 1];
int cap = min(p, q);
vector<ll> profit(cap + 1, 0);
for (int t = 1; t <= cap; ++t) {
profit[t] = t * gap + best_left[t] + best_right[t];
}
vector<ll> prefix_best(dp_prev.size());
ll cur_best = NEG_INF;
for (int i = 0; i < (int)dp_prev.size(); ++i) {
cur_best = max(cur_best, dp_prev[i]);
prefix_best[i] = cur_best;
}
vector<ll> dp_cur(cap + 1, NEG_INF);
for (int t = 0; t <= cap; ++t) {
int lim = min(block_size[id] - t, (int)dp_prev.size() - 1);
if (lim >= 0) dp_cur[t] = prefix_best[lim] + profit[t];
}
dp_prev.swap(dp_cur);
}
ll best_profit = *max_element(dp_prev.begin(), dp_prev.end());
return base - best_profit;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<int> r(n), b(m);
for (int i = 0; i < n; ++i) scanf("%d", &r[i]);
for (int i = 0; i < m; ++i) scanf("%d", &b[i]);
printf("%lld\n", min_total_length(r, b));
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.