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 revision Previous revision
Next revision
Previous revision
contest_2011-09-20 [2011/09/20 11:14]
jtkorb
contest_2011-09-20 [2011/09/20 14:33] (current)
jtkorb
Line 16: Line 16:
   * 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)**   * 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]]   * 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 23: 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: The solution to this problem is almost the same as the main problem.   * 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).   * 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.   * 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.1316542442.txt.gz ยท Last modified: 2011/09/20 11:14 by jtkorb