Candy for Later Rivals
National Olympiad — National round (2017 season)
Submission name: candy.cpp
Problem summary
Children receive token counts in order. A child’s achievement is the number of later children with at most that child’s token count. An achievement of zero earns no candy; otherwise the candy count is achievement plus token count. Find the greatest candy count. If nobody earns candy, output the largest number of children with pairwise distinct token counts.
Input
N followed by N token counts.
Output
The maximum candy count, or the stated distinct-count answer if every achievement is zero.
Constraints
1 ≤ N ≤ 100000; 1 ≤ token count ≤ m ≤ 5000. The value m is a bound and is not supplied in the input.
Worked example
An independently prepared example for this explanation.
Input
12 56 61 14 7 61 9 61 64 25 66 61 55
Output
69
Solution analysis
- Scan from right to left. Then the token counts of later children are exactly the counts already inserted into a frequency structure. A prefix-frequency query up to the current token count gives the achievement.
- Use a Fenwick tree over values 1 through 5000 to support each prefix query and insertion in logarithmic time. Evaluate the candy score only when the achievement is positive, then insert the current child.
- In the sample, the second child has 61 tokens and eight later children have at most 61, earning 69 candies. If all achievements are zero, no earlier value can be at least a later value; the whole sequence is strictly increasing, so all N token counts are distinct and the fallback answer is N.
Why it works
At each right-to-left step the tree stores exactly the later children, so its prefix sum counts precisely those with token count at most the current value. Every positive-achievement candy score is evaluated, and their maximum is correct. If none is positive, every pair is increasing in index order, proving that the maximum distinct subset has size N.
Watch out. Count equal token values as well as smaller ones. Children with achievement zero do not receive their token count in candies.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> tokens(n);
for (int &value : tokens) {
cin >> value;
}
vector<int> tree(5001, 0);
int answer = 0;
// The Fenwick tree contains only children to the right of i.
for (int i = n - 1; i >= 0; --i) {
int achievement = 0;
for (int index = tokens[i]; index > 0; index -= index & -index) {
achievement += tree[index];
}
if (achievement > 0) {
answer = max(answer, tokens[i] + achievement);
}
for (int index = tokens[i]; index <= 5000; index += index & -index) {
++tree[index];
}
}
cout << (answer == 0 ? n : answer) << '\n';
}