×

# ICL1801 - Editorial

Practice

Contest

Author: Bhuvnesh Jain

Testers: Ankit, Divesh, Priyank and Vibhav

Editorialist: Bhuvnesh Jain

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.

Setter's solution

6★likecs
3.7k2380
accept rate: 9%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,652
×1,647
×1,000
×593
×29
×3

question asked: 03 Mar '18, 19:05

question was seen: 300 times

last updated: 03 Mar '18, 22:09