 Tim Korb's Home Page

Site Tools

contest_2011-09-20

This is an old revision of the document!

Weekly Contest for September 20, 2011

Join the Contest

% cd your-pc2-directory
% /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.

Problems

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 me know.

Hints:

• A:
• B:
• C: The trick… A line that does not intersect anything creates one additional piece of land. A 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.
• D:
• E: Solve 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.
• F:
• G:
• H: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n). 