Connection Status:
Competition Arena > HIndex

HIndex

2021 TCO Parallel 1B · 2021-04-13 · by misof

2021 TCO Parallel 1B · 2021-04-13 · by misof · Brute Force, Simple Math, Simple Search, Iteration
Class Name: HIndex
Return Type: int
Method Name: cheat
Arg Types: (vector<int>, int, int)
Problem Statement

Problem Statement

The h-index is a fairly popular method of evaluating an author's scientific impact. The h-index of an author is defined as the maximum value h such that the given author has published at least h papers that have each been cited at least h times.

An unscrupulous scientist has decided to cheat and boost their h-index by paying for fake citations. You are given:

  • The int[] realCitations. Each element of realCitations is the number of citations for one of the author's papers.
  • The int budget: the maximum amount of money the scientist is willing to spend on the fake citations.
  • The int citationPrice: the cost of one fake citation (of one paper of the buyer's choice).

Calculate and return the maximum h-index the scientist can have after purchasing some fake citations.

Notes

  • The scientist has no time to make additional publications, he can only purchase citations to already existing papers.
  • Sadly, practices like the one described in the problem statement are quite common in modern academia. Awareness of these practices is the first step towards finding a way to get rid of them.

Constraints

  • realCitations will have between 1 and 300 elements, inclusive.
  • Each element of realCitations will be between 0 and 10^6, inclusive.
  • budget will be between 1 and 10^9, inclusive.
  • citationPrice will be between 1 and 10^9, inclusive.
Examples
0)
{25, 3, 5, 3, 8, 0}
447
1000
Returns: 3

A fake citation costs 1000 which is something this scientist cannot afford. The citations he already has give him an h-index of 3.

1)
{25, 3, 5, 3, 8, 0}
1447
1000
Returns: 4

A similar situation to Example 0 but now the scientist does have the budget to purchase one fake citation. One optimal choice is to buy a citation for the fourth paper (raising its total number of citations from 3 to 4), as this will make the scientist's new h-index be 4.

2)
{0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}
140000
10000
Returns: 4

This scientist writes extremely poor papers that get almost no real citations. His current h-index is only 1. However, he is quite rich and can afford to buy up to 14 fake citations. If he does so cleverly, he will be able to raise his h-index to 4 (and doesn't even have to spend all the money in his budget to do so).

3)
{0, 0, 0}
999999999
1000000000
Returns: 0
4)
{0, 0, 0}
1000000000
1
Returns: 3

Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HIndex with a public method int cheat(vector<int> realCitations, int budget, int citationPrice) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous