ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1092. Transversal

A 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
Posted by wangbicheng1 28 Nov 2015 18:07
Good solution! A great fix to the greedy algorithm