Does this problem require a matching(or something like this) approach to solve ?!

I was thinking about this problem too. It seems that it can be solved as with matching, as with min-cost. But I still can't solve it :(

I think it can be solved using minimum cost flows. However, time limit is rather tight, so maybe my solution needs some optimizations. If you provide a link where I can test my solution I will check it and tell you more.

On this page you will find the solution proposed by the creator of the problem and test cases

http://acm-icpc.coe.psu.ac.th/contest-problem/

coding this problem is difficult

I got my solution for this problem accepted during the UVA contest, so I can tell you what I did.

I tried every possible number of 1s for the rows (let this number be x). Once x is fixed, y is uniquely determined: y = (x * number_of_rows) / number_of_columns (and y must be an integer).

Then, in order to compute the minimum number of moves for the pair (x,y) I used min-cost max-flow on the following graph (similar to what mmaxio described):

• all the rows are vertices on the left side

• all the columns are vertices on the right side

• we add an extra vertex S and edges from S to each row, of capacity x and cost 0

• we add an extra vertex T and edges from each column to T, of capacity y and cost 0

• each edge between row i and column j has capacity 1 and:

• • if there is a 0 in row i, column j : the cost of the edge is 1
• • if there is a 1 in row i, column j : the cost of the edge is -1 (but we also increase the starting_cost by 1) (all the edges are directed from rows to columns)

Then you just run a min-cost max-flow algorithm and the result is the starting cost + the minimum cost obtained by the min-cost max-flow algorithm.

However, the min-cost max-flow algorithm needs to be optimized in order to get it to run within the time limit. I will post below the optimizations that I used (I also explained them for a different problem from Codechef's November 2012 contest):

1) I used the Bellman-Ford-Moore (BFM) shortest path algorithm -- this is in theory O(N^3), but it always runs much faster than that : it uses a simple queue in which a node is inserted whenever the optimal distance to it is updated.

2) I also used the "parent checking" heuristic for BFM — i.e. when you extract a node from the queue, don't do anything with it if its parent is already in the queue again (this can be extended to multiple levels — e.g. the parent's parent, etc.).

3) There is no need to update the flow on only one path at a time — just like in the case of Hopcroft-Karp's maximum matching algorithm , we can update the flow on multiple vertex-disjoint paths after running the shortest path algorithm -- this reduces the number of times the shortest path algorithm is run, which is in fact the bottleneck in this solution.

4) Finally, after running the shortest path algorithm, visit every column and add to a sum the minimum cost of reaching that column times the number of units of flow that column still needs (i.e. the capacity of the edge from the column to T minus the flow on that edge). If you add this sum to the current minimum cost you will get the minimum possible cost you may still get. If this minimum possible cost is >= than the minimum cost found so far then there is no need to continue with the algorithm (it means that the current pair (x,y) which is tested cannot be the optimal one).