Acowdemia I Bronze

Problems and Contests
#1

Link to Bronze Acowdemia I: http://www.usaco.org/index.php?page=viewproblem2&cpid=1131.

I tried solving this problem using binary search.

#include <bits/stdc++.h>

using namespace std;

int32_t main()
{
    int N, L;
    cin >> N >> L;
    vector<int> c(N);
    for(int i=0; i<N; i++){
        cin >> c[i];
    }
    L = min(L, N);
    sort(begin(c), end(c), greater<int>());
    int l = 0, h = N;
    while(l < h) {
        int m = (l + h + 1)/2;
        int cit = 0;
        for(int i=0; i<m; i++){
            cit += max(0, m-c[i]);
            if(cit > L) break;
        }
        if(cit <= L)
        {
            l = m;
        }
        else
        {
            h = m-1;
        }
    }
    cout << l << '\n';
}

I check a particular m-index by going through the m most-cited papers and calculating the additional citations I need to get every c[i] up to m. I then check if this number of citations is at most L to see if the m-index is valid.

My code gives WA on test cases 9, 11, 12, 13. I think the error in my code might be that the survey can only cite each of the N papers at most once. However, I set L = min(L, N), and I don’t see how exactly my code overlooks the case when we double cite some paper. Can you please help me spot the error in my logic and its implications?

#2

I understood my problem. I am citing the i-th paper \max(0, m-c[i]) times. Therefore, I need to include if(m-c[i] > 1){ good = false; break; } in the for loop as well.

1 Like
#3

Wow, I missed this too in the problem, weird how you can get so many test cases while ignoring like a crucial part of problem