User Tools

Site Tools


contest_2011-10-04

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
contest_2011-10-04 [2011/10/03 18:47]
jtkorb
contest_2011-10-04 [2011/10/04 11:04] (current)
jtkorb
Line 21: Line 21:
 **Hints:** **Hints:**
  
-  * A: [[Backtracker.java|Here]] is an abstract class that defines the 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. +  * 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: ​ai true means element i is in the subset; false means not in the subset. What are the candidate values? ​ ​(Obviously,​ true and false.) +  * 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 values ai indicate ​the row in which the queen in column i appears. ​ Choose candidates by pruning all the rows that conflict with (are "​attacked by") queens already placed in the previous ​columns. +  * 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.  ​Solution ​vector contains n*n booleans indicating if a bishop is located in that space. ​ Need functions that convert square number (0..n*n-1) to row and column ​values ​(integer division and mod are your friends). ​ See Queens solution to determine if two bishops are in attack positions (the slope of the line between them is 45 degrees). +  * 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 ​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 number of people who can see left and number who can see right. ​ Prune when impossible situations arise (e.g., tallest person is less than locations from left edge, or closer than locations from right edge). ​ More efficient representations and pruning criteria possible.+  * 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.   * F: More exotic application of backtracking.
contest_2011-10-04.txt · Last modified: 2011/10/04 11:04 by jtkorb