Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls


We are given $ 2n – 1$ boxes with black and 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.

Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic

So a tournament is just a complete directed graph, I believe.

I’m having trouble proving this problem. I know it is induction however. I was thinking the base case is $ 2^1$ vertices, and therefore we have a sub-tournament of 1 + 1 vertices, which holds.

Then in our induction step we have to show $ 2^{n + 1}$ . But I’m not sure how to approach this. Any ideas would be extremely appreciated.

Least Constraining Value heuristic for graph coloring problem

The graph coloring problem involves assigning colors to vertices in a graph, such that no pair of adjacent vertices have the same color. I was given the problem to use least constraining value heuristic to determine the order in which the nodes would be colored.

Image of the given graph

The image shows the graph that must be colored using the set of colors {a,b,c}, using least constraining value heuristic. From my understanding of the LCV heuristic, I am supposed to pick the vertex which eliminates the least amount of colors for its neighbors. We are also given the condition that for tie breaking, we use the smaller numbered node first, and the color ‘a’ first, ‘b’ second and ‘c’ third. Looking at each node, assigning color ‘a’ to vertex 3 only eliminates the possibility of vertex 2 being colored as ‘a’, while all other nodes cause 2 or more changes to their neighbors. Going forward, got the following order. 3a 0a 1a 2b 4c 5b But according to the key, the answer is supposed to be as follows. 0a 1a 2b 3a 4c 5b Could someone please explain what I’m doing wrong?

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem:

An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of 10 meters (5m on the right, 5m on the left with him being in the middle).

No matter where the artworks are put in the hallway we want the minimal amount of guards as possible.

My Greedy Algorithm:

Start at the beginning of the hallway. Find the position of the closest artwork from the entrance. Put the guard at position closest artwork + 5m ahead. Eliminate all the artworks covered by the guard. Re-do the process but this time start where the range of the previous guard ended 

Now how do I write a proof for this? How do I prove that my algorithm is indeed optimal? Which mathematical proof techniques can I use?

Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes

I’m having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary tree whose levels are all full except for the last one in which all the nodes are as far left as possible.

I thought of proving it using induction but I’m not really sure how to do so. Any ideas?

How can merging two sorted arrays of N items require at least 2N – 1 comparisons in every case?

The HW question, on page 362 of Data Structures and Algorithms in C++: Fourth Editionby Mark Allen Weiss, reads as follows:

Prove that merging two sorted arrays of N items requires at least 2 * N – 1 comparisons. You must show that if two elements in the merged lists are consecutive and from different lists, then they must be compared

If we are trying to find the lower bound then wouldn’t the number of comparisons be N, not 2 * N – 1? If the largest element is some array Ais smaller than the smallest element in some array B then at most you would only have to do N comparisons since after all of A‘s elements are placed in the merged array then the remaining elements in B‘s can simply be appended in to the merged array.

The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2 * N – 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

Note: I am not asking for an answer to the HW question itself as I know that is deprecated. I am confused about the implied assertion the question is making about the lower bound