Weekly Contest for September 6, 2011
From your lab workstation, use these commands to get started…
% mkdir pc2
% cp -p /homes/cs390cp/pc2/pc2v9.ini pc2
Join the Contest
% cd pc2
% /homes/cs390cp/pc2/bin/pc2team &
Log in using your individually assigned “teamX” account and password. You can work in the current window/directory, creating a subdirectory for each problem.
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 me know.
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 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.