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 11:02]
jtkorb
contest_2011-09-20 [2011/09/20 14:33] (current)
jtkorb
Line 10: Line 10:
 ===== Problems ===== ===== Problems =====
  
-  * A: [[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]] 
-  * B: [[http://​uva.onlinejudge.org/​index.php?​option=com_onlinejudge&​Itemid=8&​category=33&​page=show_problem&​problem=10018|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.
Line 23: Line 22:
 **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.  ​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).+
contest_2011-09-20.1316455336.txt.gz · Last modified: 2011/09/19 11:02 by jtkorb