Official Editorial

Warning: Common Misconception

Note that the following solution is incorrect: Instead of using binary search as the official solution does, a knapsack can be done. An array of talents can be kept, where talent[i]\texttt{talent}[i] is the minimum weight required to create a talent sum of ii. To make sure each cow is used at most once and the order of the cows doesn't matter, the indices of talent\texttt{talent} are iterated though from greatest to least, and the cows\texttt{cows} are iterated though in the outer loop; the implementation should make this clear. This maximizes the ratio tw\frac{t}{w} as desired. Then, the maximum ratio of tiwi\frac{t_i}{w_i} can be easily found by going through talent\texttt{talent} and ignoring any wiw_i that is less than WW.

My O(Total talent n)\mathcal{O}(\text{Total talent } \cdot n) code is below:

Show Code

However, even though this passes all of the test cases on USACO, there is a fatal flaw to this. We are finding the minimum weight required for each talent sum. What if the minimum weight for a talent sum is less than the weight threshold? Consider if the threshold is indeed attainable with a particular talent sum but the DP concluded it is not. The DP never considers a slightly higher weight, one that can pass the threshold, as a candidate for the answer. This means the DP fails on cases where the aforementioned scenario occurs and is optimal; one example is as follows:

4 16
11 2
17 2
12 2
4 4

The correct answer is 375; the above solution outputs 296.

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!