Let $A=\{a_1, a_2, ... , a_n\}$ be a set of non-negative real numbers and $B=\{b_1, b_2, ..., b_n\}$ be sets of positive real numbers.

Let $s = \dfrac{ \sum_A a}{\sum_B b} = \dfrac{a_1+a_2+\dots+a_n}{b_1+b_2+\dots+b_n}$.

What I want to do find $k$ so that

$s_1 = \dfrac{\sum_{A-\{a_k\}} a }{\sum_{B-\{b_k\}} b}$ is the largest.

And more generally, find

$s_p = \dfrac{\sum_{A-\{a_{k_1},a_{k_2},\dots,a_{k_p}\}} a }{\sum_{B-\{b_{k_1},b_{k_2},\dots,b_{k_p}\}} b}$

I'm not exactly sure what this is called, and I tried doing a google search but I wasn't able to find what I am looking for.

And of course, I can do this by exhaustion, but I feel that there should be a smart way to figure this out...

  • $\begingroup$ Unless something is known in advance about the elements of that set, there's not much that can be done. $\endgroup$ – apnorton Dec 12 '14 at 1:25
  • $\begingroup$ @anorton So nothing other than brute force? $\endgroup$ – Braindead Dec 12 '14 at 1:26
  • $\begingroup$ Depends on what you mean by brute force, but yes. Clearly you want to remove the smallest $p$ elements from $A$ and the largest $p$ elements from $B$. Thus, you just have to find the biggest/smallest elements of a set. If you're worried about asymptotic performance for a program, I believe there are linear-time algorithms for finding the least/greatest $p$ elements of a set. $\endgroup$ – apnorton Dec 12 '14 at 1:29
  • $\begingroup$ @anorton: I think he is deleting matching elements, that the sets are really sequences. $\endgroup$ – Ross Millikan Dec 12 '14 at 1:30
  • $\begingroup$ @RossMillikan,@anorton: Yup, I want to delete matching elements. $\endgroup$ – Braindead Dec 12 '14 at 1:31

The naive thing is to delete the smallest $\frac {a_i}{b_i}$, but this fails. Let $A=(1,51,100), B=(2,100,100).$ The worst grade is $\frac 12$, but deleting it leaves $\frac {151}{200}$, while deleting the $\frac {51}{100}$ leaves $\frac {101}{102}$, much better. The simple approach is to scale the tests to the same possible score, then it is easy.

  • $\begingroup$ Hmm... it appears dropping the $k$ with the largest $b_k - a_k$ seems to do the trick. $\endgroup$ – Braindead Dec 12 '14 at 3:10
  • $\begingroup$ I don't think that works, either. Let $A=(1,2,100), B=(2,4,103)$. At the start you have $\frac {103}{109}$, but dropping the last leaves you with $\frac 36$ $\endgroup$ – Ross Millikan Dec 12 '14 at 3:23
  • $\begingroup$ ::forehead slap:: you are right. I was thinking about minimizing the difference between the numerator and the denominator, but of course that doesn't imply a bigger fraction. $\endgroup$ – Braindead Dec 12 '14 at 3:45

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.