Rods
Greedy Approach Sort rods in decreasing order: a_0 a_1 a_ N-1. If there exist consecutive indices i such that a_i < a_ i+1 + a_ i+2, then all rods a_0, a_1,, a_ i+2 can form a polygon, and the answer is their total su...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Given $N$ rods with positive integer lengths, select a subset of at least 3 rods that can form a closed polygon, maximizing the total length of selected rods. A set of rods can form a polygon if and only if the longest rod is strictly less than the sum of all other rods in the set.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Greedy Approach
Theorem.
Sort rods in decreasing order: $a_0 \ge a_1 \ge \cdots \ge a_{N-1}$. If there exist consecutive indices $i$ such that $a_i < a_{i+1} + a_{i+2}$, then all rods $a_0, a_1, \ldots, a_{i+2}$ can form a polygon, and the answer is their total sum.
Proof.
We need $a_0 < \sum_{j=1}^{k} a_j$ for a subset $\{a_0, \ldots, a_k\}$. Since $a_i < a_{i+1} + a_{i+2} \le a_{i-1} + a_i$ (by the sorted order), applying this relation repeatedly:
More directly: if we take all rods $\{a_0, \ldots, a_{i+2}\}$, the total sum $S = \sum_{j=0}^{i+2} a_j$. We need $a_0 < S - a_0$, i.e., $S > 2a_0$. Since $a_i < a_{i+1} + a_{i+2}$, the subsequence $a_0, a_1, \ldots$ does not decrease as fast as a geometric sequence, so the partial sums grow fast enough to satisfy $S > 2a_0$.
If no such consecutive triple exists, then $a_i \ge a_{i+1} + a_{i+2}$ for all $i$, meaning the sequence decreases at least as fast as Fibonacci numbers. For 64-bit integers, this limits $N$ to about 90. In this case, check all subsets of size $\ge 3$ (or observe that if no triple satisfies the condition, no polygon is possible).
Algorithm
Sort rods in decreasing order.
Scan consecutive triples: if $a_i < a_{i+1} + a_{i+2}$, the answer is the sum of all rods $a_0, \ldots, a_{i+2}$. (Actually, we want the maximum sum polygon, so take all $N$ rods if the polygon condition $a_0 < \text{rest}$ holds; otherwise try removing the largest.)
Specifically: check if total sum $> 2 a_0$ (all rods form a polygon). If not, remove $a_0$ and repeat. Since the Fibonacci-like bound limits iterations to $O(\log_\phi(\max\_value))$, this terminates quickly.
Complexity
Time: $O(N \log N)$.
Space: $O(N)$.
C++ Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> a(N);
for(int i = 0; i < N; i++) cin >> a[i];
sort(a.rbegin(), a.rend());
// Compute prefix sums
vector<long long> prefix(N + 1, 0);
for(int i = 0; i < N; i++) prefix[i+1] = prefix[i] + a[i];
// Try removing the largest rods one by one
for(int j = 0; j + 2 < N; j++){
// Subset: a[j], a[j+1], ..., a[N-1]
long long total = prefix[N] - prefix[j];
int count = N - j;
if(count >= 3 && total > 2 * a[j]){
cout << total << "\n";
return 0;
}
}
// No valid polygon possible
cout << 0 << "\n";
return 0;
}Notes
The key insight is that in a sorted sequence, if no three consecutive elements satisfy the triangle inequality $a_i < a_{i+1} + a_{i+2}$, the sequence decreases at least as fast as Fibonacci numbers, limiting the search. In practice, the loop terminates after very few iterations (at most about 90 for 64-bit values), so the algorithm is effectively $O(N \log N)$ dominated by sorting.
Code
C++ solution used for this page.
// IOI 2009 - Rods
// Greedy: sort descending, greedily include all rods and check polygon condition.
// A polygon can be formed iff the longest rod < sum of all others.
// O(N log N) time.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<long long> a(N);
for (int i = 0; i < N; i++) cin >> a[i];
sort(a.rbegin(), a.rend()); // decreasing order
// Start with all rods. Remove the largest one at a time until condition holds.
long long totalSum = 0;
for (int i = 0; i < N; i++) totalSum += a[i];
// Try removing the largest rods one by one until the polygon condition is met.
long long sum = totalSum;
for (int j = 0; j <= N - 3; j++) {
// With rods a[j], a[j+1], ..., a[N-1]:
// max is a[j], need sum - a[j] > a[j], i.e., sum > 2 * a[j]
// and at least 3 rods.
if ((N - j) >= 3 && sum > 2LL * a[j]) {
cout << sum << "\n";
return 0;
}
sum -= a[j];
}
// No valid polygon possible.
cout << 0 << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.