Differences

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

--- contest_2011-09-06 [2011/09/05 11:58] – jtkorb
+++ contest_2011-09-06 [2011/09/06 12:21] (current) – jtkorb
@@ Line 17: / Line 17: @@
 ===== Problems =====
-  * A: [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110202&format=html|Poker Hands]] (Repeated here for those of you who want to try it and for those who didn't quite get it last week.)
+  * A: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=30&page=show_problem&problem=1256|Poker Hands]] (Repeated here for those of you who want to try it and for those who didn't quite get it last week.)
   * B: [[prelude to doublets|Prelude to Doublets]]
-  * B: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1091|Doublets]]
+  * C: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1091|Doublets]]
-  * C: [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110402&format=html|Stacks of Flapjacks]]
+  * D: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=32&page=show_problem&problem=56|Stacks of Flapjacks]]
-  * D: [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110508&format=html|Pairsumonious Numbers]]
+  * E: [[prelude to pairsumonious numbers|Prelude to Pairsumonious Numbers]]
-  * E: [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110601&format=html|How many Fibs?]]
+  * F: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=1143|Pairsumonious Numbers]]
-Candidates...
+  * G: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1124|How many Fibs?]]
-  * Yahtzee
-  * Pairsumonious Numbers
-  * How Many Pieces of Land?
 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.
@@ Line 34: / Line 30: @@
   * A: The main trick to this problem is creating a hand evaluation method that returns a simple value that can be compared to other hands.  One representation of hand value is as a six-character string, where the first character represents the hand type (e.g., 1 = "high hand", 9 = "straight flush") and the remaining five characters are encoded values of the cards (e.g., "A" = deuce, "B" = three, ..., and "M" = ace) in order of relevance to the hand type (e.g., list the three-of-a-kind from a full house before the pair, even if the pair is higher).
-  * B: The PC site does not judge this problem correctly, PC2 may not, either.  Get an "Accepted" at the UVA site before submitting to contest.
+  * B: The input format is the same as for Doublets.  Use this prelude to set up for it.  You probably want to store the dictionary in a hash table.
+  * C: The PC site does not judge this problem correctly, PC2 may not, either.  Get an "Accepted" at the UVA site before submitting to the contest.  One approach is to preprocess the dictionary: For each dictionary word, create a set of all words in the dictionary that are one character away from that word.
+  * D: Be careful to allow for the case in which a single stack has flapjacks of the same diameter.
+  * E: For Pairsumonious Numbers, you'll need to store the N*(N-1)/2 values into a sorted array to use them to compute the N sums.  This problem gets you set up for that.
+  * F: Although backtracking is discussed in a later chapter, it works here, too.
+  * G: Rumor has it that Sterling's Formula works on this problem, but you can also create a cache of Fibonacci numbers and do the counting that way.