MRS - Editorial

general
, , , , ,
1

PROBLEM LINK

Contest

Practice

Author :- Ranjan Kumar

Editorialist:–Ranjan Kumar

Difficulty :

Easy

Pre-Requisites:

Game Theory, Greedy, Implementation.

Problem:–

Given a n*m matrix we have to find the optimal solution for two players where one is allowed to choose a row and he is interested in maximizing the result whereas other is allowed to choose a value from the selected row and she is interested in minimizing the value.

Quick Solution:–

As the question is about a game where each player has to make an optimal move, we will use greedy approach. In the quick solution I would like to say that for solving the problem we need to find minimum value in each row and select maximum of them.

Detailed Approach:–

Now we come to the detailed approach where I will explain the technique to solve the problem.
As we are provided with a matrix n*m in which first player has to select a row and second has choice to select any value from that row.

Also first player is aware of the fact that second player to minimize the value so he has to select as large value as possible.

So we come to situation when the first player will select a row having the minimum value which is higher than the minimum value of all the rows.

So for a matrix Mat of n*m:

Let us take an array of size n.

Now a[0]=min(Mat[0][0],…………,Mat[0][m-1]);

    a[1]=min(Mat[1][0],………..,Mat[1][m-1]);
   .
   .
   .
   a[n-1]=min(Mat[n-1][0],………..,Mat[n-1][m-1]);

Now let the answer be ans.

So ans=max(a[0],……….,a[n-1]);

Hence ans will be the final answer.

Time Complexity:—

O(nm)

Solution :–

Setter’s Solution can be found here .

Feel free to post comments if anything is not clear to you.

1 Like
2

Very well explained :slight_smile:

3

how is its time complexity is o(nm) Ranjan .
can you elaborate?

4

Its very simple;
we are looking at each column for each row.

So for n rows we loop n times and for each row i, we loop for all the elements of the column of that row i.e. m
Hence nm … i.e. O(nm)