FrozenStandings
TCO 2014 Finals · 2014-03-26 · by rng_58
Problem Statement
There are N contestants in the final round. They are numbered 0 through N-1 according to the results of the previous round. According to the frozen standings, contestant i has already solved X[i] problems. After the standings have been frozen, each contestant was only allowed to solve one additional problem. Thus, for each i the actual number of problems solved by contestant i is either X[i] or X[i] + 1.
In the final standings the contestants will be ordered by the number of problems solved (more is better). In case of a tie the contestant with a smaller number will have the better place.
The array X is generated from given ints A and seed. Use the following pseudocode to generate X:
64bit_integer x = seed;
for (i = 0; i < N; i++) {
x = x * 20142014 % 1000000007;
X[i] = x % A;
}
How many different rankings are possible at the end of the contest? Return this value modulo 1,000,000,007.
Constraints
- N will be between 1 and 500,000, inclusive.
- A will be between 1 and 500,000, inclusive.
- seed will be between 1 and 1,000,000,006, inclusive.
Statement by TopCoder, Inc. — view the original on the archive.
3 3 2137378 Returns: 2
The array X will be {0, 2, 2}. If contestant 2 solved one more problem during the last hour but contestant 1 did not, the final ranking will be (2,1,0). Otherwise the final ranking will be (1,2,0).
1 1 565225711 Returns: 1
The array X will be {0}.
5 1 765276374 Returns: 27
The array X will be {0, 0, 0, 0, 0}.
8 2 667363653 Returns: 226
The array X will be {1, 0, 1, 1, 1, 0, 1, 1}.
20 4 765276374 Returns: 933806
The array X will be {3, 3, 2, 3, 1, 0, 3, 1, 3, 0, 1, 3, 2, 1, 0, 1, 0, 3, 2, 1}.
Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FrozenStandings with a public method int countStandings(int N, int A, int seed) · 90 test cases · 2 s / 256 MB per case