Codechef | April 21 challenge | Worthy Matrix | solution |KAVGMAT
Chef found a matrix A with N rows (numbered 1 through N) and M columns (numbered 1 through M), where for each row r and column c, the cell in row r and column c (denoted by (r,c)) contains an integer Ar,c
This matrix has two interesting properties:
- The integers in each row form a non-decreasing sequence, i.e. for each valid i, Ai,1≤Ai,2≤…≤Ai,M.
- The integers in each column also form a non-decreasing sequence, i.e. for each valid j, A1,j≤A2,j≤…≤AN,j.
A K-worthy submatrix is a square submatrix of A, i.e. a submatrix with l rows and l columns, for any integer l, such that the average of all the integers in this submatrix is ≥K.
Chef wants you to find the number of K-worthy submatrices of A.
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains three space-separated integers N, M and K.
- N lines follow. For each valid ii, the ii-th of these lines contains M space-separated integers Ai,1,Ai,2,Ai,3,…,Ai,M
For each test case, print a single line containing one integer ― the number of K-worthy submatrices of A.
- 0≤Ar,c≤10^9 for each valid r,c
- the sum of N⋅M over all test cases does not exceed 10^6
Subtask #1 (15 points): the sum of N⋅M over all test cases does not exceed 10^3
Subtask #2 (25 points): the sum of N⋅M over all test cases does not exceed 4⋅10^5
Subtask #3 (60 points): original constraints
1 3 3 4 2 2 3 3 4 5 4 5 5
Example case 1: The following are the seven 4-worthy submatrices:
-  with average 4; this matrix occurs only once
-  with average 4.75; this matrix also occurs only once
-  with average 4; we find this matrix twice in A
-  with average 5; we find this matrix 3 times in A
Original question will be found at https://www.codechef.com/APRIL21A/problems/KAVGMAT
Solution will be published once the contest is over.