USACO 2021 US Open Contest Bronze Division - Acowdemia I

Problem link: here

Solution Author: Stefan Dascalescu

Problem 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.

#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)