TopCoder problem "CircularShifts" used in SRM 436 (Division I Level Three)



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 given ints 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.
 

Definition

    
Class:CircularShifts
Method:maxScore
Parameters:int, int, int, int, int
Returns:int
Method signature:int maxScore(int N, int Z0, int A, int B, int M)
(be sure your method is public)
    
 

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)
    
141
96478
24834
74860
92112
Returns: 419992

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10336

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13698&pm=10336

Writer:

Gluk

Testers:

PabloGilberto , ivan_metelsky , ged , zhuzeyuan

Problem categories:

Math