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)

Good solution! A great fix to the greedy algorithm

There is a counter-example to the statement, that step 4 reduces number of +

1 1 1 1 1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0

N = 2

1. Total number of + is equal to 9 > 4
2-3. There is no empty row or column
4. Max matching has size of 2, so the number of + increases after applying the transversal


Edited by author 19.09.2026 18:47