3
$\begingroup$

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{denominator sum}}$ is maximized. As in this case, selecting $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$ will result in $\frac{4+2+1}{2+3+2}$ = 1 which is maximized.

How can I select $k$ fractions which will always result in the maximum $\frac{\text{numerator sum}}{\text{denominator sum}}$ value?

Edit:

  • Attempt 1: Sorting fractions in descending order. This passes a few test cases but that it's. This can also be proven by example that it is not the optimal solution. Let's say we have a list of 3 fractions sorted in descending order, $\frac{1}{2}$, $\frac{20}{59}$, $\frac{1}{3}$ and $k = 2$. The optimal solutions is $\frac{1+1}{2+3}$, not $\frac{1+20}{2+59}$.
$\endgroup$
  • 1
    $\begingroup$ What did you try? What progress have you made so far? Where did you get stuck? What programming paradigms have you tried? Have you tried dynamic programming? Greedy algorithms? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. May 10 at 15:58
  • $\begingroup$ I'm basically stuck at thinking of the idea, sorting the fractions in descending order does pass some tests but that's it. I'm also very week at dynamic programming. $\endgroup$ – Loc Truong May 10 at 16:18
  • $\begingroup$ Sounds like you have a candidate algorithm that passes all the test cases you've tried. If so, I suggest you next try to prove it correct (see cs.stackexchange.com/q/59964/755), then edit your question to show the algorithm and your attempts to prove it correct and your progress on that and where you got stuck. Folks here might not be interested in solving your exercise for you, but if you make an attempt and get stuck on some specific step, people might be more likely to help. $\endgroup$ – D.W. May 10 at 16:41
2
$\begingroup$

For a list of fractions, define the ratio as (sum of numerator) / (sum of denominator).

Question: Can we find a list of k fractions with the ratio ≥ r, for some given r?

Let the sum of numerators be X, and the sum of denominators be Y, then we require X / Y ≥ r or X - rY ≥ 0. For a single fraction x / y, we can calculate x - ry. We pick the k fractions where x - ry is largest. If the sum X - rY ≥ 0, then we have a list with ratio ≥ r, otherwise there is none.

We have obvious lower and upper bounds for r (the k-largest and the largest value of any fractions). With binary search we can easily find a list with maximum ratio.

Responding to some comments: What I presented is the basic idea. There is plenty of room for improvement.

For example "we pick the k fractions where x - ry is largest" - that can easily be done without sorting the array, much faster than n log n. Start like Quicksort, but only process subarrays that you need to determine the k largest values.

And it's not just binary search, because each time you actually find a list of fractions and can update the lower or upper bound for r or both. (For example if the lower and upper bound were 6.0 ≤ r ≤ 10.0, you look for a list with ratio 8.0 and only find one with ratio 7.6, then in the next search you know 7.6 ≤ r < 8.0 is possible).

Since the lower bound for r is one that was actually achieved, you can also check which is the smallest eps for which you would have put a different fraction in the top k list of fractions.

$\endgroup$
  • $\begingroup$ Please correct me if I'm wrong, this is my understanding of your answer. We basically binary search the highest ratio $r$. Each step we find a new list $L'$ with ratio $r' > r$, we update the previous highest ratio of $L$ which is $r$. If we cant find the higher ratio, we reduce it's by setting $r_{max} = r'$, if the new ratio is the same as the previous ratio, we know that we have the optimal sum. $\endgroup$ – Loc Truong May 11 at 4:03
  • $\begingroup$ Given $k = n$, building $L'$ is very high-cost. $\endgroup$ – Loc Truong May 11 at 4:30
  • $\begingroup$ Given k = n, you may feel free to pick all fractions, since you have no other choice. Anyway, all you need is sort the list each time. And since the list is almost sorted from the previous r, because x - yr isn't changing too much, Quicksort will do that very nicely. And if speed is important to you, there are ways to make this faster. $\endgroup$ – gnasher729 May 11 at 10:20
  • $\begingroup$ Unfortunately the accept solution is in range of $O(nlogn)$, $O(n^{2})$ is too slow. $\endgroup$ – Loc Truong May 13 at 6:28
  • 1
    $\begingroup$ @j_random_hacker, I'm not entirely sure that the number of steps of the binary search is bounded at all. Certainly the interval of values to search is not a function of $n$. $\endgroup$ – Peter Taylor May 14 at 10:07
2
$\begingroup$

Based on insights in the other answers, one simple and quite efficient algorithm is:

  1. Set $r = 0$.
  2. Choose the top $k$ values of $x_i - ry_i$ (using, e.g., quickselect in $O(n)$ time).
  3. Sum the chosen $x_i$ into $X$ and the $y_i$ into $Y$.
  4. If $X - rY > 0$:
    • Set $r = X / Y$. (This will strictly increase $r$.)
    • Go to step 2.

The idea is to determine a set of lines that produce the highest possible sum at the current $r$ value, and then "slide right" along the sum of those lines (which is also a line) until it intersects the $x$ axis: where that intersection occurs is an achievable $r$ value, but it may not be the maximum possible such value, because there may be some other combination of lines that does even better. When this is no longer possible, we have found the maximum $r$.

Every time $r$ is successfully updated in step 4, at least one of the chosen $k$ lines is replaced at the following step 2 with a different line that is above it everywhere at and to the right of the current $r$ value; the replaced line will never be chosen again, so the loop executes at most $n-k$ times. Step 2 can be performed using quickselect in $O(n)$ time, for $O(n^2)$ time overall (and just $O(n)$ time when $n-k = O(1)$). Note that because we do not necessarily process each segment of the piecewise linear maximum function, there will be many inputs for which the loop executes less than the full $n-k$ times.

Removing dominated lines

It is also possible to get rid of "dominated" lines after step 2 without altering the time complexity -- this should speed things up in practice. Line $i$ is dominated if $x_i - ry_i < A$ and $y_i > B$, where $A$ is the smallest of the $k$ chosen $x_i - ry_i$ values, and $B$ is the largest of their denominators $y_i$.

$\endgroup$
1
$\begingroup$

Extending gnasher's observation:

Question: Can we find a list of k fractions with the ratio ≥ r, for some given r?

Let the sum of numerators be X, and the sum of denominators be Y, then we require X / Y ≥ r or X - rY ≥ 0. For a single fraction x / y, we can calculate x - ry. We pick the k fractions where x - ry is largest. If the sum X - rY ≥ 0, then we have a list with ratio ≥ r, otherwise there is none.

For each fraction $\frac{x}{y}$ the graph of $x - ry$ against $r$ is a straight line. The sum of the $k$ highest lines is a convex monotonically decreasing piecewise linear function with discontinuities only possible when two of the straight lines intersect. Therefore we can take the pairwise intersections of the lines to find all values of $r$ at which the $k$ highest lines might change, use bisection as described by gnasher to find the linear piece where the sum crosses zero, and then interpolate linearly within that piece to find the exact value of $r$.

Cost:

  • $\Theta(n^2)$ to find the intersections
  • $O(n^2 \lg n)$ to sort them
  • Finding the $k$ highest can be done in $O(n)$ time using quickselect, so $O(n \lg n)$ time for the bisection
  • $O(n)$ time for the final interpolation

As an optimisation, it's not necessary to do the full sort. Using quickselect to partition at the median, you can test whether the sum at that median value is above or below zero and then recurse only on half of the intersections. This gives an algorithm with $\Theta(n^2)$ running time.


This description of the curve also gives a bisection algorithm without preprocessing. If you have a value of $r$ where the curve is above the line and a value where it's below the line, you can extrapolate the linear segments of the line at those two values to find their intersection point, which must be at an intermediate value of $r$. When both values are on the same linear segment you interpolate to find the root. There is an important subtlety in the selection of the top $k$ lines at $r$: depending on whether it's a lower or an upper bound you need to break ties differently to get the correct gradient.

This takes at most $n - k$ steps (as observed by j_random_hacker - I'm kicking myself for not spotting it), so $O(n^2)$ time overall, but as with the algorithm they present it has a good chance to do better than worst case.

$\endgroup$
  • $\begingroup$ So overall this solution takes $O(n^{2}lgn)$, I think it's one of the solution but it's not fast enough. $\endgroup$ – Loc Truong May 14 at 7:38
  • $\begingroup$ The question doesn't say anything about specific performance bounds. $\endgroup$ – Peter Taylor May 14 at 10:07
  • $\begingroup$ This is a nice way to get a guaranteed time complexity in terms of $n$. But it would be even better if there was a way to somehow generate the $i$-th intersection lazily! $\endgroup$ – j_random_hacker May 14 at 19:57
0
$\begingroup$

If you sort the fractions by their ratios in descending order, and take the k fractions with largest ratio, that gives you a lower bound. Why would this not be optimal?

The k-th fraction, the k-1st fraction and so on pull the average down. Say k = 10, you have five fractions 100/10, five fractions 20/10, and 100 fractions 1/1. Taking the ten largest ratios gives a result 600 / 100 = 6. Taking the five largest, and five times 1/1 gives 505 / 55 > 9. So you want some large ratios, combined with small numerators and denominators.

In my example, can we get a result of 7? We obviously take the five fractions with a ratio ≥ 7, giving 500/50. Assume we add 5 more fractions with a sum X / Y, then we need (500 + X) / (50 + Y) ≥ 7, or 500 + X ≥ 350 + 7Y, or 150 + X ≥ 7Y or 7Y - X ≤ 150. For each fraction x / y we define its "badness" as 7y - x, then we need to find 5 fractions with a total badness ≤ 150. We take the fractions with the least badness; if the sum is ≤ 150 then we found 10 fractions with ratio ≥ 7, otherwise there are no such 10 fractions. In any case, we may have found 10 better points, and we adjust the ratio we are looking for.

$\endgroup$
  • 1
    $\begingroup$ This seems a long comment, not an answer. $\endgroup$ – xskxzr May 11 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.