### 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: 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.
• B: This problem is from the chapter on sorting. Comparators help here.
• C: See B.
• D: Once you see the trick, the solution is easy with big integers (are they required?).
• E: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n).
contest_2011-09-20.1316452200.txt.gz · Last modified: 2011/09/19 10:10 by jtkorb