Differences

This shows you the differences between two versions of the page.

--- contest_2010-10-14 [2010/10/14 10:15] – created jtkorb
+++ contest_2010-10-14 [2010/10/15 05:15] (current) – jtkorb
@@ Line 14: / Line 14: @@
   * Team 4: Abram, John B, Tim
   * Team 5: Alex, Eric, Dylan
 ===== Problems =====
-A and B are from Chapter 7: Number Theory.  C, D, and E are from Chapter 8: Backtracking.  For A, use the GCD algorithm in the text.  For the backtracking problems, use the schema in the text.
   * A: [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110901&format=html|Bicoloring]]
@@ Line 24: / Line 21: @@
   * D: [[http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=111105&format=html|Cutting Sticks]]
+**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.