Tim Korb's Home Page

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Weekly Contest for September 13, 2011 ======

===== Join the Contest =====

   % cd your-pc2-directory
   % /homes/cs390cp/pc2/bin/pc2team &

Log in using your individually assigned "teamX" account and password.  You can work in the current window/directory, creating a subdirectory for each problem.

===== Problems =====

  * A: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=1143|Pairsumonious Numbers]]
  * B: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=32&page=show_problem&problem=1132|Longest Nap]]
  * C: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=32&page=show_problem&problem=967|Shoemaker's Problem]]
  * D: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1154|How Many Pieces of Land?]]
  * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990|Self-describing Sequence]]

//Remember:// If you've already solved one or more of these problems, try (1) solving again without referring to your old solution, and/or (2) using a different language (Java or C++).  If you want to work on an additional problem from the book, let [[jtk@purdue.edu|me]] know.

**Hints:**

  * A: Solve [[prelude_to_pairsumonious_numbers|Prelude to Pairsumonious Numbers]] first.  An exhaustive search of all possible sums works.  Create a candidate vector by seeding the first location with 1/2 of the first (lowest) sum.  Extend the vector by subtracting the current vector element from one of the sums.  Each time the vector fills, check to see if it is a solution.  If not, backtrack by selecting a different sum value at each of the extension steps.  Tricky bits: watch for sums less than 0 and only extend the current candidate solution vector if the entries are non-decreasing.  The check solution procedure verifies that the pair-wise sum of every pair of values has been found.
  * B: This problem is from the chapter on sorting.  Comparators help here.
  * C: See B.
  * D: Once you see the trick, the solution is easy with big integers (are they required?).
  * E: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n).