Worthy Matrix - CodeChef Solution in C++ and Java | AskTheCode

CodeChef April Long Challenge Solution| Worthy Matrix solution in Java | AskTheCode

---

Problem: 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.

---

Input:

• 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 i, the i-th of these lines contains M space-separated integers Ai,1,Ai,2,Ai,3,…,Ai,M.

---

Output: For each test case, print a single line containing one integer ― the number of K-worthy submatrices of A.

---

Example Input: 1 3 3 4 2 2 3 3 4 5 4 5 5

---

Example Output: 7

---

Code:

In C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll min(ll x,ll y){
    if(x<y){
        return x;
    }
    return y;
}
int main() {
    ll testCase;
    cin>>testCase;
    while(testCase-- !=0){
        ll n,m,kVal;
        cin>>n>>m>>kVal;
        double matrix[n+1][m+1];
        for(ll i=0;i<=n;i++){
            for(ll j=0;j<=m;j++){
                if(i==0 || j==0){
                    matrix[i][j]=0;
                }
                else{
                    cin>>matrix[i][j];
                }
            }
        }
        for(ll i=0;i<=n;i++){
            double prev=0;
            for(ll j=0;j<=m;j++){
                matrix[i][j]+=prev;
                prev=matrix[i][j];
            }
        }
        for(ll j=0;j<=m;j++){
            double prev=0;
            for(ll i=0;i<=n;i++){
                matrix[i][j]+=prev;
                prev=matrix[i][j];
            }
        }
        ll alpha=min(n,m);
        ll totalPossibleSubMatrix=0;
        for(ll len=1;len<=alpha;len++){
            for(ll i=len;i<=n;i++){
                for(ll j=len;j<=m;j++){
                    if((matrix[i][j]+matrix[i-len][j-len]-matrix[i][j-len]-matrix[i-len][j])/(len*len)>=kVal){
                        totalPossibleSubMatrix++;
                    }
                }
            }
            
        }
        cout<<totalPossibleSubMatrix<<endl;
    }
}

---

In Java

import java.util.*;
import java.io.*;

class KAVGMAT {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int t = sc.nextInt();
        while (t-- != 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++)
                arr[i] = sc.readArray(m);

            out.println(solve(arr, n, m, k));
        }
        out.close();
    }

    static long solve(int[][] arr, int n, int m, int k) {
        long[][] prefixSum = new long[n + 1][m + 1];
        long cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                prefixSum[i][j] = arr[i - 1][j - 1] + prefixSum[i][j - 1];
            }
        }

        for (int j = 1; j <= m; j++) {
            for (int i = 1; i <= n; i++) {
                prefixSum[i][j] += prefixSum[i - 1][j];
            }
        }

        for (int sz = 1; sz <= n; sz++) {
            for (int i = 1; i <= n - sz + 1; i++) {
                int l = 1;
                int r = m - sz + 1;
                int pos = -1;
                while(l<=r) {
                    int mid = (l+r)/2;
                    long avg = (prefixSum[i+sz-1][mid+sz-1] - prefixSum[i+sz-1][mid-1] - prefixSum[i-1][mid+sz-1] + prefixSum[i-1][mid-1]) / ((long)sz*sz);
                    
                    if(avg >= k) {
                        r = mid - 1;
                        pos = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                if(pos != -1)   
                    cnt += (m - sz + 1 - pos + 1);
            }
        }
        return cnt;
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        public String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return null;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}