USACO 2021 US Open, Bronze Problem 1. Acowdemia I

Bessie the cow has enrolled in a computer science PhD program, driven by her love of computer science and also the allure of one day becoming "Dr. Bessie". Having worked for some time on her academic research, she has now published?NN?papers (1≤N≤1051≤N≤105), and her?ii-th paper has accumulated?cici?citations (0≤ci≤1050≤ci≤105) from other papers in the research literature.

Bessie has heard that an academic's success can be measured by their?hh-index. The?hh-index is the largest number?hh?such that the researcher has at least?hh?papers each with at least?hh?citations. For example, a researcher with?44?papers and respective citation counts?(1,100,2,3)(1,100,2,3)?has an?hh-index of?22, whereas if the citation counts were?(1,100,3,3)(1,100,3,3)?then the?hh-index would be?33.

To up her?hh-index, Bessie is planning to write a survey article citing several of her past papers. Due to page limits, she can include at most?LL?citations in this survey (0≤L≤1050≤L≤105), and of course she can cite each of her papers at most once.

Help Bessie determine the maximum?hh-index she may achieve after writing this survey.

Note that Bessie's research advisor should probably inform her at some point that writing a survey solely to increase one's?hh?index is ethically dubious; other academics are not recommended to follow Bessie's example here.

 

 

 

SAMPLE INPUT:

4 0
1 100 2 3

SAMPLE OUTPUT:

2

Bessie cannot cite any of her past papers. As mentioned above, the?hh-index for?(1,100,2,3)(1,100,2,3)?is?22.

 

SAMPLE INPUT:

4 1
1 100 2 3

SAMPLE OUTPUT:

3

If Bessie cites her third paper, then the citation counts become?(1,100,3,3)(1,100,3,3). As mentioned above, the?hh-index for these counts is?33.

 

 

Problem credits: Dhruv Rohatgi

USACO 2021 US Open, Bronze Problem 1. Acowdemia I 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Dhruv Rohatgi )

Let's suppose that?L=0L=0; then we just want to compute the?hh-index of Bessie's papers with no additional citations. To find this, we can sort the citation counts from largest to smallest, and find the largest?hh?such that the first?hh?papers all have at least?hh?citations. This can be done in one pass through the sorted counts.

Now let's consider how to use?LL?extra citations to increase the?hh-index. Since the survey cannot cite any one paper multiple times, it's not possible to increase the?hh-index by more than?11: the?(h+1)(h+1)-st most cited paper before the survey had at most?hh?citations, so afterwards it cannot have more than?h+1h+1?citations.

But it's not always possible to increase the?hh-index by one. When is it possible? Well, out of the top?hh?papers before the survey, some?kk?of them have exactly?hh?citations (and the rest have more than?hh). We need to cite each of these?kk?papers. Additionally, we need to cite the?(h+1)(h+1)-st most cited paper. So it's necessary that?L≥k+1L≥k+1. Finally, if the?(h+1)(h+1)-st most cited paper has less than?hh?citations, then we cannot hope to increase the?hh-index. Conversely, if it has?hh?citations (it cannot have more than?hh), and if?L≥k+1L≥k+1, then the?hh-index can be increased to?h+1h+1.

Below is Danny Mittal's code, which does a slight variation on the above idea. This program increments the citation counts of the?[h?L+2,h+1][h?L+2,h+1]-most cited papers (which we've seen is optimal) and checks what the new?hh-index is.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class AcowdemiaI {
 
    static int hIndex(Integer[] papers) {
        int h = papers.length;
        while (h > 0 && papers[h - 1] < h) {
            h--;
        }
        return h;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int l = Integer.parseInt(tokenizer.nextToken());
        Integer[] papers = new Integer[n];
        tokenizer = new StringTokenizer(in.readLine());
        for (int j = 0; j < n; j++) {
            papers[j] = Integer.parseInt(tokenizer.nextToken());
        }
        Arrays.sort(papers, Comparator.reverseOrder());
        int h = hIndex(papers);
        if (h != n) {
            for (int j = h; j >= 0 && j > h - l; j--) {
                papers[j]++;
            }
        }
        Arrays.sort(papers, Comparator.reverseOrder());
        System.out.println(hIndex(papers));
    }
}

[/hide]