CircularShifts | Topcoder Archive

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

```
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.
```
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.
```
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).

111111111

Returns: 2585408

```
141
```
```
96478
```
```
24834
```
```
74860
```
```
92112
```
```
Returns: 419992
```

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)2024, Topcoder, Inc. All rights reserved.