FrozenStandings
TCO 2014 Finals · 2014-03-26 · by rng_58
TCO 2014 Finals · 2014-03-26 · by rng_58 · Dynamic Programming
Problem Statement
Problem Statement
The final round of Top Cat Open 2014 is over!
However, we do not know the final standings yet because the scoreboard has been frozen for the last hour.
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:
How many different rankings are possible at the end of the contest? Return this value modulo 1,000,000,007.
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.
Examples
0)
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 1 565225711 Returns: 1
The array X will be {0}.
2)
5 1 765276374 Returns: 27
The array X will be {0, 0, 0, 0, 0}.
3)
8 2 667363653 Returns: 226
The array X will be {1, 0, 1, 1, 1, 0, 1, 1}.
4)
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.
Coding Area
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