Ranker

SRM 112 · 2002-09-06 · by dgoodman

Class Name: Ranker

Return Type: int

Method Name: rankSum

Arg Types: (int, int, int)

Problem Statement

In a national competition, members submit entries which are automatically scored. The ranking of the entry's score relative to the scores of all previously submitted entries is then returned to the member. A returned ranking of 17, for example, means that 16 previously submitted entries were scored higher than your entry. If your ranking is 1, it means that your score is at least as good as every previously submitted entry.

We need software to store the scores and return the rankings. We will demonstrate it on a sequence of scores generated by a pseudorandom number generator. The scores will be: a mod p, a*a mod p, a*a*a mod p, ... Create a class Ranker that contains a method rankSum that is given a and p and also n, the number of scores to generate, as inputs and returns the sum of the n rankings. If the sum is greater than 1,000,000,000 return -1.

The sequence of scores can be generated by

    int score = 1;
    for(int i=0; i<n; i++){
        score = (score*a)%p;
        //...process this score
    }

Notes

the sequence may cycle, resulting in many repeated scores
duplicate scores do affect the reported ranking (see Example 1)

Constraints

a is between 1 and 2,000,000,000 inclusive
p is between 1 and 2,000,000,000 inclusive
a*p is less than or equal to 2,000,000,000
n is between 1 and 100,000 inclusive

Examples

3
10
7
Returns: 15

This a and p generate the sequence 3, 9, 7(27%10), 1(21%10), 3, 9, 7, ... Their ranks, relative to all the preceding values are 3 has a rank of 1 (there are no other values) 9 has a rank of 1 (it is better than the 3) 7 has a rank of 2 (it was beaten by the 9) 1 has a rank of 4 (it is lower than all preceding values) 3 has a rank of 3 (it was beaten by 9 and 7) 9 has a rank of 1 (it is at least as big as all its predecessors) 7 has a rank of 3 (it was beaten by both of the 9's) The sum of the ranks is 1+1+2+4+3+1+3 = 15.

3
2
4
Returns: 4

This a and p generate the sequence 1, 1, 1, 1, 1, ... The 4 ranks are 1,1,1,1 which sums to 4.

3
4
100000
Returns: -1

The sequence is 3, 1, 3, 1, ... The 100,000 ranks are 1,2,1,3,1,4,... which sums to more than 1,000,000,000.

1
1
1
Returns: 1

2
3
1000
Returns: 126250

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

Coding Area

Language: C++17 · define a public class Ranker with a public method int rankSum(int a, int p, int n) · 14 test cases · 2 s / 256 MB per case