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

×

CROFT - Editorial

Practice
Contest

Difficulty:


Medium Prerequisites: =
Logic, ad-hoc game, greedy, sorting

Quick Explanation:

====================
Find optimal move for each player & arrange values in the form of array.

Detailed explanation:

=======================
First, we consider the constraints on making moves. Each Ai is paired with each Bi , and only one player can ever receive points for some index i. Once a player receives points for index i, the opposing player can never receive the points at index i of their own array.

Next, we must consider what would make an optimal move. It can be proven that the optimal move for the current player is to always choose the first unused element having the maximal value for AI + Bi , as the player will either add the largest number of points to their own score or block the opposing player from ever receiving a large amount of points.

So now that we've established we must both maintain paired values and choose the first available index having a maximal value for AI + Bi, we have to consider the most efficient way to find which index to choose. The best way to do this is to sort each pair of values in descending order of the maximum sum of Ai and Bi.

Next, we simply need to traverse the sorted array from 0 to n-1, adding the appropriate number of points at index i (i.e., the paired value at i associated with the current player) to the current player's score. This means that in the ith move, the current player will make an optimal move by choosing the ith element in the sorted array.

Once we've finished summing the scores, we simply compare them and print the appropriate result.

Complexity:


O(n.log(n))

This question is marked "community wiki".

asked 29 Oct '16, 23:42

prescient's gravatar image

0★prescient
41
accept rate: 0%

edited 07 Jun '17, 17:35

admin's gravatar image

0★admin ♦♦
19.0k348495533

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:

×14,441
×2,408
×876
×865
×681
×139
×1

question asked: 29 Oct '16, 23:42

question was seen: 754 times

last updated: 07 Jun '17, 17:35