Comments on ps3b
================



Algorithm
---------

The correct scheduling algorithm was to sort the problem sets by the
ratio D/P of days divided by penalty points per day. The way to see
this was to look at two psets (D1, P1) and (D2, P2) and figure out
which one to complete first. If we choose to complete pset 1 first
then pset 2, the total number of penalty points would be:

D1*P1+(D1+D2)*P2

If we instead completed pset 2 first then pset 1, we would have:

D2*P2+(D1+D2)*P1

The difference between these two is:

D1*P2 - D2*P1

Dividing this by P1*P2, we see that if D1/P1 is less than D2/P2, then
this value is negative, meaning that it's cheaper to do pset 1
first. If D1/P1 is greater than D2/P2, then it's cheaper to do pset 2
first. This means that in a correct ordering of the psets, psets are
sorted in increasing order of the ratio D/P. Thus, we can sort all
psets by this ratio and compute the total number of penalty points for
this schedule.


Implementation notes
--------------------

By far the most common (but least severe) issue with students'
submissions was not reading from ps3b.in and writing to ps3b.out, as
specified in the problem statement. (Many people read from, e.g.,
ps3b-sample10.in.)

The next most common type of problem was that either the heap sort or
the scheduling code was O(N^2). The heap sort should have been O(N log
N) and the scheduling code should have been O(N) (although you could
have gotten away with O(N log N), since the heap sort was already O(N
log N)).

By far the most common specific problem with heap sort was an improper
use of a list slice. Students who wanted to remove an element from the
end of their heap often used code such as "heap=heap[:-1]" or
"heap=heap[0:(length-1)]". This code makes an entirely new list, which
takes O(N) time, makes removing an element from the heap take O(N)
time, and makes heap sort O(N^2) overall. Better was to use something
like "heap.pop()" to remove the last element in constant time.

A few students also rebuilt the entire heap after each heap operation,
instead of only fixing O(log N) elements on a path from the root to a
leaf. This also made heap sort O(N^2) instead of O(N log N).

Also, many students had slow scheduling code. Usually, this involved
using two loops to compute penalty points instead of using a single
loop and maintaining a running sum of penalty points being accrued per
day. Some students didn't have two explicit loops, but effectively had
the same thing inside of a fancy list comprehension.