Metal Processing Plant
Time limit4sMemory limit128 MB
Split all shipments into two groups so the sum of the largest pairwise distance inside each group is as small as possible.
- Level
Hard8 of 10
- Topics
- Graph, Union-find, Sorting
- Solved
- No attempts yet
Problem
Each month n ore shipments arrive. Pairwise distances d(i,j) measure similarity. For a subset S, define
D(S) = max_{i,j in S} d(i,j)
(zero when |S| ≤ 1). Partition all shipments into two groups A and B to minimize D(A) + D(B).
Input
- Line 1: integer n (1 ≤ n ≤ 200)
- Next n-1 lines: line i lists d(i,i+1) through d(i,n)
Output
The minimum possible value of D(A) + D(B)