3535. Vasya and matrix

 

Vasya received a rectangular matrix of size n × m as a gift from his mother. Each cell of the matrix contains an integer. At first, Vasya enthusiastically played various mathematical games with the matrix: sometimes he would swiftly compute its determinant, and sometimes he would easily raise it to different powers.

However, he eventually got bored of such games and came up with a new pastime: Vasya chooses an integer k and tries to find a submatrix of maximum area such that the sum of all its elements does not exceed k. A submatrix is defined as a rectangular fragment of the original matrix.

 

Input. The first line contains three integers: n, m and k (1 ≤ n, m ≤ 300, 1 ≤ k ≤ 109). The next n lines each contain m non-negative integers, each of which does not exceed 1000.

 

Output. Print a single integer – the area of the largest submatrix whose sum of elements does not exceed k.

 

Sample input 1

Sample output 1

1 3 4

8 6 4

1

 

 

Sample input 2

Sample output 2

3 3 12

7 5 7

8 4 8

4 3 2

3

 

 

SOLUTION

dynamic programming + binary seasrch

 

Algorithm analysis

Let a be the input rectangular matrix. Create a two-dimensional array dp of the same size, where dp[i][j] represents the sum of elements in the submatrix with opposite corners at points (1, 1) and (i, j). The values in this array can be computed using the following formula:

dp[i][j] = dp[i – 1][j] + dp[i][j – 1] – dp[i – 1][j – 1] + a[i][j]

 

Now consider a submatrix of array a of size w × h. Let its opposite corners be located at coordinates (i, j) and (i + w – 1, j + h – 1).

 

Then the sum of all elements in the submatrix is calculated using the formula:

dp[i + w – 1][j + h – 1] – dp[i + w – 1][j – 1] – dp[i – 1][j + h – 1] + dp[i – 1][j – 1]

 

Let’s solve the problem using brute-force search. Iterate over all possible submatrix sizes w × h, as well as all valid coordinates of the top-left corner (i, j) of the submatrix. Using the dp array, compute the sum of elements inside the current submatrix in constant time. If this sum does not exceed k, we keep track of the maximum area among all such submatrices.

However, this brute-force approach has a time complexity of O(n4), which is too slow. We can speed it up to O(n3logn) by applying binary search on the width h of the submatrix.

Fix the top-left corner (i, j). Let g(w, h) denote the sum of elements in the submatrix with corners at (i, j) and (i + w – 1, j + h – 1). If we fix the height w and treat the width h as a variable, then g(w, h) becomes a non-decreasing function with respect to h, since the original matrix a contains non-negative integers. This allows us to use binary search to find the maximum value of h for which g(w, h) ≤ k.

 

Example

For example, the sum of the numbers in the submatrix with corners at points (2, 2) and (3, 3) is

48 – 19 – 19 + 7 = 17

 

Algorithm implementation

The input matrix is stored in the array à.

 

#define MAX 210

int a[MAX][MAX], dp[MAX][MAX];

 

The function f(w, h) returns 1 if there exists a submatrix of size w × h such that the sum of its elements does not exceed k. To check this, all possible coordinates of the top-left corner (i, j) are iterated over, and the sum of elements in the rectangle with corners at (i, j) and (i + w – 1, j + h – 1) is computed in constant time using the dp array.

 

int f(int w, int h)

{

  for (int i = 1; i + w - 1 <= n; i ++)

  for (int j = 1; j + h - 1 <= m; j ++)

    if (dp[i + w - 1][j + h - 1] - dp[i + w - 1][j - 1] –

        dp[i - 1][j + h - 1] + dp[i - 1][j - 1] <= k) return 1;

  return 0;

};

 

The main part of the program. Read the input matrix.

 

scanf("%d %d %d",&n,&m,&k);

for (i = 1; i <= n; i++)

for (j = 1; j <= m; j++)

  scanf("%d",&a[i][j]);

 

Based on the input matrix a, compute the auxiliary matrix dp.

 

for (i = 1; i <= n; i++)

for (j = 1; j <= m; j++)

  dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];

 

Iterate over the possible values of the submatrix width w.

 

answer = 0;

for (w = 1; w <= n; w++)

{

 

The length of the submatrix is determined using binary search over the range [l; r].

 

  l = 1; r = m;

  while (l < r)

  {

    mid = (l + r) / 2;

 

For a submatrix of size w × mid, iterate over all possible positions of its top-left corner (i, j). If there exists at least one position where the sum of elements in the submatrix does not exceed k, update the value of the resulting area answer.

 

    if (f(w,mid))

    {

      answer = max(answer, w * mid);

      l = mid + 1;

    }

    else r = mid;

  }

 

  mid = (l + r) / 2;

  if (f(w,mid))

    answer = max(answer, w * mid);

};

 

Print the area of the largest submatrix found.

 

printf("%d\n",answer);