wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> binary matrix transformation
        
(Message started by: ic10503 on Sep 22^nd, 2009, 10:39am)

Title: binary matrix transformation
Post by ic10503 on Sep 22^nd, 2009, 10:39am

How do i convert a binary matrix(containing only 0s and 1s) to a complete zero matrix? Only operations allowed are u can toggle a whole row or a whole column. The conversion has to be done in minimum number of steps(a step is defined as toggling a whole row or whole column).

Title: Re: binary matrix transformation
Post by ic10503 on Sep 23^rd, 2009, 1:59am

any replies?????/

Title: Re: binary matrix transformation
Post by towr on Sep 23^rd, 2009, 2:31am

If both dimensions of the matrix are even, and the number of 1s is odd, then it's impossible. Because every step conserves parity.

[hide]In general, you don't need to toggle the same row or column more than once. So you can pick a column (or row), and split into the cases where you toggle it and one where you don't. And then toggle all the rows (or columns) that have a 1 in that column (row). After that you can only toggle rows (columns), because otherwise you mess up the first row (column). Pick any column (row) to decide which remaining rows (columns) need to be toggled, and you're done.[/hide]

Title: Re: binary matrix transformation
Post by Eigenray on Sep 23^rd, 2009, 3:51am

As towr points out, there are at most 2 solutions for any configuration. But given any solution, toggling every row and every column gives another solution. Therefore any configuration has either no solutions, or exactly two solutions, which are complements of each other. So one can simply assume, WLOG, that the first column is not flipped and then deduce all the moves; if this gives a solution with more than n moves, take the complement. But only 2^2n-1 out of 2^{n^2} configuration will have solutions at all.

Title: Re: binary matrix transformation
Post by Grimbal on Sep 24^th, 2009, 7:15am

on 09/23/09 at 02:31:29, towr wrote:

[hide]... (working solution) ... [/hide]

And if that doesn't solve it, nothing does. I.e. if that doesn't work, then there is no solution.