SATA07 - Editorial

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 imes wt_1) + (val_2 - R imes wt_2) + \dots + (val_m - R imes wt_m) \geq 0$

Let x_i = val_i - R imes 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 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.

2 Likes