Misc. thoughts on the problem set.


1. Raffles

   -- The number of digits you need to read is the same as the number
      of digits in the number of tickets sold.  So, you need to figure
      out the length of N.  There are tons of ways of doing that.

   -- There is an issue with the data that I had not considered until
      someone pointed it out.  Namely, for 10 tickets (or any power of
      10), you need to read 1 less digit, e.g., for 10 tickets, you
      really only need to read 1 digit.  I left it alone for the contest
      since a majority of teams wrote the solution the  way I had.

2. Memoization

   -- There are notes in the solution file.  For no memoization,
      the number of work units is Fib (n + 1).  For some
      memoization, the number of work units is n (see the solution
      for a proof).  You can also do brute force for this case.

   -- I did give some extra time for this problem in the submissions,
      which enabled some brute force programs to go through
      (you really should memoize the answers though).

3. Worst. Problem. Ever.

4. Polynomial Multiplication

5. Total Drama Island

    -- It's a stable marriage problem.

6. Election Time!

    -- Hard part is getting the p values.  It can be done using a modified
       Floyd-Warshall (I think it's a form of min-flow / max-cut, but I didn't
       think about it that much.)  I deliberately limited the number of
       candidates so that you could also do this through brute force
       generation of the paths.  You can very quickly eliminate possible
       paths once you find one path.