User Tools

Site Tools


contest_2011-09-20

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
contest_2011-09-20 [2011/09/19 16:59] jtkorbcontest_2011-09-20 [2011/09/20 14:33] (current) jtkorb
Line 13: Line 13:
   * B: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=959|Reverse and Add]]   * 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)**   * 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 One to Self-describing Sequence]] +  * D: [[Prelude to Self-describing Sequence]] 
-  * E: [[Prelude Two 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=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. //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.
  
Line 22: Line 24:
   * A: One solution is to create a mapping from mistyped characters to the corresponding correct character.   * 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.   * 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:  +  * D: The solution to this problem is almost the same as the main problem. 
-  * E+  * E: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n)
-  * F: 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.
contest_2011-09-20.1316476772.txt.gz · Last modified: 2011/09/19 16:59 by jtkorb