TopCoder Statistics - 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.)

Definition

Class:: OnLineRank
Method:: calcRanks
Parameters:: int, int[]
Returns:: int
Method signature:: int calcRanks(int k, int[] scores)
(be sure your method is public)

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

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

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

Returns: 17
5

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

Returns: 39
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
10

{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Returns: 20
3

{100,100,99,99,98,98,97}

Returns: 19
2

{100,100,99,99,98,98,97}

Returns: 15
31

{100,100,99,99,98,98,97}

Returns: 25
21

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

Returns: 454
3

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

Returns: 19
8

{9,3,4,8,5,5,6,2,8,1}

Returns: 35
5

{9,3,4,8,5,5,6,2,8,1}

Returns: 28
1

{9,3,4,8,5,5,6,2,8,1}

Returns: 14
3

{9,3,4,8,5,5,523,6,2,8,1}

Returns: 24
1

{79}

Returns: 1
5

{ 87, 32, 4, 98, 56, 74, 32, 1, 95, 25 }

Returns: 30
5

{ 5, 5, 5, 5, 5, 3 }

Returns: 11
4

{ 1, 24, 62, 21, 23, 74, 22, 1, 2, 3, 4, 5, 6, 7, 89, 22, 35, 63, 11, 46, 78 }

Returns: 46
1

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

Returns: 19
3

{ 6, 9, 8, 15, 7, 12, 12, 110, 42, 89, 21 }

Returns: 22
3

{ 9, 8, 7, 6, 5, 4 }

Returns: 18
5

{ 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84 }

Returns: 87
1

{ 9, 6, 10, 11, 9, 8, 7, 10, 12 }

Returns: 13
1

{ 1, 2, 3, 4, 5, 4, 3, 2, 1 }

Returns: 13
6

{ 6, 9, 8, 19, 5, 13 }

Returns: 12
1

{ 5, 4, 3, 2, 1 }

Returns: 9
3

{ 9, 10, 8, 5 }

Returns: 9

Statistics

Problem Statement for "OnLineRank"

Problem Statement

Definition

Constraints

Examples