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

×

SATA07 - Editorial

2
1

PROBLEM LINK:

Practice

Contest

Author: Akul Sareen

Tester: Tapan Sahni

Editorialist: Akul Sareen

DIFFICULTY:

MEDIUM

PREREQUISITES:

Binary search, Greedy

PROBLEM:

Given N items, each with an associated weight and value, choose exactly M items such that the ratio of sum of value to sum of weight of chosen items is maximum

QUICK EXPLANATION:

Binary search for the maximum ratio. While checking for a given ratio R greedily picking items with maximum value - R*weight is sufficient.

EXPLANATION:

The sample cases might lead you to believe that greedily picking items based on their value to weight ratio should get the right answer. However, that is not correct. Consider the case where there are 3 items with (value,weight) = (4,1),(4,3),(1,1) and you have to pick 2 items. Greedy will get you a value to weight ratio = 8/4 = 2, whereas the actual answer will get you 5/2 = 2.5.

As with many questions that ask you to maximize or minimize a value, you can try binary searching for the answer. To be able to do that we need to be able to answer the question, whether for some ratio R it is possible to achieve that ratio. Therefore, we want to find some set of M items such that:

$\displaystyle \frac{val_1 + val_2 + \dots + val_m}{wt_1 + wt2 + \dots + wt_m} \geq R $

then, we can rearrange the inequality to get:

$(val_1 - R \times wt_1) + (val_2 - R \times wt_2) + \dots + (val_m - R \times wt_m) \geq 0$

Let $x_i = val_i - R \times wt_i$, then for some given R we are simply trying to find a set of M items such that $x_1 + x_2 + \dots + x_m \geq 0$. We can do this step greedily by taking the M items with the largest values of x. If their sum is less than 0, then <b<r< b=""> cannot be achieved, else it can.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution will be uploaded later.

This question is marked "community wiki".

asked 02 Feb '16, 20:59

akulsareen's gravatar image

4★akulsareen
470410
accept rate: 44%

edited 23 Mar '16, 18:03

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,852
×2,657
×1,056
×1,024
×11
×4

question asked: 02 Feb '16, 20:59

question was seen: 743 times

last updated: 23 Mar '16, 18:03