Differences

This shows you the differences between two versions of the page.

--- contest_2011-09-20 [2011/09/20 11:14] – jtkorb
+++ contest_2011-09-20 [2011/09/20 11:22] – jtkorb
@@ Line 23: / Line 23: @@
   * 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 1 + C(n, 2) + C(n, 4).  Use big integers and simplified combinatorial formulas.
+  * 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.