contest_2011-09-13

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

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

contest_2011-09-13 [2011/09/11 08:18] jtkorb |
contest_2011-09-13 [2011/09/20 14:34] (current) jtkorb old revision restored |
||
---|---|---|---|

Line 11: | Line 11: | ||

* A: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=1143|Pairsumonious Numbers]] | * A: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=1143|Pairsumonious Numbers]] | ||

+ | * B: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=32&page=show_problem&problem=1132|Longest Nap]] | ||

+ | * C: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=32&page=show_problem&problem=967|Shoemaker's Problem]] | ||

+ | * D: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1154|How Many Pieces of Land?]] | ||

+ | * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=990|Self-describing Sequence]] | ||

- | 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 this chapter, 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: 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. | * A: 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. | ||

+ | * B: This problem is from the chapter on sorting. Comparators help here. | ||

+ | * C: See B. | ||

+ | * D: Once you see the trick, the solution is easy with big integers (are they required?). | ||

+ | * E: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n). |

contest_2011-09-13.1315754280.txt.gz ยท Last modified: 2011/09/11 08:18 by jtkorb