### Site Tools

contest_2011-09-20

# 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: One solution is to create a mapping from mistyped characters to the corresponding correct character.
• 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 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: The solution to this problem is almost the same as the main problem.
• E: Pre-compute a run-length encoded array to represent f, then do a binary search to find f(n).
• 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.