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 10:10]
jtkorb
contest_2011-09-20 [2011/09/20 14:33] (current)
jtkorb
Line 10: Line 10:
 ===== Problems ===== ===== Problems =====
  
-  * X: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=33&​page=show_problem&​problem=10082|WERTYU]] +  * A: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=31&​page=show_problem&​problem=1023|WERTYU]] 
-  * A: [[Prelude to Pairsumonious Numbers]] +  * B: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=33&​page=show_problem&​problem=959|Reverse and Add]] 
-  * A: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=33&​page=show_problem&​problem=1143|Pairsumonious Numbers]] +  * 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)** 
-  * B: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=32&​page=show_problem&​problem=1132|Longest Nap]] +  * D: [[Prelude to Self-describing Sequence]] 
-  * C: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=32&​page=show_problem&​problem=967|Shoemaker'​s Problem]] +  * 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)** 
-  * D: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=34&​page=show_problem&​problem=1154|How Many Pieces of Land?]] +  * F: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=34&​page=show_problem&​problem=1195|The Priest Mathematician]] 
-  * E: [[Prelude One to Self-describing Sequence]] +  * G: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=34&​page=show_problem&​problem=787|Steps]]
-  * 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]]+
  
 //​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 24: Line 22:
 **Hints:** **Hints:**
  
-  * A: Solve [[prelude_to_pairsumonious_numbers|Prelude ​to Pairsumonious Numbers]] first.  ​An exhaustive search of all possible sums works. ​ Create ​candidate vector by seeding ​the first location with 1/2 of the first (lowestsum.  ​Extend the vector by subtracting the current vector element from one of the sums.  ​Each time the vector fillscheck to see if it is solution.  ​If notbacktrack 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: One solution is to create a mapping from mistyped characters to the corresponding correct character. 
-  * B: This problem ​is from the chapter on sorting.  ​Comparators help here. +  * B: Use procedure, ''​reverse(n)'',​ to reverse ''​n''​ according to the rules of the problem. ​ A brute force test (up to 1000is sufficient. 
-  * C: See B+  * 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: Once you see the trick, ​the solution is easy with big integers (are they required?).+  * 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 ten seconds.
contest_2011-09-20.1316452200.txt.gz · Last modified: 2011/09/19 10:10 by jtkorb