| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| contest_2011-10-04 [2011/10/01 14:26] – jtkorb | contest_2011-10-04 [2011/10/04 11:04] (current) – jtkorb |
|---|
| ===== Problems ===== | ===== Problems ===== |
| |
| * X: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=802|Little Bishops]] | * A: [[Prelude 1 to Backtracking -- Permutations]] |
| * X: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=1069|Queue]] | * B: [[Prelude 2 to Backtracking -- Subsets]] |
| * X: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=942|Garden of Eden]] | * C: [[Prelude 3 to Backtracking -- Queens]] |
| | * D: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=802|Little Bishops]] |
| | * E: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=1069|Queue]] |
| | * F: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=942|Garden of Eden]] |
| |
| //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 [[jtk@purdue.edu|me]] know. | //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 [[jtk@purdue.edu|me]] know. |
| **Hints:** | **Hints:** |
| |
| * A: | * A: Use this abstract class that defines the [[Backtracker.java|backtracking]] interface and solution from the textbook. Candidates are the numbers ''1..N'' (or ''0..N-1''); but prune out the ones that have already appeared in ''a''. |
| | * B: The solution array is a vector of booleans: ''a[i]'' true means element ''i'' is in the subset; false means not in the subset. What are the candidate values? |
| | * C: The solution array value ''a[i]'' indicates the row in which the queen in column ''i'' appears. Choose candidates by pruning all the rows that conflict with (i.e., are "attacked by") queens already placed in the earlier columns. |
| | * D: Like Queens, except more Bishops are possible (they only conflict diagonally, not via rows and columns). The solution vector contains ''n*n'' booleans indicating if a bishop is located in that space. Need functions that convert a square number (''0..n*n-1'') to row and column numbers (integer division and mod are your friends). See Queens solution to determine if two bishops are in attack positions (i.e., the slope of the line between them is 45 degrees). |
| | * E: Generate people placements from left to right. Need functions to compute the number of people who can see to the left and the number who can see to the right. Prune when impossible situations arise (e.g., if the tallest person is less than ''p'' locations from the left edge, or if closer than ''r'' locations from the right edge). More efficient representations and pruning criteria are possible (and necessary to be accepted at the UVA or PC sites). |
| | * F: More exotic application of backtracking. |
