Highscore | Topcoder Archive

Problem Statement

Many computer games have high score lists, where the best achieved scores are stored in non-ascending order. The rank of a score in such a list is normally the position in the sorted list. But if several scores are equal, their rank is the smallest position of such a score in the sorted list. For example, if the high score list looks like:

then the ranks would be

Given the number of possible entries in the high score list (int places), a list of scores (int[] scores) and a new score (int newscore), write a method getRank which returns the rank of the new score within the high score list. If the score is too low to get a position on the high score list, your method should return -1. Note that in a case where all places on the high score list are already filled, an old score will only be replaced if the new score is better (see example 2).

Definition

Class:: Highscore
Method:: getRank
Parameters:: int[], int, int
Returns:: int
Method signature:: int getRank(int[] scores, int newscore, int places)
(be sure your method is public)

Constraints

places is between 10 and 50, inclusive.
The number of elements in scores is between 0 and places, inclusive.
Each element of scores is between 0 and 2000000000, inclusive.
scores is sorted in non-ascending order.
newscore is between 0 and 2000000000, inclusive.

Examples

```
{100,90,80}
```
```
90
```
```
10
```
```
Returns: 2
```
Inserting the score of 90 in the high score list gives {100, 90, 90, 80}. The ranks for this list are {1,2,2,4} (see example above). Therefore the return value is 2.
```
{}
```
```
0
```
```
50
```
```
Returns: 1
```
The high score list is still empty, so the new score gets the top position.
```
{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
```
```
1
```
```
10
```
```
Returns: -1
```
All 10 places on the high score list are already taken, and the new score is not better than any of them.
```
{10, 9, 8, 7, 6, 5, 4, 3, 3, 0}
```
```
1
```
```
10
```
```
Returns: 10
```
In this case, the score of 0 will be replaced by the new score of 1.

{2000000000, 19539, 19466, 19146, 17441, 17002, 16348, 16343,
15981, 15346, 14748, 14594, 13752, 13684, 13336, 13290, 12939,
12208, 12163, 12133, 11621, 11119, 10872, 10710, 10390, 9934,
9296, 8844, 8662, 8653, 8168, 7914, 7529, 7354, 6016, 5428,
5302, 5158, 4853, 4538, 4328, 3443, 3222, 2107, 2107, 1337,
951, 586, 424, 31}

Returns: 46

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.