Nested Ball Intervals
National Olympiad — National round (2015 season)
Submission name: balls.cpp
Problem summary
Starting from the full row, repeatedly extract its widest nonempty consecutive subrow whose first weight is strictly smaller than the current first weight and whose last weight is strictly smaller than the current last weight. Continue on that extracted subrow. Sum the lengths of extracted subrows and count the moves. This is the per-move-maximal interpretation used by the official analysis.
Source clarification. The statement asks for a globally maximum extracted total, but the official analysis (https://infos.infosbg.com/files/Contests/NOI-3/2015/day2/E/analyses/balls_analysis.pdf) specifies the widest next interval greedy algorithm. Those claims conflict: for [10,1,9,8,7,6,5,6,7,8,9,1,10], greedy yields 11 in one move, while the valid nested lengths 9+7+5+3+1 yield 25. This lesson implements the official per-move-maximal interpretation and makes no global-optimality claim.
Input
N followed by N positive ball weights.
Output
The total extracted length and the number of moves.
Constraints
1 ≤ N ≤ 1,000,000; weights 1–1,000,000.
Worked example
An independently prepared example for this explanation.
Input
10 56 61 14 7 9 95 25 82 63 75
Output
11 2
Solution analysis
- Keep the current interval [left, right]. Its next left endpoint must have a weight smaller than a[left], so scan rightward for the first such position. Its next right endpoint must be smaller than a[right], so scan leftward for the last such position.
- If these positions do not cross, they define the widest valid extracted subrow. Add its length to a 64-bit total, count one move, and make it the current interval. If they cross, there is no valid extraction. The boundaries only move inward, giving a linear scan.
- In the sample the first extracted interval is [14, 7, 9, 95, 25, 82, 63], of length 7. Within it the next interval is [7, 9, 95, 25], of length 4. Its first weight 7 admits no smaller internal first endpoint, so the process stops with total 11 and two moves.
Why it works
For a fixed current interval, every legal extracted left endpoint is at or after the first value smaller than the current first value. Every legal extracted right endpoint is at or before the last value smaller than the current last value. If the two selected endpoints cross, no interval is legal. Otherwise their interval is legal and contains every other legal choice, hence maximizes this move’s length. Repeating proves the implementation follows the per-move-maximal process. This does not prove global optimality over arbitrary chains.
Watch out. Both comparisons are strict. The total can exceed 32-bit range. Do not claim the greedy choice globally maximizes the sum over all possible chains: that assertion is false.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> weight(n);
for (int &value : weight) {
cin >> value;
}
int left = 0;
int right = n - 1;
long long total = 0;
int moves = 0;
while (left < right) {
// Widest next interval: earliest smaller left end, latest smaller right end.
int nextLeft = left + 1;
int nextRight = right - 1;
while (nextLeft < right && weight[nextLeft] >= weight[left]) {
++nextLeft;
}
while (nextRight > left && weight[nextRight] >= weight[right]) {
--nextRight;
}
if (nextLeft > nextRight) {
break;
}
total += nextRight - nextLeft + 1;
++moves;
left = nextLeft;
right = nextRight;
}
cout << total << ' ' << moves << '\n';
return 0;
}