Problem Statement |
| | In this problem your task is to break a pseudorandom number generator given its last K outputs. Each `random' number will be generated as a function of the previous M `random' numbers, for some M. After the function is evaluated, the result is taken modulo a prime P, and that is the output. For instance, a simple generator function would be Sn = Sn-1+Sn-2 (mod P). A more complicated one is Sn = Sn-11*Sn-2 + Sn-1 + 1 (mod P). In general we will consider polynomials functions of the last M numbers. Your task is to write a method crack that takes a int[] S, a int, M, an int P, and returns your best guess for the next M numbers output by the generator.
The prime, P will be between 101 and 40000, inclusive. M will be chosen as floor(rand()*rand()*996)+5, where rand() is a uniform random number in [0,1].
The polynomial will be generated by first picking D, the maximum degree as 1, 2, or 3. The number of terms will then be chosen in [2,min(200,1+M+(D>1?M(M+1)/2)+(D>2?M(M+1)(M+2)/6)], and each term will be generated with a degree in [0,D]. After the degree d is chosen, d (not necessarily distinct) previous random numbers (offsets) are selected as the components of the term. If this generates a term which has already been generated, the process is repeated (so, degree 0 will only occur once, for instance). After the variables are chosen, the coefficient is chosen in [0,P-1]. You will be given the K sequential random numbers for K in [M,min(1000000,3*MD)]. The random number generator will be initialized with M random values, and then run for K+100*M iterations, of which you will be given the final K.
All random choices are uniform and independent.
Your score will be the number of the M entries that are correct. Your overall score will simply be the sum of your individual scores.
You can download the source code and class files to generate a sequence of random numbers. To run, simply enter 'java LaggedGenerator <seed>'. The output will be the M initial values, followed by an asterisk, followed by 100M random values, followed by an asterisk, followed by K random values, followed by an asterisk, and finally the M values to predict. The seeds for the examples are 1-9 and 18, in order. |
| |
Definition |
| | | Class: | LaggedGenerator | | Method: | crack | | Parameters: | int[], int, int | | Returns: | int[] | | Method signature: | int[] crack(int[] S, int P, int M) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 30 seconds. |
| - | The memory limit is 1024M. |
| - | In the examples, N is the number of terms in the polynomial. |
| - | There are 100 non-example test cases. |
| |
Examples |
| 0) | |
| | | Returns: "" | P = 101
N = 4
D = 2
M = 5
K = 50
|
|
|
| 1) | |
| | | Returns: "" | P = 36299
N = 7
D = 1
M = 16
K = 44
|
|
|
| 2) | |
| | | Returns: "" | P = 23789
N = 177
D = 3
M = 102
K = 668069
|
|
|
| 3) | |
| | | Returns: "" | P = 13687
N = 62
D = 2
M = 155
K = 4147
|
|
|
| 4) | |
| | | Returns: "" | P = 28403
N = 26
D = 1
M = 25
K = 40
|
|
|
| 5) | |
| | | Returns: "" | P = 17257
N = 19
D = 3
M = 611
K = 682883
|
|
|
| 6) | |
| | | Returns: "" | P = 21481
N = 51
D = 1
M = 115
K = 193
|
|
|
| 7) | |
| | | Returns: "" | P = 24281
N = 180
D = 2
M = 211
K = 125395
|
|
|
| 8) | |
| | | Returns: "" | P = 27847
N = 127
D = 1
M = 565
K = 928
|
|
|
| 9) | |
| | | Returns: "" | P = 39317
N = 169
D = 2
M = 26
K = 1485
|
|
|
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)2020, TopCoder, Inc. All rights reserved.