Drop
----

This problem was intended to be the hardest problem in the set, and indeed, nobody
solved it. When choosing to drop tests, there is a trade-off between tests with very
low percentage scores and tests with mediocre percentage scores but with a large number
of questions. Which one of these is better can depend on the other tests you are
keeping. Figuring out how to balance these requirements is the heart of this problem.

The first thing you have to realize is that a simple greedy algorithm is not going
to be correct. For example, it seems reasonable to drop tests one at a time, always
choosing to drop the test that will improve your cumulative average by as much as
possible. However, it turns out this is wrong. For example, consider dropping 2 tests
from a group of 100/100, 14/50, 14/50, 100/200, and 100/200. The greedy approach would
first drop a 14/50 test and then a 100/200 test to get a score of 214/350 = 61%, but
the optimal strategy is to drop both 100/200 tests for a score of 128/200 = 64%.

If you have done a lot of other programming competitions, you might also think of the
dynamic programming approach (see the stones write-up). By tracking the number of
questions and the number of tests, you can use this to solve the problem in
(number of questions)*(number of tests) time. Unfortunately, the maximum number of
questions over all the tests is a trillion, so that is no good either.

What do you do then? It turns out that the problem can be solved with a binary search.
We ask the following question: "Can you drop k tests to make your cumulative average
at least x?". It turns out that fixing x makes the problem substantially easier
because this is enough to determine which tests are better than others.

If we fix x, we need to choose tests so that
    (sum a_i) / (sum b_i) >= x
       <=> sum a_i >= sum (x*b_i)
       <=> sum (a_i - x*b_i) >= 0.
Thus, we compute c_i = a_i - x*b_i for each i. We now need to drop k of those values so
that their sum is at least 0. This is a much easier problem! Just sort the c_i's and
drop the k smallest values.

This reduces everything to a standard binary search problem. For each x, we can test
whether we can get an average of at least x, and we need to find the maximum average
that can be made. C++ code is shown bleow.

    double lb = 0, ub = 1;
    for (i = 0; i < 100; i++) {
      double x = (lb+ub)/2;

      for (j = 0; j < tests; j++)
	scores[j] = num[j] - x*den[j];
      sort(scores, scores+tests);
      double total = 0;
      for (j = k; j < tests; j++)
	total += scores[j];

      if (total >= 0)
	lb = x;
      else
	ub = x;
    }
    cout << int(100*lb + 0.5) << endl;

• 太强了！ (2848) S1 2006-08-20 13:19:06
• 进来看看 (79) xtu723 2008-09-18 19:28:08
• 牛X (2) ZaakDov 2009-09-24 20:48:31
• Re:原装解题报告 (9) weihaohaoren 2012-01-26 17:18:12