MostLikely

SRM 336 · 2007-01-25 · by dgoodman

SRM 336 · 2007-01-25 · by dgoodman · Simple Math, Simple Search, Iteration

Show categories

Class Name: MostLikely

Return Type: int

Method Name: likelyRank

Arg Types: (vector<int>, int, int)

Problem Statement

In a contest, we know the scores of all our competitors, and we estimate that our own score is equally likely to be any integer value between low and high, inclusive. We want to know what our rank will most likely be. We define our rank to be 1 + the number of competitors that beat us, so our rank will be number 1 if no one beats us (even if several tie us).

Given a int[] scores, the scores of our competitors, and ints low and high, return our most likely rank. If there is more than one most likely rank, return -1.

Constraints

scores will contain between 1 and 50 elements, inclusive.
Each element of scores will be between 0 and 1,000,000,000, inclusive.
low will be between 0 and 1,000,000,000, inclusive.
high will be between low and 1,000,000,000, inclusive.

Examples

{3,12,4}
8
8
Returns: 2

It is certain that only the 12 will beat us, giving us a rank of 2.

{3,4,5}
3
7
Returns: 1

Our score is equally likely to be 3 or 4 or 5 or 6 or 7. One of those scores (the 3) gives us a rank of 3. Similarly, one of those scores gives us a rank of 2. And the remaining 3 scores all give us a rank of 1 which is thus the most likely.

{3,4,5}
2
5
Returns: -1

Each of our possible scores gives us a different rank, so all those ranks are tied for most likely.

{121,120,119}
120
120
Returns: 2

{5}
1
1
Returns: 2

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

Coding Area

Language: C++17 · define a public class MostLikely with a public method int likelyRank(vector<int> sc, int low, int high) · 102 test cases · 2 s / 256 MB per case