TopCoder Statistics - Problem Statement

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

1

1

Returns: 1
2

3

1000

Returns: 126250
5000

100003

99999

Returns: -1
10002

10007

60000

Returns: 899220483
5

5

100000

Returns: 100000
10

1000777

63265

Returns: 999977075
2

4096

100000

Returns: 1199879
2

5

2

Returns: 2
10002

10007

90000

Returns: -1
12003

13000

99999

Returns: -1
10002

10007

60000

Returns: 899220483

Statistics

Problem Statement for "Ranker"

Problem Statement

Definition

Notes

Constraints

Examples