MaxSquare | Topcoder Archive

Problem Statement

You are given a large square matrix A. The matrix has dimensions n times n and it has a very special form derived from a sequence of integers. The exact procedure used to generate A is given below.

A square submatrix S is a square subarray of A that is contiguous in both dimensions. More formally, a square matrix S of size m*m (for some m between 1 and n, inclusive) is a square submatrix of A if we can find offsets x and y for which S[i][j] = A[x+i][y+j] for all i, j between 0 and m-1, inclusive. Note that a square submatrix cannot be empty.

Your task is to find a square submatrix of A with the largest sum of all its elements, and to return that sum.

The matrix A will be constructed in three steps:

We'll use a pseudorandom generator to generate B: a sequence of n integers.
We will apply some edits to the sequence B.
We will use the edited sequence B to define the matrix A.

In order to generate B you are given the int n, a long s (the seed for the generator), an int q (a modulo used in the generator), and an int o (an offset used in the generator). The pseudocode that generates B looks as follows:

for i in 0..n-1:
    B[i] = (s div 2^20) modulo q + o

    s0 = (s * 621) modulo 2^51
    s1 = (s * 825) modulo 2^51
    s2 = (s * 494) modulo 2^51
    s3 = (s *  23) modulo 2^51

    s = s3
    s = (s * 2^10 + s2) modulo 2^51
    s = (s * 2^10 + s1) modulo 2^51
    s = (s * 2^10 + s0 + 11) modulo 2^51

In the pseudocode shown above, ^ denotes exponentiation and div denotes integer division (e.g., 49 div 10 is 4). The variables s0 through s3 are temporary variables. All calculations can be done in signed 64-bit integer variables without overflowing. Note that all elements of B will be between o and o+q-1, inclusive.

In the second step we'll apply several edits to the sequence B. You are given data about the edits in two equally long int[]s x and y. The pseudocode for this step:

for i in 0..|x|-1:
    B[ x[i] ] = y[i]

Finally, matrix A is constructed as follows: for all i and j between 0 and n-1, inclusive, A[i][j] = B[i]+B[j].

Definition

Class:: MaxSquare
Method:: getMaxSum
Parameters:: int, long, int, int, int[], int[]
Returns:: long
Method signature:: long getMaxSum(int n, long s, int q, int o, int[] x, int[] y)
(be sure your method is public)

Notes

From the constraints of the problem it follows that B will always contain between 1 and 105 integers, inclusive, and that their absolute values won't exceed 108.
The process used to produce the sequence B is only used to keep the input size small. The reference solution would work for any sequence B that matches the constraints mentioned in the previous Note.

Constraints

n will be between 1 and 105, inclusive.
s will be between 0 and 251-1, inclusive.
q will be between 1 and 108+1, inclusive.
o will be between -108 and 108-q+1, inclusive.
x and y will have the same length.
x will contain between 0 and 500 elements, inclusive.
x will be sorted in strictly increasing order.
Each element of x will be between 0 and n-1.
Each element of y will be between -108 and 108, inclusive.

Examples

```
6
```
```
10000000014
```
```
20
```
```
-12
```
```
{1}
```
```
{3}
```
```
Returns: 28
```
The initial array B generated by the PRNG is {4, -3, -9, -7, 5, 2}. Next, we set B[1] to 3. Then, we generate A that looks as follows: 8 7 -5 -3 9 6 7 6 -6 -4 8 5 -5 -6 -18 -16 -4 -7 -3 -4 -16 -14 -2 -5 9 8 -4 -2 10 7 6 5 -7 -5 7 4 The square submatrix with the largest possible sum has dimension 2x2 and is located in the top-right corner of A. The sum of its elements is 9 + 6 + 8 + 5 = 28. There is no square submatrix (of any dimensions) with a larger sum, so 28 is the correct return value.
```
7
```
```
10000000029
```
```
20
```
```
-12
```
```
{}
```
```
{}
```
```
Returns: 12
```
B = {4, -1, -7, -5, 3, -12, -4}
```
10
```
```
42
```
```
40
```
```
-5
```
```
{}
```
```
{}
```
```
Returns: 2660
```
B = {-5, 0, 25, 4, 11, 29, 18, 20, 23, 8}

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.