C++ code related to matrix,n*n grid etc

Question

Hii, The problem statement is:

Buttons

Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation. Edit: When the initial and the final configurations are the same, print "0". Input
The first line contains t, the number of test cases (about 10). Then t test cases follow.

Each test case has the following form: * The first line contains n, the size of the board (1 ≤ n ≤ 1000). * n lines follow. The ith line contains n space separated integers representing the ith row of the initial grid. Each integer is either a 0 or a 1. * n lines follow, representing the final grid, in the same format as above. Output For each test case, output the number of row-button presses, followed by the row buttons that must be pressed. Print the number of column-button presses next, followed by 0-indexed indices of the column buttons that must be pressed. The total number of button presses must be minimized. Output "-1" if it is impossible to achieve the final configuration from the initial configuration. If there is more than one solution, print any one of them. Example Input: 1 3 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1

Output: 1 0 1 2

I have uploaded code at: http://www.megaupload.com/?d=VOJR39BM

Though it works absolutely fine on my machine,it doesnt accept a solution at codechef and gives me a wrong answer.Can anyone guide me what to do pls pls pls??

Code has been written in C++ and compiled using g++ compiler.

Any help would be deeply appreciated ppl :) Thanking in advance

Answer 1

In the code posted, I would revise the code after you calculate "matrixc". I find it very difficult to follow beyond that point, so I'm going to stop looking at the code and talk about the problem. For those without the code, matrix C = initial matrix - final matrix. The matrices are over the binary field.

In problems like these, look at the symmetries in the solution. There are three symmetries. One is the order of the buttons does not matter. If you take a valid solution and rearrange it, you get another valid solution. Another symmetry is that pressing a button twice is the same as not pressing it at all. The last symmetry is that if you take the complement of a valid solution, you get another valid solution. For example, in a 3x3 grid, if S = { row1, row3, col1 } is a solution, then S' = { row2, col2, col3 } is also a solution.

So all you need to do is find one solution, then exploit the symmetry. Since you only need to find one, just do the easiest thing you can think of. I would just look at column 1 and row 1 to construct the solution, then check the solution against the whole matrix. If this solution gives you more than N buttons to press for an NxN grid, then take the solution's complement and you'll end up with a smaller one.

Symmetry is a very important concept in computer science and it comes up almost everywhere. Understanding the symmetries of this problem is what allows you to solve it without checking every possible solution.

P.S. You say this code is C++, but it is also perfectly valid C if you remove #include <iostream> from the top. It might take a lot less time to compile if you compile it as C.