Problem Link
Author: Bhuvnesh Jain
Testers: Ankit, Divesh, Priyank and Vibhav
Editorialist: Bhuvnesh Jain
Difficulty
CAKEWALK
Prerequisites
Sorting, Looping Techniques
Problem
Find the winner of the game when each player in his turn can select any number from the matrix which is not selected yet.
Explanation
The first thing to notice in this problem is that matrix has no role and the game is played on the array has the same result.
Next thing to notice is that the optimal strategy of each player would be a greedy selection of the largest number not selected yet. This is because if the person selects any other number than the largest number then in the next turn his opponent will select this largest number, hence have an advantage over him to win the game.
So, we can simply find the sum both the players will attain, when playing optimally. Based on this sum we can decide the winner of the game. To find the sum, sort all the numbers in the matrix in descending order and then assign every alternate number to player 1(Cyborg) and remaining numbers to player 2(Geno).
For details, refer to the setter’s solution below.
Time Complexity
O(N * M * \log{(N * M)}), per test case.
Space Complexity
O(N * M) per test case.