Day 2, Task 2: The School Bus
Two-Phase Bitmask DP For small n (up to about 15), we use an exact algorithm in two phases. Phase 1: Optimal Tour for Each Subset (Held--Karp TSP) For each subset S of locations whose total student count does not exce...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
A school bus starts at a depot, picks up students at $n$ locations, and returns. The bus has capacity $C$, so it may need multiple round trips. Each location $i$ has coordinates $(x_i, y_i)$ and $s_i$ students. Minimize the total Euclidean distance traveled across all trips.
This is a variant of the Capacitated Vehicle Routing Problem (CVRP).
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Two-Phase Bitmask DP
For small $n$ (up to about 15), we use an exact algorithm in two phases.
Phase 1: Optimal Tour for Each Subset (Held--Karp TSP)
For each subset $S$ of locations whose total student count does not exceed $C$, compute the shortest round trip from the depot visiting all locations in $S$.
Define $\text{tsp}[S][v]$ as the minimum distance to visit every location in $S$, starting from the depot and ending at location $v$. The recurrence is: \[ \text{tsp}[S][v] = \min_{u \in S \setminus \{v\}} \bigl(\text{tsp}[S \setminus \{v\}][u] + d(u, v)\bigr), \] with base case $\text{tsp}[\{v\}][v] = d(\text{depot}, v)$.
The round-trip cost for subset $S$ is: \[ \text{tour}[S] = \min_{v \in S} \bigl(\text{tsp}[S][v] + d(v, \text{depot})\bigr). \]
Phase 2: Set Partition DP
Partition all $n$ locations into capacity-feasible trips to minimize total cost: \[ \text{dp}[S] = \min_{\substack{T \subseteq S,\; T \ne \emptyset \\ \text{students}(T) \le C}} \bigl(\text{tour}[T] + \text{dp}[S \setminus T]\bigr), \] with $\text{dp}[\emptyset] = 0$.
Subsets of $S$ are enumerated using the standard bitmask trick: for (T = S; T > 0; T = (T-1) & S).
Complexity Analysis
Phase 1 (TSP): $O(2^n \cdot n^2)$ time, $O(2^n \cdot n)$ space.
Phase 2 (partition): $O(3^n)$ time (sum over all $S$ of the number of subsets of $S$ equals $3^n$).
Total: $O(2^n \cdot n^2 + 3^n)$ time, $O(2^n \cdot n)$ space.
Feasible for $n \le 15$.
Example
Input:
4 6
0 0 (depot)
1 1 3 (location 1: 3 students)
3 1 2 (location 2: 2 students)
2 3 4 (location 3: 4 students)
4 2 1 (location 4: 1 student)
Total students = 10, capacity = 6.
At least 2 trips are needed.The DP finds the optimal partition into trips and the shortest tour for each.
Notes
This problem is NP-hard in general (it contains TSP as a special case when $C \ge \sum s_i$).
The bitmask DP gives an exact solution for $n \le 15$.
For larger $n$, heuristics (nearest-neighbor, savings algorithm) or metaheuristics (simulated annealing) are necessary.
The subset enumeration identity $\sum_{S \subseteq [n]} 2^{|S|} = 3^n$ explains the $O(3^n)$ time for Phase 2.
Code
C++ solution used for this page.
// IOI 1993 - Day 2, Task 2: The School Bus
// Capacitated VRP: bus makes multiple round trips from depot.
// Bitmask DP: TSP on feasible subsets + set partition DP.
// O(2^n * n^2 + 3^n), feasible for n <= 15.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 16;
const double INF = 1e18;
int n, capacity;
int students[MAXN];
double dist_mat[MAXN + 1][MAXN + 1]; // 0 = depot, 1..n = locations
double tspDp[1 << MAXN][MAXN];
double tourCost[1 << MAXN];
int totalStudents[1 << MAXN];
bool feasible[1 << MAXN];
double partDp[1 << MAXN];
int main() {
scanf("%d%d", &n, &capacity);
double dx[MAXN + 1], dy[MAXN + 1];
scanf("%lf%lf", &dx[0], &dy[0]); // depot
for (int i = 1; i <= n; i++)
scanf("%lf%lf%d", &dx[i], &dy[i], &students[i - 1]);
// Compute distance matrix
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
dist_mat[i][j] = hypot(dx[i] - dx[j], dy[i] - dy[j]);
int full = (1 << n) - 1;
// Precompute feasibility for each subset
for (int S = 0; S <= full; S++) {
totalStudents[S] = 0;
for (int i = 0; i < n; i++)
if (S & (1 << i))
totalStudents[S] += students[i];
feasible[S] = (totalStudents[S] <= capacity);
}
// TSP DP: tspDp[S][v] = min cost from depot visiting all in S, ending at v
for (int S = 0; S <= full; S++)
for (int i = 0; i < n; i++)
tspDp[S][i] = INF;
for (int i = 0; i < n; i++)
tspDp[1 << i][i] = dist_mat[0][i + 1];
for (int S = 1; S <= full; S++) {
if (!feasible[S]) continue;
for (int v = 0; v < n; v++) {
if (!(S & (1 << v)) || tspDp[S][v] >= INF) continue;
for (int u = 0; u < n; u++) {
if (S & (1 << u)) continue;
int newS = S | (1 << u);
if (!feasible[newS]) continue;
double cost = tspDp[S][v] + dist_mat[v + 1][u + 1];
if (cost < tspDp[newS][u])
tspDp[newS][u] = cost;
}
}
}
// Compute round-trip tour cost for each feasible subset
for (int S = 0; S <= full; S++) {
tourCost[S] = INF;
if (!feasible[S]) continue;
if (S == 0) { tourCost[S] = 0; continue; }
for (int v = 0; v < n; v++) {
if (!(S & (1 << v))) continue;
tourCost[S] = min(tourCost[S], tspDp[S][v] + dist_mat[v + 1][0]);
}
}
// Set partition DP: partition all locations into feasible trips
for (int S = 0; S <= full; S++) partDp[S] = INF;
partDp[0] = 0;
for (int S = 1; S <= full; S++) {
for (int T = S; T > 0; T = (T - 1) & S) {
if (feasible[T] && tourCost[T] < INF)
partDp[S] = min(partDp[S], partDp[S ^ T] + tourCost[T]);
}
}
printf("%.2f\n", partDp[full]);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.