|
|
back to boardA non-greedy solution Posted by ucs6 3 Dec 2012 11:52 I solved this problem with a non-greedy solution. Basically there are only one of the following 4 cases: 1. total number of '+' is <= 2N, problem solved; 2. There exists one column without any '+', and there also exists one column with more than 2 '+'(i.e. at least three), in this case you can "move" that two '+'s to the empty column (through two permutations); 3. Similar condition for case 2, move the row; 4. None of above is satisfied, using Hungarian Algorithm to find a best traversal. Repeat above process until case 1 is reached. This is not greedy and we can prove that it is correct: Both case 2 and 3 guarantees that 1) the total number of '+'s does not change, and 2) cannot continue infinitely, i.e. it must reach case 4 at some point. Then case 4 guarantees the total number of '+'s will be reduced at least by 1 (due to the fact that 2N + 1 is odd, and neither case 2 and case 3 is satisfied, can be easily proved) Re: A non-greedy solution Good solution! A great fix to the greedy algorithm |
|
|