MedoN11's blog

By MedoN11, history, 7 years ago, In English


Recently I was solving this problem :

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it