We are given $2n - 1$ boxes with a total of $B$ black and $W$ white balls. In the $i$-th, box there are $w_i$ white and $b_i$ black balls. It is required to choose $n$ boxes so that, the sum of the white balls is at least $W/2$, and the sum of black balls is at least $B/2$. Solve for $O(n\log{n})$.

What I am currently thinking is this:

Generate some hashtable to be able to track the boxes that we chose.
Sort the boxes by the quantity of the white (in increasing order) balls and chose the last $n$ balls every time keeping them in our hashtable.
Sort by the quantity of the black balls and do the same. Check every time to see if we already chose the box or not. Here comes the problem: Suppose we didn't. Then we can face a situation where we already have $n$ boxes that have in total at least $W/2$ white balls but at the same time, they have in total less than $B/2$ black balls. How can we overcome this problem?

We can't just switch the chosen boxes that have the least number of white balls with the one that have the maximum available number of black balls since the box with white balls can contain significant amount of black balls on its own.

  • $\begingroup$ maybe sorting them by the total number of balls could prove useful? $\endgroup$ – nir shahar Jun 3 at 7:35
  • $\begingroup$ Can you show that there always exists a solution? That would be a good start. $\endgroup$ – Yuval Filmus Jun 3 at 7:48
  • 1
    $\begingroup$ You haven't specified what $W$ and $B$ are. $\endgroup$ – Yuval Filmus Jun 3 at 7:49

Let $B^*, B_1, B_2, \dots, B_{2n-2}$ be the the bins sorted by the number of white balls, in non-increasing order (break ties arbitrarily). Notice that the first bin is called $B^*$.

Consider the two groups $G_E = \{ B^* \} \cup \{B_i \mid i \text{ is even} \}$ and $G_O = \{ B^* \} \cup \{B_i \mid i \text{ is odd} \}$. Clearly $|G_E| = |G_O| = 1 + \frac{2n-2}{2} = n$.

Moreover, each of $G_E$ and $G_O$ contains at least $W/2$ white balls. This is true since since for each bin not in $G_E$ (resp. $G_O$) the previous bin in the sorted order must be in $G_E$ (resp. $G_O$). That is, the total number of white balls in $G_E$ (resp. $G_O$) is at least as large as the number of white balls not in $G_E$ (resp. $G_O$).

Now, total the number of black balls in at least one group $G^* \in \{G_E, G_O\}$ must be at least $B/2$. This is easy to see since $\{G_E, G_O \setminus \{B^*\}\}$ is a partition of the set of bins, and hence the bins in at least one set of the partition (which is either $G_E$ or a subset of $G_O$) must contain at least half the black balls.

| cite | improve this answer | |
  • $\begingroup$ Wow... very elegant $\endgroup$ – dingalapadum Jun 3 at 16:44

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.