MaxSquare
SRM 735 · 2018-06-25 · by majk
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
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
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].
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.
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}
100
207650457737033
20
-10
{14, 21, 22, 26, 45, 64, 67, 70, 73}
{5, -4, 6, 4, -4, 4, 2, -10, -4}
Returns: 3384
100
227292310727029
20
-10
{27, 48, 68, 78}
{-2, -1, 2, 8}
Returns: 22352
Submissions are judged against all 42 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaxSquare with a public method long long getMaxSum(int n, long long s, int q, int o, vector<int> x, vector<int> y) · 42 test cases · 2 s / 256 MB per case