Below are solutions I coded over a two hour period one night while watching Futurama. Most of the programs compiled and passed on the first try, but I had the advantage of having seen all of the problems before (including remembering the algorithms we used and silly mistakes we made).
All of my solutions are short, so hopefully they are not too hard to understand despite the lack of commenting. If the source code itself combined with the short description is insufficient, let me know and I will expand upon them.
I have also included what mistakes our team made for the problems we missed during the competition.
This problem is nicely solved using dynamic programming. Short explanation, initialize a triangular memory array with 1's anywhere paper exists in the input and 0's anywhere else. These values represent the height of the largest triangle that can be formed with the corresponding tile as the tip. Looping over all entries, calculate the largest height each entry can have, and keep track of the best over all. The largest area is then height2.
We missed this problem because while devising an algorithm, we drew the triangles as blocks to make array indices easier to visualize, but this meant we did not pay attention to tile orientation.
[ Download code ]
There are two parts to this problem:
implementing a recursive descent parser
and printing the polynomial running time.
(You also need some simple polynomial arithmetic,
but that is rather trivial in this problem.)
The recursive descent parser does not even need look ahead,
so it is really quite trivial.
Printing the polynomial is tricky only because of a number of special cases:
0,
1,
c,
n,
c*n,
n^d,
and c*n^d
(for values of c and d greater than 1).
We missed this problem because of the polynomial printer. In our original solution, it printed an empty string for a constant “1” polynomial. (This is somewhat embarassing considering how frequently polynomial printing problems arise at competitions.)
[ Download code ]
Assuming you remember the Pythagorean theorem, this problem should be rather simple.
We missed this because of a simple typo in the source code (wrong sign on one of the directional vectors), which was not tested in the judging test data.
[ Download code ]
The trick is to realize for a video camera to see the whole area, it needs to be on the inside of each wall plane. Start with an infinite bounding box, and for each wall restrict the box to the interior of the wall. Because the walls are axis-aligned, the bounding box must be rectangular. Further, because the vertices are given in clockwise winding order, you can easily determine which side of the wall faces inward.
[ Download code ]
This problem is solvable by a breadth-first search, but make sure to realize that a greater number of moves is acceptable if it results in fewer block pushes. (During the programming competition, Jack used a priority queue for this; in the solution below, I just use two queues.)
Verifying the solution to this problem is a pain, because some puzzles have multiple solutions, and the judging software used some funky algorithm to choose between equivalent cases. E.g., in a large open area with the pusher at the top left and the block at the bottom right, the judging data shows the pusher moving diagonally towards the block, whereas our solution just searches each direction in turn.
[ Download code ]
I won't bother describing the solution to this problem.
[ Download code ]
There are at most five people with three different states and two different states for the time of day, so just 2*35 = 486 combinations. Loop through each combination, test if all of the statements are valid, and keep track of what each person can be. Finally, loop through the records of what everyone can be, and print out appropriately. (Solution is generally similar to what Jack wrote during the competition, but I simplified the output code logic a bit.)
During the competition, we forgot the period on the end of some output lines. (We would have caught this on the sample data using automated testing rather than eyeballing the output.)
[ Download code ]