CircularShifts
SRM 436 · 2009-03-11 · by Gluk
SRM 436 · 2009-03-11 · by Gluk · Math
Problem Statement
Problem Statement
You have two lists of numbers, X and Y, each containing exactly N elements. You can optionally apply any number of circular shifts to each list. A circular shift means removing the last element from a list and re-inserting it before the first element. For example, {1, 2, 3} would become {3, 1, 2}, and {3, 1, 2} would become {2, 3, 1}. After you apply any circular shifts, the final score is calculated as:
X[0]*Y[0] + X[1]*Y[1] + ... + X[N-1]*Y[N-1]
You are givenint s Z0, A, B and M. Generate a list Z of length 2*N, using the following recursive definition:
Z[0] = Z0 MOD M
Z[i] = (Z[i-1]*A+B) MOD M (note that Z[i-1]*A+B may overflow a 32-bit integer)
Then, generate lists X and Y, each of length N, using the following definitions:
X[i] = Z[i] MOD 100
Y[i] = Z[i+N] MOD 100
Return the maximal final score you can achieve.
X[0]*Y[0] + X[1]*Y[1] + ... + X[N-1]*Y[N-1]
You are given
Z[0] = Z0 MOD M
Z[i] = (Z[i-1]*A+B) MOD M (note that Z[i-1]*A+B may overflow a 32-bit integer)
Then, generate lists X and Y, each of length N, using the following definitions:
X[i] = Z[i] MOD 100
Y[i] = Z[i+N] MOD 100
Return the maximal final score you can achieve.
Notes
- In the statement, "A MOD B" represents the remainder of integer division of A by B. For example, 14 MOD 5 = 4 and 20 MOD 4 = 0.
- The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.
Constraints
- N will be between 1 and 60,000, inclusive.
- Z0, A and B will each be between 0 and 1,000,000,000, inclusive.
- M will be between 1 and 1,000,000,000, inclusive.
Examples
0)
5 1 1 0 13 Returns: 5
Both lists contain only ones, so no matter how many shifts you perform, the score will always be 5.
1)
4 1 1 1 20 Returns: 70
The lists are {1, 2, 3, 4} and {5, 6, 7, 8}. The maximal score is achieved by not making any shifts.
2)
10 23 11 51 4322 Returns: 28886
The lists are (23, 4, 95, 20, 17, 94, 63, 44, 13, 96) and (87, 54, 13, 18, 61, 24, 17, 94, 53, 2).
3)
1000 3252 3458736 233421 111111111 Returns: 2585408
4)
60000 123121 289347322 231211112 989333333 Returns: 149230883
Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CircularShifts with a public method int maxScore(int N, int Z0, int A, int B, int M) · 93 test cases · 2 s / 256 MB per case