You are not logged in. Please login at www.codechef.com to post your questions!

×

ICL1801 - Editorial

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

asked 03 Mar '18, 19:05

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 03 Mar '18, 22:09

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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