HIndexCounting
TCO21 Algo Semi 1 · 2021-11-12 · by misof
Problem Statement
If you spent some time in academia (or solved TCO21 round 1B), you should be familiar with the h-index.
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.
Professor Doofus has told you that he has published P papers, that his papers have a total of C citations, and that his h-index is exactly H.
You would like to determine which of his papers has how many citations. Count all valid options, and return that count modulo 1,000,000,007.
Two options are considered the same if one can be obtained from the other by changing the names of the papers. For example, one option might be the scenario in which the professor has one paper with 2 citations, two papers with 7 citations each, and one paper with 0 citations.
Constraints
- P will be between 1 and 50, inclusive.
- C will be between 0 and 3000, inclusive.
- H will be between 0 and P, inclusive.
7 0 1 Returns: 0
Seven papers, no citations. It is impossible to have a positive h-index.
6 10 3 Returns: 2
In order to have h-index 3, the professor must have: either papers with 0, 0, 0, 3, 3, and 4 citations or papers with 0, 0, 1, 3, 3, 3 citations
5 13 1 Returns: 5
6 18 3 Returns: 101
5 1500 5 Returns: 677184648
The exact answer is 1,677,184,655. The returned number is this answer modulo 10^9 + 7.
Submissions are judged against all 104 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HIndexCounting with a public method int count(int P, int C, int H) · 104 test cases · 2 s / 256 MB per case