| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| contest_2011-09-20 [2011/09/19 16:24] – jtkorb | contest_2011-09-20 [2011/09/20 14:33] (current) – jtkorb |
|---|
| * 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?]] | * 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 to Pairsumonious Numbers]] | * D: [[Prelude to Self-describing Sequence]] |
| * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=1143|Pairsumonious Numbers]] | * 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: [[Prelude One to Self-describing Sequence]] | * F: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1195|The Priest Mathematician]] |
| * G: [[Prelude Two to Self-describing Sequence]] | * G: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=787|Steps]] |
| * H: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990|Self-describing Sequence]] | |
| |
| //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. |
| **Hints:** | **Hints:** |
| |
| * A: | * A: One solution is to create a mapping from mistyped characters to the corresponding correct character. |
| * B: | * 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 that does not intersect anything creates one additional piece of land. A line that crosses other lines creates one additional piece of land for each crossing, plus one piece. There is one initial piece. The first two statements mean that each pair of points generates one piece of land (number of combinations of n choose 2). The second point adds a piece of land for each intersection, which comes from two lines, which comes from four points (number of combinations of n choose 4). Thus, 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: Solve [[prelude_to_pairsumonious_numbers|Prelude to Pairsumonious Numbers]] first. An exhaustive search of all possible sums works. Create a candidate vector by seeding the first location with 1/2 of the first (lowest) sum. Extend the vector by subtracting the current vector element from one of the sums. Each time the vector fills, check to see if it is a solution. If not, backtrack by selecting a different sum value at each of the extension steps. Tricky bits: watch for sums less than 0 and only extend the current candidate solution vector if the entries are non-decreasing. The check solution procedure verifies that the pair-wise sum of every pair of values has been found. | * E: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n). |
| * F: | * 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. |
| * G: | |
| * H: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n). | |
