Worthy Matrix CodeChef Solution | Easy Approach | C++, Java, Python

Share:

Worthy Matrix CodeChef Solution View on Codechef

Worthy Matrix CodeChef Solution

Chef found a matrix AA with NN rows (numbered 11 through NN) and MM columns (numbered 11 through MM), where for each row rr and column cc, the cell in row rr and column cc (denoted by (r,c)(r,c)) contains an integer Ar,cAr,c.

This matrix has two interesting properties:

  • The integers in each row form a non-decreasing sequence, i.e. for each valid ii, Ai,1≤Ai,2≤…≤Ai,MAi,1≤Ai,2≤…≤Ai,M.
  • The integers in each column also form a non-decreasing sequence, i.e. for each valid jj, A1,j≤A2,j≤…≤AN,jA1,j≤A2,j≤…≤AN,j.

A KK-worthy submatrix is a square submatrix of AA, i.e. a submatrix with ll rows and ll columns, for any integer ll, such that the average of all the integers in this submatrix is ≥K≥K.

Chef wants you to find the number of KK-worthy submatrices of AA.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains three space-separated integers NN, MM and KK.
  • NN lines follow. For each valid ii, the ii-th of these lines contains MM space-separated integers Ai,1,Ai,2,Ai,3,…,Ai,MAi,1,Ai,2,Ai,3,…,Ai,M.

Output

For each test case, print a single line containing one integer ― the number of KK-worthy submatrices of AA.

Constraints

  • 1≤T≤101≤T≤10
  • 1≤N⋅M≤1061≤N⋅M≤106
  • N≤MN≤M
  • 0≤K≤1090≤K≤109
  • 0≤Ar,c≤1090≤Ar,c≤109 for each valid r,cr,c
  • the sum of N⋅MN⋅M over all test cases does not exceed 106106

Codechef Subtasks

#1 (15 points): the sum of N⋅MN⋅M over all test cases does not exceed 103103

#2 (25 points): the sum of N⋅MN⋅M over all test cases does not exceed 4⋅1054⋅105

#3 (60 points): original constraints

Example Input

1
3 3 4
2 2 3
3 4 5
4 5 5

Example Output

7

Explanation

Example case 1: The following are the seven 44-worthy submatrices:

  • [3445][3445] with average 44; this matrix occurs only once
  • [4555][4555] with average 4.754.75; this matrix also occurs only once
  • [4][4] with average 44; we find this matrix twice in AA
  • [5][5] with average 55; we find this matrix 33 times in A

Worthy Matrix CodeChef Solution

C++

#include<iostream>
using namespace std;

int main()
{
    long long int t;
    cin>>t;
    for(long long int test=0;test<t;test++)
    {
      long long int n,m;
      long long int count=0;
      long long int k;
      cin>>n>>m>>k;
      long long int dp[n+1][m+1];
      for(long long int i=0;i<n+1;i++)
      {
          for(long long int j=0;j<=m;j++)
          {
              if(i==0||j==0)
                dp[i][j]=0;
              else
              cin>>dp[i][j];



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

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


       for(long long int ll=1;ll<=n;ll++)
    {
        for(long long int i=ll;i<=n;i++)
        {
            long long int low=ll;
            long long int mid;
            long long int high=m;
            int flag=0;
            int mid2;
             while(low<=high)
             {
                 mid=(low+high)/2;
                if(((dp[i][mid]-dp[i-ll][mid]-dp[i][mid-ll]+dp[i-ll][mid-ll])/(ll*ll))<k)
                    low=mid+1;
                else{
                    high=mid-1;
                    flag++;
                    mid2=mid;

             }
             if(flag!=0 &&((dp[i][mid]-dp[i-ll][mid]-dp[i][mid-ll]+dp[i-ll][mid-ll])/(ll*ll))<k)
             mid=mid2;

             }
             if(flag!=0)
              count=count+m-(mid-1);


            }

        }




cout<<count<<endl;
}
return 0;
}

Java

/* package codechef; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main(String args[]) throws Exception {
		FastReader fr = new FastReader();
		int t = fr.nextInt();
		PrintWriter out = new PrintWriter(System.out);
//		String a[] = new String[]
		while (t-- > 0) {
			int n = fr.nextInt();
			int m = fr.nextInt();
//			int b = fr.nextInt();
			int k = fr.nextInt();
			int arr[][] = new int[n][m];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					arr[i][j] = fr.nextInt();
			String ans = solve(n, m, k, arr);
//			String ans = solve(n,a,b,k);
//			String ans = solve(n);
			out.println(ans);
		}
		out.close();
	}
	
	public static String solve(String s) throws Exception {
		StringBuilder ans = new StringBuilder("YES");
 		return ans.toString();
	} 
	
	public static String solve(int n, int m, int k, int arr[][]) throws Exception {
		StringBuilder ans = new StringBuilder();
		int sum[][] = new int[n][m];
		for(int i = 0; i < n; i++) {
			sum[i][0] = arr[i][0];
			for(int j = 1; j<m; j++)
				sum[i][j] = sum[i][j-1] + arr[i][j];
		}
		
		for(int i = 1; i < n; i++) {
			for(int j = 0; j<m; j++)
				sum[i][j] += sum[i-1][j];
		}
		
		
		int d[][] = new int[n][m];
		long count = 0;
		for(int i = n-1; i>-1; i--) {
			for(int j = m-1; j>-1; j--) {
				int s = 1;
				if(i < n-1 && j < m-1) {
					s = Math.max(d[i+1][j], d[i][j+1]);
				} else if(i < n-1) {
					s =  d[i+1][j];
				} else if(j < m-1) {
					s = d[i][j+1];
				}
				int maxSize = Math.min(n-i, m-j);
				if(s > maxSize) {
					d[i][j] = s;
					continue;
				}
				boolean flag = false;
				while(avg(sum, s, i, j) < k) {
					s++;
					if(maxSize < s) {
						flag = true;
						break;
					}
				}
				if(!flag) {
					count += (maxSize-s+1); 
				}
				d[i][j] = s;
			}
		}
		
 		return count + "";
	}
	
	public static double avg(int sum[][], int n, int x, int y) {
		double avg = 0;
		if(x==0 && y ==0) {
			avg = sum[x+n-1][y+n-1];
		} else if(x == 0) {
			avg = sum[x+n-1][y+n-1] - sum[x+n-1][y-1];
		} else if(y == 0) {
			avg = sum[x+n-1][y+n-1] - sum[x-1][y+n-1];
		} else {
			avg = sum[x+n-1][y+n-1] - sum[x-1][y+n-1]-sum[x+n-1][y-1] +sum[x-1][y-1];
		}
		avg /= (n*n);
		return avg;
	}
	 
	
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

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

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

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

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

}

Python

# cook your dish here
def worthy():


    testcases = int(input())
    while(testcases):
        (m,n,k) = map(int,input().strip().split(' '))
        matrix = [[0 for x in range(n)] for y in range(m)]
        
        matrix = []
        for i in range(m):
            r = list(map(int,input().strip().split(' ')))
            matrix.append(r)
            
        
                
        auxillary = [[0 for x in range(n+1)] for y in range(m+1)] 
        
        for i in range(m+1):
            auxillary[i][0] = 0
            
        for j in range(n+1):
            auxillary[0][j] = 0
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                auxillary[i][j] = matrix[i-1][j-1]
                
        
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                auxillary[i][j] += auxillary[i][j-1]
                
        for j in range(1,n+1):
            for i in range(1,m+1):
                auxillary[i][j] += auxillary[i-1][j]
                
        
        
                
        result = 0
        
        for p in range(1,m+1):
            for i in range(1,m-p+2):
                l = 1 
                h = n-p+1 
                mid = 0
                q = 0
                flag = 0
                while(l <= h):
                    mid = int((l+h)/2)
                    out = auxillary[i+p-1][mid+p-1]-auxillary[i+p-1][mid-1]-auxillary[i-1][mid+p-1]+auxillary[i-1][mid-1]
                    if (out >= k*p*p):
                        h = mid-1 
                        q = mid 
                        flag = 1 
                    else:
                        l = mid+1 
                        
                if flag == 1: 
                    result += (n-p-q+2)
                    
        
        print(result)
        testcases -= 1
                
        
   
        
    




if __name__ == '__main__':
    worthy()

Worthy Matrix CodeChef Solution Tutorial

See more posts here

x