LAWN - Editorial

editorial
1

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < a_i and 0 <= y < b_i.

Count and return the number of maximum integers in the matrix after performing all the operations.

QUICK EXPLANATION:

Find the minimum of all a_i's and multiply it by the minimum of all the b_i's

EXPLANATION:

As per the given problem statement, all the operations are performed on a rectangular sub-matrix of the initial all 0's M matrix. The upper left corner of each such rectangle is given by the index (0,0) and the lower right corner for an operation [i, j] is given by the index (i,j).

The maximum element will be the one on which all the operations have been performed.

To find all the elements we don’t need to count them, we can simply find the smallest region which is common in all of them since all the operation rectangle have the same starting point.

COMPLEXITIES

Here K is the size of operations

TIme Complexity: O(K).
A single traversal of all operations is done.

Space Complexity: O(1).
No extra space is used.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

int maxCount(int m, int n, vector<vector<int>>& ops) {
    
int i,row=INT_MAX,col=INT_MAX;

if(ops.size()==0)
	return m*n;

for(i=0;i<ops.size();i++)
{
	row = min(row,ops[i][0]);
	col = min(col,ops[i][1]);
}

return row*col;
}

int main() {
ios_base::sync_with_stdio(false);
int t,m,n,k,i;

cin>>t;
while(t--)
{
	cin>>m>>n>>k;
	vector<vector<int>>v(k, vector<int>(2, 0));
	
	for(i=0;i<k;i++)
		cin>>v[i][0]>>v[i][1];
	
	cout<<maxCount(m,n,v)<<endl;
}

return 0;
}
1 Like