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/19 16:58]
jtkorb
contest_2011-09-20 [2011/09/20 14:33] (current)
jtkorb
Line 12: Line 12:
   * A: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=31&​page=show_problem&​problem=1023|WERTYU]]   * 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]]   * 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 and 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.1316476695.txt.gz · Last modified: 2011/09/19 16:58 by jtkorb