ICL1801 - Editorial

cakewalk
editorial
greedy
icl1801
icl2018
likecs

#1

Problem Link

Practice

Contest

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.

Solution Links

Setter’s solution