USACO 2017 December Contest Silver Division - My Cow Ate My Homework

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can use suffix minimum to compute the minimum for each suffix of values, and as we fix the amount of questions Bessie has eaten, we can compute the average for each possible number of questions Bessie has remaining in her set.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
#include <map>

using namespace std;

int main() {
    ifstream cin("homework.in");
    ofstream cout("homework.out");

    int n;
    cin >> n;
    vector<int> a(n), sa(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sa[n-1] = a[n-1];
    int sum = a[n-1];
    for(int i = n-2; i >= 0; i--) {
        sa[i] = min(a[i], sa[i+1]);
        sum += a[i];
    }
    map<double, vector<int>> freq;
    for(int i = 0; i < n-2; i++) {
        sum -= a[i];
        freq[(double)(sum - sa[i+1])/(double)(n-i-2)].push_back(i);
    }
    for(auto r : freq.rbegin()->second) {
        cout << r+1 << '\n';
    }
    return 0;
}