Statistics

Problem Statement for "Highscore"

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:
100
90
90
80
then the ranks would be
1
2
2
4
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

  1. {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.

  2. {}

    0

    50

    Returns: 1

    The high score list is still empty, so the new score gets the top position.

  3. {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.

  4. {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.

  5. {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}

    1337

    50

    Returns: 46

  6. {10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,9}

    10

    50

    Returns: 1

  7. {10,10,9,9,9,8,8,8,8,7,7,7,7,7,6,6,6,6,6,6,5,5,5,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,2,2,2,2,2}

    2

    50

    Returns: 45

  8. {2000000000,2000000000,2000000000,2000000000,2000000000,2000000000,2000000000,2000000000,2000000000,2000000000}

    2000000000

    10

    Returns: -1

  9. {0,0,0,0,0,0,0,0,0}

    0

    10

    Returns: 1

  10. {1994545937, 1938943236, 1902605580, 1707491184, 1377509761, 1347571835, 1217847778, 1140345403, 1103320943, 856465388}

    496673726

    42

    Returns: 11

  11. {1740665186, 1709527555, 1539354427, 1480770569, 1349214389, 1245184376, 814903705, 788125553, 721703778, 465503691, 423475004, 379610024, 239733076, 231195889, 109266651}

    213159886

    34

    Returns: 15

  12. {1924424854, 1869076508, 1812125141, 1696815179, 1662099718, 1527497209, 1472193624, 1391284950, 1373480982, 1270736526, 1211536634, 1106628158, 954534139, 893588844, 812415196, 633294201, 576948272, 528127546, 357541085, 2999473}

    69819329

    20

    Returns: 20

  13. {1939928133, 1875935049, 1874384766, 1832123006, 1809983561, 1625747860, 1588411305, 1361588761, 1320953759, 1136618504, 1133373165, 1106524752, 847491406, 733381297, 677242199, 584857676, 558993346, 510461239, 457677773, 242350491, 116483683, 101258178, 98100520, 93572540, 69360786}

    521656710

    38

    Returns: 18

  14. {1903735057, 1887825995, 1880825322, 1877831942, 1802388243, 1555852138, 1513446242, 1203724509, 1200731806, 1105750579, 863109059, 836341042, 745861977, 726734362, 706121526, 503119284, 437528121, 416091381, 336416999, 257840551, 242394994, 233495100, 211064438, 183815485, 141972426, 117998694, 97397548, 63965870, 48028723, 12674889}

    370202168

    33

    Returns: 19

  15. {1974014389, 1964036502, 1953683864, 1953248190, 1926289996, 1781913563, 1735290113, 1641543549, 1640198679, 1621452949, 1597571326, 1586267163, 1555302851, 1458106487, 1384793500, 1269037460, 1265178712, 1177524568, 1104177778, 1048331951, 981750648, 979385732, 812662202, 733383112, 427958704, 278890030, 242667017, 235032387, 216597435, 173344067, 166328677, 109524502, 103765484, 66807754, 13678613}

    1455897858

    35

    Returns: 15

  16. {1877393448, 1834989440, 1759499467, 1738609108, 1673995822, 1519198720, 1500826967, 1467241958, 1396862963, 1394688430, 1325309652, 1306535105, 1296477122, 1273712974, 1264561740, 1223164070, 1075918311, 1070687864, 1057166548, 974370191, 969826757, 961165694, 886803778, 743005399, 695169475, 649123734, 616740593, 613674568, 594450572, 510913920, 348167239, 326934943, 309789149, 261236661, 246618669, 244517132, 129006603, 118116160, 111063613, 89571464}

    268720403

    42

    Returns: 34

  17. {1911149990, 1902703485, 1888970559, 1883636820, 1880142125, 1753625007, 1732488637, 1689754533, 1569142580, 1563923162, 1497333876, 1480687681, 1390602329, 1300053421, 1272661111, 1227449115, 1191777786, 1186665734, 1092781939, 1025601386, 957029871, 834037365, 776513336, 748859997, 733100499, 722645215, 688375817, 625966032, 598088401, 583935317, 582066621, 382819993, 374271715, 316052593, 288279863, 193032316, 131639041, 105406189, 75050206, 71787501, 71564608, 51370353, 38768929, 8996184, 3514904}

    1878768466

    49

    Returns: 6

  18. {1978501717, 1879220794, 1814291060, 1812449837, 1792216779, 1789819517, 1668115199, 1613617070, 1577726434, 1575355039, 1554280006, 1485366242, 1451396991, 1442994192, 1403168401, 1374399628, 1348617509, 1248826990, 1153916906, 1146537624, 1088370258, 1070154972, 1053802901, 988916555, 952578434, 949250003, 844791307, 820134199, 815921820, 796086813, 750603113, 741656383, 685507230, 667331505, 637949195, 609344475, 607889868, 501643894, 466963173, 430207065, 351184889, 320597257, 205026957, 141444725, 128212188, 124119560, 101645255, 94839898, 65635978, 62828927}

    52707780

    50

    Returns: -1

  19. { 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 }

    1337

    50

    Returns: 46

  20. { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    10

    10

    Returns: -1

  21. { 10 }

    2

    10

    Returns: 2

  22. { 50 }

    5

    10

    Returns: 2

  23. { 10, 10, 9, 9, 9, 8, 8 }

    8

    10

    Returns: 6

  24. { 10 }

    5

    10

    Returns: 2

  25. { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

    1

    10

    Returns: -1

  26. { 10, 10, 10, 10 }

    5

    10

    Returns: 5

  27. { 500, 400, 400, 400, 400 }

    400

    10

    Returns: 2

  28. { 10 }

    20

    10

    Returns: 1

  29. { 100, 90, 90, 90, 10 }

    90

    10

    Returns: 2

  30. { 1, 1, 1 }

    1

    10

    Returns: 1

  31. { 100, 90, 80 }

    20

    10

    Returns: 4

  32. { 3, 2, 2, 1 }

    1

    10

    Returns: 4

  33. { 10, 9, 8 }

    5

    10

    Returns: 4

  34. { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    10

    13

    Returns: -1

  35. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    1

    10

    Returns: -1

  36. { 10 }

    7

    10

    Returns: 2

  37. { 2, 1 }

    0

    10

    Returns: 3

  38. { 10, 9, 9, 9, 9, 9, 9, 9, 9, 9 }

    9

    10

    Returns: -1

  39. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 }

    1

    15

    Returns: 1

  40. { }

    2

    10

    Returns: 1

  41. { 90, 90, 90, 90, 90, 90, 90, 90, 90, 90 }

    60

    30

    Returns: 11

  42. { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    5

    15

    Returns: -1

  43. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    1

    18

    Returns: -1

  44. { 50, 40, 30, 30, 30, 30, 30, 20, 10 }

    5

    10

    Returns: 10

  45. { 90, 80, 70, 60, 50, 40, 40, 30, 20, 10, 0 }

    35

    12

    Returns: 8

  46. { 5, 5, 5 }

    3

    10

    Returns: 4

  47. { 50 }

    50

    10

    Returns: 1

  48. { 10, 10, 10, 9, 9, 9, 9, 9, 9 }

    9

    10

    Returns: 4

  49. { 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

    9

    14

    Returns: 14

  50. { 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 1 }

    1

    11

    Returns: -1

  51. { 2 }

    1

    10

    Returns: 2

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.
This problem was used for: