Correctness of Flow Solution

Revision en2, by MedoN11, 2017-05-03 10:36:18

Hello.

Recently I was solving this problem : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2103

Simply the problem says given 12 * n grid of zeros and ones, find the minimum number of swaps to map it to another 12 * n grid where allowed moves are down, up, left and right.

Upon tracing some samples the solution appeared to be minimum cost bipartite matching between non matched ( should be 0 but is 1 or vice versa) one nodes and zero nodes. ( If they are not equal this is impossible). I couldn’t prove correctness so I ran it against a backtracking solution for many small cases, and all passed. Submitted a flow solution and got AC.

Can any body help with proving correctness?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MedoN11 2017-05-03 10:36:18 38 Tiny change: 'n matched one nodes' -> 'n matched ( should be 0 but is 1 or vice versa) one nodes'
en1 English MedoN11 2017-05-03 10:34:36 739 Initial revision (published)