Weekly Contest for October 14-15, 2010
The contest this week is a team contest. One workstation per team. Divide up the problems, one per person. Solve, fight over workstation, collaborate on algorithms, code reviews, and debugging.
The contest server is on pc2.cs.purdue.edu. From a departmental UNIX machine, use this command to get started…
% (cd /homes/jtk/pc2; bin/pc2team)
Teams
Team 1: Ben, Hearson, Winthan
Team 2: Derek, Yuedong
Team 3: Emily, John L
Team 4: Abram, John B, Tim
Team 5: Alex, Eric, Dylan
Problems
Notes:
A: Recursive walk of the graph will do. Use a marker to keep track of nodes you've already visited.
B: Tricky. Use Dijkstra's (or possibly Floyd's) algorithm multiple times.
C: Dynamic programming. Sort and find recurrence. (Actually, simple iteration works, too.)
D: Dynamic programming. Use recursive divide and conquer trying each possible initial slice in turn.