Stuck with Matrix Problem (Gift Rift | CodeChef)

help
, ,
1

Please help me with question I’m not getting the point if i’ll find minimum
2 3 - (no. of rows and colums)
9 8 8
2 6 11- i’ll get min of row as 2, and max of columns as 11 if i’ll traverse, so how will I solve the problem???
we’ve to find the smallest in its row, but largest in its column, eg in above case its 8.

2

What you should do is, for every row find the smallest element(s)(if smallest is multiple times) and for each of these smallest element check if it is the largest element in that column.

e.g.
9 8 8
2 6 11
In first row 8 and 8 are smallest, so I check in second column if it is the largest or not. Turns out it is the largest, so I have an answer.
Do this for all the rows.
P.S : I am answering “find the smallest in its row, but largest in its column.”
Reply if something is wrong.

1 Like
3

thankyou for your reply, but if I apply a loop to find smallest in row then
for(int i = 0; i < r; ++i){
int minm=a[i][0];
for(int j = 1; j < c; ++j)
if(a[i][j]<minm)
minm=a[i][j];
}
it will traverse through all elements and give 2 as minimum,
and so how do I find out 8 as smallest in row??

4

Check this code and let me know if you get it or not :slight_smile:

bool thereIsGreater = 0;
	for (int i = 0; i < r; ++i) {
		int minm = a[i][0];
		for (int j = 1; j < c; ++j)
			if (a[i][j] < minm)
				minm = a[i][j];
		for(int j = 0; j < c; ++j){
			if(a[i][j] == minm){
				for (int k = 0; k < r; ++k) {
					if(a[k][j] > minm){
						thereIsGreater = 1;
						break;
					}
				}
				if(!thereIsGreater){
					cout << minm << endl;
					break;
				}
			}
		}
		if(!thereIsGreater)
			break;
	}
	if(thereIsGreater)
		cout << "None Found!\n";

`

1 Like
6

Create 2 arrays, one which stores the smallest element of each rows and other is a 2D array which stores the column of the smallest value.
Now, as there can be more than 1 column which has the smallest value in a row, we need to store multiple indexes for the same row. Thus, we will use a data structure called VECTOR.
Vector is nothing but a resizable array. You can google its various functions.

e.g.
9 8 8
2 6 11

int row[r];
vector<vector<int>> index(r); // 2D vector
//calculate min value in all rows and store it in row array;
//now again search through all rows. If you find an element which is the smallest in that row,
//store it in the vector.
index[r].push_back(c);

Now run a loop from 0 to r and another from 0 to index[r].size() and calculate the highest value
in column j. check if the highest value is equal to smallest value in row i, then that element can be considered. store element row[i] in min if value of min is greater that row[i]. The final value of min
will be the answer.

Here, row[0] = 8, and row[1] = 2;
and index[0] = {1,2} and index [1] = {0};

for(int i=0;i<r;i++)
{
     for(int j=0;j<index[i].size();j++)
     {
     //code to check for largest value in column j
     }
}
2 Likes
7

Thakyou brother for your detailed explanation I was out for few days, so now I’ll try it!!

1 Like
8

bro its giving right in 2 of the test cases but wrong in:
2 3
9 8 8
2 6 11

#include <iostream>
using namespace std;


int main() {

long r,c;
cin>>r>>c;
long a[r][r];
for(int i = 0; i < r; ++i){
    for (int j = 0; j< c; ++j)
    cin>>a[i][j];
}

bool thereIsGreater = 0;
for (int i = 0; i < r; ++i) {
	int minm = a[i][0];
	for (int j = 1; j < c; ++j)
		if (a[i][j] < minm)
			minm = a[i][j];
	for(int j = 0; j < c; ++j){
		if(a[i][j] == minm){
			for (int k = 0; k < r; ++k) {
				if(a[k][j] > minm){
					thereIsGreater = 1;
					break;
				}
			}
			if(!thereIsGreater){
				cout << minm << endl;
				break;
			}
		}
	}
	if(!thereIsGreater)
		break;
}
if(thereIsGreater)
	cout << "GUESS\n";
  
return 0;
}
9

Are you sure the output is not correct? I ran it on my system and it gives output as 8.

10

Er …

2 Likes