Mangoes
This is a weighted interval scheduling problem. Each tree defines a job with interval [d_i, d_i + k - 1] and weight a_i. We must select a set of jobs (at most one per day) to maximize total weight. Greedy with Max-Hea...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
There are $n$ mango trees. Tree $i$ has $a_i$ mangoes that ripen on day $d_i$ and fall off after $k$ days. That is, tree $i$'s mangoes can be harvested on any single day in the interval $[d_i,\, d_i + k - 1]$.
A harvester picks one tree per day, collecting all of its available mangoes. Maximize the total number of mangoes harvested.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
This is a weighted interval scheduling problem. Each tree defines a job with interval $[d_i,\, d_i + k - 1]$ and weight $a_i$. We must select a set of jobs (at most one per day) to maximize total weight.
Greedy with Max-Heap
Sweep through days from the earliest ripening day to the latest deadline:
Maintain a max-heap of available trees, keyed by mango count.
On each day, add all trees that ripen on or before this day.
Remove expired trees (deadline passed) from the top of the heap.
Pick the tree with the most mangoes and add its value to the total.
Lemma (Correctness).
The greedy strategy of always picking the highest-value available job is optimal for unit-time jobs on a timeline. This follows from the exchange argument: if an optimal solution picks a lower-value job on some day while a higher-value job is available, swapping them does not decrease the total.
Caveat. The greedy approach as stated has a subtle issue: popping expired entries only from the top of the heap may leave expired entries deeper in the heap. These stale entries are harmless because they will be discarded when they eventually reach the top. However, if the heap contains only expired entries on some day, the algorithm correctly produces no harvest for that day.
Potential Issue with Day-by-Day Sweep
If $d_{\max} + k$ is very large (up to $10^9$), iterating over every day is too slow. In that case, we should use event-driven processing: sort all trees by ripening day, and for each day that has at least one event (a tree ripening or an opportunity to harvest), process the heap. The number of meaningful events is at most $n$, so the total work is $O(n \log n)$.
Complexity Analysis
Time: $O(n \log n)$ for sorting and heap operations.
Space: $O(n)$ for the heap.
Example
Suppose $n = 3$, $k = 2$, with trees: $(d=1, a=5)$, $(d=2, a=3)$, $(d=2, a=8)$.
Day 1: Tree 1 available. Pick tree 1 (5 mangoes).
Day 2: Trees 2 and 3 available. Pick tree 3 (8 mangoes).
Day 3: Tree 2 still available (deadline is day 3). Pick tree 2 (3 mangoes).
Total: $5 + 8 + 3 = 16$.
Code
C++ solution used for this page.
// IOI 1991 - Problem 2: Mangoes
// Weighted job scheduling: each tree has interval [d, d+k-1] with value a.
// Pick at most one tree per day to maximize total harvest.
// DP with binary search, sorted by deadline. O(n log n)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
scanf("%d%d", &n, &k);
struct Tree {
int start, end, value;
};
vector<Tree> trees(n);
for (int i = 0; i < n; i++) {
int d, a;
scanf("%d%d", &d, &a);
trees[i] = {d, d + k - 1, a};
}
// Sort by end time (deadline)
sort(trees.begin(), trees.end(),
[](const Tree& a, const Tree& b) { return a.end < b.end; });
// dp[i] = max mangoes considering first i trees
vector<long long> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1]; // skip tree i-1
// Binary search: find last tree j whose end < tree i's start
int lo = 0, hi = i - 1, best = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (trees[mid].end < trees[i - 1].start) {
best = mid + 1;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
dp[i] = max(dp[i], dp[best] + trees[i - 1].value);
}
printf("%lld\n", dp[n]);
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.