Connection Status:
Competition Arena > OnLineRank

OnLineRank

SRM 179 · 2004-01-17 · by dgoodman

SRM 179 · 2004-01-17 · by dgoodman · Simulation
Class Name: OnLineRank
Return Type: int
Method Name: calcRanks
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

Proposals arrive at our office in a sequence. We give each one a score. We then calculate its "rank" based on comparison with the scores of the most recent submissions. Its rank is 1 + the number of recent scores that are greater than it. So a rank of 1 is the best possible rank and indicates that no recent score was greater. A rank of 2 would mean that exactly one recent score was greater. We need software that can calculate the rank of each score.

Create a class OnLineRank that contains a method calcRanks that is given k, the number of recent scores to use in each rank calculation, and int[] scores, the sequence of scores of the arriving proposals. The method should calculate the rank for each score and return the sum of all the ranks.

Each rank should be calculated based on the preceding k scores. If fewer than k scores have preceded this score, base the calculation on all the preceding scores. (The first proposal is thus guaranteed a rank of 1.)

Constraints

  • k will be between 1 and 100 inclusive.
  • scores will contain between 1 and 50 elements inclusive.
  • Each element of scores will be between 0 and 1000 inclusive.
Examples
0)
3
{6,9,8,15,7,12}
Returns: 11

The 6 is the first score and earns a rank of 1. The 9 is compared with the 6, which does not exceed it, so it earns a rank of 1. The 8 is compared with the 6 and 9, and is beaten by the 9, so it earns a rank of 2. The 15 is compared with 6, 9, and 8, and earns a rank of 1. The 7 is compared with 9, 8, and 15, but not with 6, which is not recent. Its rank is 4. The 12 is beaten by the 15, earning a rank of 2. 1+1+2+1+4+2 = 11

1)
80
{3,3,3,3,3,3,3}
Returns: 7

No score is exceeded by even one of its predecessors, so each of the seven scores earns a rank of 1.

2)
1
{9,8,7,6,5,4,3,2,1}
Returns: 17
3)
5
{9,8,7,6,5,4,3,2,1}
Returns: 39
4)
9
{1,5,100,92,5,17,45,92,30,30,1,5,100,92,5,17,45,92,30,30,1,5,100,92,5,17,45,92,30,30,1,5,100,92,5,17,45,92,30,30,1,5,100,92,5,17,45,92,30,30}
Returns: 234

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

Coding Area

Language: C++17 · define a public class OnLineRank with a public method int calcRanks(int k, vector<int> scores) · 28 test cases · 2 s / 256 MB per case

Submitting as anonymous