Acowdemia I (Editorial)

Let us consider how to determine the $h$-index for a given array of numbers. First, sort the array in descending order. Then find the largest value $h$ such that the elements in positions from $1$ to $h$ are at least equal to $h$. In other words, we look for the maximum $h$ for which the condition a_h \ge h holds.

For example, in the following case the $h$-index is equal to $3$, since a_3 ≥ 3, but a_4 < 4.

After adding $l$ citations, the $h$-index cannot increase by more than $1$. Indeed, since a_{h+1} < h + 1, and each paper can be cited at most once, the maximum we can achieve is to increase a_{h + 1} by $1$ (if initially a_{h + 1} = h).

Next, starting from position h + 1 and moving towards smaller indices, increase the array elements by $1$. In other words, increase by $1$ all elements in the segment a[max(1, h - l + 2); h + 1].

After that, we sort the array in descending order again and recalculate the $h$-index. The resulting value is the answer.

Example

In the first example, Bessie cannot cite her own papers, so her $h$-index for the set (1, 100, 2, 3) is equal to $2$.

In the second example, if Bessie cites the third paper, the number of citations becomes (1, 100, 3, 3). In this case, the $h$-index increases to $3$.

Consider the following example. The numbers are already arranged in descending order. The $h$-index of this array is equal to $4$.

• Let l = 2. Increase the elements $a[4;5]$ by $1$ and then sort the array in descending order again. The $h$-index of the resulting array is still equal to $4$.

• Let l = 4. Increase the elements $a[2;5]$ by $1$ and then sort the array in descending order. As a result, the $h$-index of the resulting array will become equal to $5$.

Algorithm implementation

The hIndex function computes the $h$-index for an array that has already been sorted in descending order. Indexing starts from $1$. The function returns the maximum value of $i$ for which the condition v_i \ge i holds. If such an index does not exist (that is, the $h$-index of the array is $n$), then the function returns the value v.size() - 1, which is equal to $n$.

int hIndex(vector<int> &v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] < i) return i - 1;
  return v.size() - 1;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &l);
v.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &v[i]);

Sort the array in descending order, starting from the first element.

sort(v.begin() + 1, v.end(), greater<int>());

Compute the $h$-index of the original array.

h = hIndex(v);

Starting from position h + 1 and moving towards smaller indices, increase the corresponding values v_i by $1$.

for (i = h + 1; i > max(h - l + 1, 0); i--)
  v[i]++;

Sort the array in descending order and compute its new $h$-index.

sort(v.begin() + 1, v.end(), greater<int>());
h = hIndex(v);

Print the answer.

printf("%d\n", h);