StrawberryHard
SRM 762 · 2019-07-01 · by teja349
Problem Statement
This problem has an unusual time limit of 5 seconds.
Teja and Raja are experienced players in CSGo (Catch the Strawberry and go). CSGo is a two-player game consisting of n rounds. Teja and Raja play alternate rounds, Teja goes first. (Thus, Teja plays rounds 1, 3, 5, ..., while Raja plays rounds 2, 4, 6, ...)
At the beginning of the entire game Teja and Raja each have zero strawberries. In each round of CSGo, the active player can gain between 0 and 2*k strawberries. The actual number of strawberries gained is a random event (more details below) and all these random events are mutually independent.
You are given the values n, k, Arange, Brange, and seed. Use the following pseudocode to generate arrays A and B, each of length 2*k+1:
state = seed
for i = 0 .. 2*k:
state = (1103515245 * state + 12345)
state = state modulo 2^31
A[i] = state modulo Arange
state = (1103515245 * state + 12345)
state = state modulo 2^31
B[i] = state modulo Brange
For each valid index i, let pA(i) = A[i] / sum(A) and let pB(i) = B[i] / sum(B). The value pA(i) is the probability that Teja gains exactly i strawberries in any one round in which he is the active player. The value pB(i) is the same for Raja.
For spectators a game of CSGo is competitive if the absolute difference between the number of Teja's and the number of Raja's strawberries never exceeds k. (I.e., after each round the difference must be k or less.)
What is the probability with which the game between Teja and Raja will be competitive? It can be shown that the answer is always rational. Let X/Y be the answer in reduced form. Let Z = Y^(-1) be the inverse element to Y when computing modulo 10^9 + 7. Compute and return the value (X*Z) modulo 10^9 + 7.
Notes
- The inverse element to Y when computing modulo 10^9 + 7 is the only Z in the range [0, 10^9 + 6] such that Y*Z = 1 (modulo 10^9 + 7).
- The constraints ensure that the answer is always well-defined: the probability is always a fraction X/Y such that Y has a unique inverse element.
Constraints
- n will be between 1 and 17 inclusive.
- k will be between 1 and 7000 inclusive.
- Arange and Brange will be between 1 and 10^9+7 inclusive.
- seed will be between 0 and 10^9+6 inclusive.
- Sum of elements of A will not be a multiple of 10^9+7.
- Sum of elements of B will not be a multiple of 10^9+7.
15 1596 750210936 595502725 350348366 Returns: 282765234
1 1673 864461633 165070685 666663580 Returns: 561063812
15 1183 557777258 738042995 693722696 Returns: 764916223
15 1862 401673940 74036498 438933226 Returns: 905150019
16 1033 523882665 929880015 242088165 Returns: 777221174
1 3 2 7 0 Returns: 571428576
The pseudocode should give you the arrays A = {1,1,1,1,1,1,1} and B = {2,3,0,0,1,1,0}. This game consists of just one round in which Teja gains some strawberries. If Teja gains between 0 and 3 strawberries, the game will be competitive, if he gains more, it won't be. The probability that Teja gains between 0 and 3 strawberries is 4/7. Thus, we have X = 4 and Y = 7. We can compute that Z = 142,857,144 and therefore the answer you should return is (X*Z) modulo (10^9 + 7) = 571,428,576.
6 3 3 3 740562 Returns: 1
The arrays are A = {1, 2, 0, 0, 0, 0, 0} and B = {1, 1, 0, 0, 0, 0, 0}. This game has six rounds. In each round, the active player gains at most one strawberry. (Note that the probability of gaining more strawberries is zero.) Thus, the difference between the numbers of Teja's and Raja's strawberries never exceeds 3 and the game is guaranteed to be competitive.
7 3 3 3 740562 Returns: 753086426
If Teja always gains a strawberry and Raja never does, the game will not be competitive. Thus, the probability that this game won't be competitive is (2/3)^4 * (1/2)^3.
Submissions are judged against all 65 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StrawberryHard with a public method int competitive(int n, int k, int Arange, int Brange, int seed) · 65 test cases · 2 s / 256 MB per case