Minimise Sum

Hard
0/120
Average time to solve is 45m
profile
Contributed by
5 upvotes
Asked in company
Intuit

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 3 5
1 2 3
4 0 5
2 7 4
1 2 1
3 4
Sample Output 1:
246
12
Explanation:
For the first test case, given K = 5, and matrix 
‘mat’ = [[1, 2, 3],
         [4, 0, 5],
         [2 , 7, 4]]
 You can do three operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.

For the second test case, given K = 1 and the matrix
mat = [[3, 4]]
You can do one operation on element 4. Then the sum of all submatrices will be 12.
Sample Input 2:
2
2 2 4
1 2
3 4
3 3 3
1 2 3
3 4 5
5 6 7
Sample Output 2:
24
368
Hint

Count the contribution of each element in the minimum sum.

Approaches (1)
Iterative 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
Time Complexity

O(N*M*log(N*M)), Where N and M are the number rows and columns in the matrix.

 

We are iterating through every matrix element, which will cost O(N*M) time. We also sort all the elements in the array that takes O(N*M*log(N*M)) time. Hence the final time complexity is O(N*M*log(N*M)).

Space Complexity

O(N*M), Where N and M are the number rows and columns in the matrix.

 

We are maintaining the array, which will have N*M elements. Hence the overall space complexity is O(N*M).

Code Solution
(100% EXP penalty)
Minimise Sum
Full screen
Console