User Tools

Site Tools


contest_2011-09-13

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-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