Author :- Ranjan Kumar
Game Theory, Greedy, Implementation.
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.
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.
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.
a=min(Mat,………..,Mat[m-1]); . . . a[n-1]=min(Mat[n-1],………..,Mat[n-1][m-1]);
Now let the answer be ans.
Hence ans will be the final answer.
Setter’s Solution can be found here .
Feel free to post comments if anything is not clear to you.