contest_2011-09-20

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

Both sides previous revision Previous revision Next revision | Previous revision | ||

contest_2011-09-20 [2011/09/20 10:21] 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 three 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.1316539301.txt.gz ยท Last modified: 2011/09/20 10:21 by jtkorb