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 20, 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=31&page=show_problem&problem=1023|WERTYU]]
  * B: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=959|Reverse and Add]]
  * C: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1154|How Many Pieces of Land?]] **(not open to Brent or Hearson)**
  * D: [[Prelude to Self-describing Sequence]]
  * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990|Self-describing Sequence]] **(not open to Andrew, Derek, Hearson, or Yuedong)**
  * F: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1195|The Priest Mathematician]]
  * G: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=787|Steps]]

//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: One solution is to create a mapping from mistyped characters to the corresponding correct character.
  * B: Use a procedure, ''reverse(n)'', to reverse ''n'' according to the rules of the problem.  A brute force test (up to 1000) is sufficient.
  * C: The trick...  A line between two points creates one additional piece of land on its own.  In addition, a line that crosses other lines creates one additional piece of land for each crossing.  There is one initial piece.  Thus, each pair of points adds one piece of land (n choose 2) and each set of four points adds a piece of land corresponding to the intersection (n choose 4).  The number of pieces of land is, thus, 1 + C(n, 2) + C(n, 4).  Use big integers and simplified combinatorial formulas.
  * D: The solution to this problem is almost the same as the main problem.
  * E: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n).
  * F: A brute force solution (trying all values of k between 1 and n) works for the contest test data.  You'll need a more efficient solution to get it past the UVA judge in ten seconds.