Nile
Observation: adjacent pairing suffices After sorting artifacts by weight, every optimal matching pairs only adjacent elements. Suppose an optimal matching pairs artifacts a < b and c < d (in sorted order) with a < c <...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
$N$ artifacts have weights $W[i]$, individual transport costs $A[i]$, and paired transport costs $B[i] < A[i]$. Two artifacts can share a boat if $|W[i] - W[j]| \le D$. For each of $Q$ queries (different values of $D$), find the minimum total transport cost.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Observation: adjacent pairing suffices
Lemma.
lem:adjacent After sorting artifacts by weight, every optimal matching pairs only adjacent elements.
Proof.
Suppose an optimal matching pairs artifacts $a < b$ and $c < d$ (in sorted order) with $a < c < b < d$. The ``crossing'' pairs $(a,b)$ and $(c,d)$ can be replaced by $(a,c)$ and $(b,d)$ without increasing cost (both new pairs have smaller weight differences, so they remain compatible, and $B$-costs depend only on individual artifacts, not on partner choice). Repeatedly uncrossing yields a non-crossing matching, which pairs only adjacent elements in sorted order.
DP for a fixed $D$
Sort artifacts by weight. Define $\mathrm{dp}[i]$ = minimum cost for artifacts $0, \ldots, i{-}1$:
where $\sigma$ is the sorted permutation.
Optimal $O((N+Q) \log N)$ offline algorithm
Key idea.
Sort queries by $D$. As $D$ increases, new adjacent pairs become eligible (their weight difference drops below $D$). We process pairs in order of their weight difference (smallest gap first) and ``activate'' each pair when $D$ reaches its gap.
Reformulation.
The DP above is equivalent to a minimum-weight path in a DAG: node $i$ has an edge of weight $A_{\sigma(i)}$ to node $i{+}1$ (solo transport), plus an edge of weight $B_{\sigma(i)} + B_{\sigma(i+1)}$ from $i$ to $i{+}2$ when the pair $(i, i{+}1)$ is eligible.
When a new pair $(i, i{+}1)$ is activated, it may improve the solution. We maintain the DP values using a DSU (Disjoint Set Union) structure. Each component of the DSU represents a maximal interval of artifacts where every adjacent pair within the interval is eligible. When components merge, we recompute the optimal matching for the merged interval.
DSU with interval DP.
For each component (interval $[\ell, r]$), store:
$f_0$: minimum cost for artifacts $\ell, \ldots, r$ when artifact $r$ is not paired with $r{+}1$ (i.e., $r$ is either alone or paired with $r{-}1$).
$f_1$: minimum cost when artifact $r$ is paired with the next artifact to the right (used when merging).
When activating pair $(i, i{+}1)$ and merging their components $[\ell_1, i]$ and $[i{+}1, r_2]$:
with similar formulas for $f_1^{\text{new}}$.
The total cost initially is $\sum A_{\sigma(i)}$. Each pair activation potentially reduces the cost. After processing all activations up to the current $D$, the answer is the global $\mathrm{dp}[N]$.
Efficient merging.
Each DSU merge is $O(\alpha(N))$ amortized. Sorting the $N{-}1$ adjacent gaps and $Q$ queries takes $O(N \log N + Q \log Q)$. Total: $O((N + Q) \log N)$.
Complexity
The implementation above uses the $O(NQ)$ DP approach.
Time: $O(N \log N + NQ)$ --- sorting once, then $O(N)$ per query.
Space: $O(N + Q)$.
Optimal complexity (sketch)
The offline DSU approach processes pairs in order of weight gap. Maintain for each DSU component its $f_0, f_1$ values (cost with/without the rightmost element open for pairing). When merging two components at a newly eligible gap, update the values in $O(1)$. Sort queries alongside gaps and read off answers at the appropriate moments.
This yields $O((N + Q) \log N)$ time. The main difficulty is correctly maintaining the boundary DP values during union; we refer to the official IOI 2024 editorial for the complete derivation.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// IOI 2024 - Nile
// N artifacts with weight W[i], solo cost A[i], paired cost B[i] (B[i] < A[i]).
// Two artifacts can pair iff |W[i] - W[j]| <= D.
// For Q queries with different D, find minimum total transport cost.
//
// Sort by weight. DP on sorted order: either ship artifact alone (cost A[i])
// or pair with previous artifact if weight difference <= D (cost B[i] + B[i-1]).
// Pairing adjacent in sorted order is optimal.
// Time: O(N log N + NQ).
vector<ll> calculate_costs(vector<int> W, vector<int> A,
vector<int> B, vector<int> E) {
int N = W.size();
int Q = E.size();
// Sort artifacts by weight
vector<int> idx(N);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b) {
return W[a] < W[b];
});
vector<int> sw(N), sa(N), sb(N);
for (int i = 0; i < N; i++) {
sw[i] = W[idx[i]];
sa[i] = A[idx[i]];
sb[i] = B[idx[i]];
}
vector<ll> ans(Q);
for (int q = 0; q < Q; q++) {
ll D = E[q];
// dp[i] = min cost for first i sorted artifacts
vector<ll> dp(N + 1, 0);
for (int i = 1; i <= N; i++) {
// Option 1: ship artifact i-1 alone
dp[i] = dp[i - 1] + sa[i - 1];
// Option 2: pair with previous artifact
if (i >= 2 && (ll)(sw[i - 1] - sw[i - 2]) <= D)
dp[i] = min(dp[i], dp[i - 2] + (ll)sb[i - 1] + sb[i - 2]);
}
ans[q] = dp[N];
}
return ans;
}
int main() {
int N, Q;
scanf("%d", &N);
vector<int> W(N), A(N), B(N);
for (int i = 0; i < N; i++)
scanf("%d %d %d", &W[i], &A[i], &B[i]);
scanf("%d", &Q);
vector<int> E(Q);
for (int i = 0; i < Q; i++) scanf("%d", &E[i]);
auto ans = calculate_costs(W, A, B, E);
for (int q = 0; q < Q; q++)
printf("%lld\n", ans[q]);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.