Last Updated: 16 Oct, 2021

Minimise Sum

Hard

Asked in company

Solve now

Problem statement

You are given a matrix of ‘N’ rows and ‘M’ columns and a non-negative integer ‘K’. You have to find the minimum possible sum of all elements in each submatrix after performing most ‘K’ decrements.

Note:

You can’t decrease a number below 0.

For example:

You are given ‘K’ = 5, and matrix 
‘mat’ = [[1, 2, 3],
         [4, 0, 5],
         [2 , 7, 4]]
You can do 3 operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.

Input Format:

The first line of input contains a single integer ‘T’, denoting the number of test cases.

The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’, representing the rows, columns of the matrix, and the given integer.

The following ‘N’ lines of input contain ‘M’ space-separated integers representing the matrix elements.

Output Format:

For each test case, print a single integer representing the minimum possible sum of all elements in each submatrix. Print the answer in the modulo 10^9 + 7.

Print a single line for each test case.

Constraints:

1 <= T <= 10
1 <= N, M <= 500
0 <= K <= 10^12
1<= mat[i][j] <= 10^6

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will count the number of times a given element will count towards the cumulative submatrix sum for each element in the matrix. We will maintain the variables to count from top-left, top-right, bottom-left, bottom-right.

Then we sort the array in reverse order according to the count, and for each, we will subtract K and add it to the answer.

Algorithm:

Set N as size of mat, and M as the size of mat[0]
Initialise and empty array ways
Iterate i and j from all the elements of mat
- Set row as (j + 1)*(m - j) and col as (i + 1)*(n - i) -1
- Set topLeft as i*j, and topRight as (m - j - 1) * (n - i) - 1
- Set bottomLeft as j*(n - i - 1) and bottomRight as (n - i - 1)*(m - j - 1)
- Set left as j*i*(n - 1 - 1) and right as (m - n - 1)*(n - i - 1)
- Set top as i*j (m - j - 1) and bottom as (n - i - 1)*j*(m - j - 1)
- Set d1 as topLeft * bottomRight and d2 as topRight*bottomLeft
- Set total as row + col + topLeft + topRight + bottomLeft + left + right + top + bottom + d1 + d2
- Insert the array [total * mat[i][j], mat[i][j]] in ways
Reverse sort the ways array
Set ans as 0
Iterate i from 0 to n*m
- Set element as ways[i][1]
- If k is greater than element
  - Set ways[i][1] as 0 and subtract element from k
- Otherwise if k is greater than 0
  - Subtract k from ways[i][1]
  - Set k as 0
- If element is not equal to 0
  - Add ways[i][0] / element * ways[i][1] to ans
Finally return ans

Solve now