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 is the minimum weight required to create a talent sum of . To make sure each cow is used at most once and the order of the cows doesn't matter, the indices of are iterated though from greatest to least, and the are iterated though in the outer loop; the implementation should make this clear. This maximizes the ratio as desired. Then, the maximum ratio of can be easily found by going through and ignoring any that is less than .
My 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!