USACO 2021 US Open Contest Bronze Division - Acowdemia I

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Frequency Arrays solution

We can keep track using frequency arrays of how many times each number from \(0\) to \(10^5\) appears in Bessie's list. Then, in order to find the initial h-index, we will find the greatest \(i\) such that there are at least \(i\) papers cited at least \(i\) times, something which can be done by traversing the frequency array values.

The key observation is that we can only increase the h-index by one and in order to do this, we must make sure that we can increment enough values equal to \(x\) (where \(x\) is the initial h-index) in order to reach an h-index equal to \(x+1\).

Sorting solution

Sort the array and keep track of how many consecutive equal values you have. At each step, the index is either the number of values used so far or the current value.

You might increase the index by one if you can increase the index of at most L papers using the operation given in the statement.

Source codes

The source codes in C++ and Python can be seen below.

Frequency Arrays solution

#include <iostream>
#include <vector>

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> frq(100001);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        frq[x]++;
    }

    // find the current h_index
    int cnt = 0, h_index = 0, cnt_h = 0;
    for (int i = 0; i <= 100000; i++) {
        if (n - cnt >= i) {
            h_index = i;
            cnt_h = n - cnt - frq[i];
        }
        cnt += frq[i];
    }

    // check if we can improve the h_index by 1
    if (cnt_h + min(k, frq[h_index]) >= h_index + 1) {
        h_index++;
    }

    cout << h_index << '\n';
    return 0;
}

Sorting solution

#include <bits/stdc++.h>
using namespace std;

int n, v[100002], L;
int main()
{
    cin >> n >> L;
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    sort(v+1, v+n+1);

    int mx = 0;
    int cnteq = 0;
    for(int i = n; i >= 1; i--)
    {
        cnteq++;
        if(i < n && v[i] < v[i+1])
            cnteq = 1;
        mx = max(mx, min(v[i], n - i + 1));
        if(cnteq <= L && v[i] + 1 <= n - i + 1) 
            mx = max(mx, v[i] + 1);
    }

    cout << mx;
    return 0;
}

n, L = map(int, input().split())
v = list(map(int, input().split()))
v.sort()
mx = 0
cnteq = 0
for i in range(n-1, -1, -1):
    cnteq += 1
    if i < n-1 and v[i] < v[i+1]:
        cnteq = 1
    mx = max(mx, min(v[i], n - i))
    if cnteq <= L and v[i] + 1 <= n - i:
        mx = max(mx, v[i] + 1)
print(mx)