Ranker | Topcoder Archive

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
    }

Definition

Class:: Ranker
Method:: rankSum
Parameters:: int, int, int
Returns:: int
Method signature:: int rankSum(int a, int p, int n)
(be sure your method is public)

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.
```
10002
```
```
10007
```
```
60000
```
```
Returns: 899220483
```

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.