### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

This was the first problem I wrote for Codechef and I’m glad so many people could solve it. I hope it was fun solving it

As I understand, many people tried to find the pattern and did some guess work. Here I provide a fully combinatorial solution to the problem. I wont be surprised if a shorter (& smarter) solution exists.

Call OP1(i,j) the operation given in problem statement applied at cell(i,j). Trick to solve this problem is to be able to break OP1 in simpler operations with same power.

Before counting number of solvable configurations, we need to first characterise solvable configurations. Lets try to look at different cases:

- Case 1 : Both sides even
- This is the easiest of all the cases. By a smart sequence of moves( shown below), we can toggle any given cell without changing any of the other cells. By this we can solve any initial configuration of the board. Hence in case when N & M are both even answer is 2^(N*M).
- If you want to toggle cell (i,j) : Press switch in all those cells which are in same row or column as that of(i,j). Note (i,j) is to be pressed exactly once. This results only cell(i,j) getting flipped.
- Case 2 : 1 side even, 1 side odd. Without loss of generality assume number of rows is even and number of columns is odd. This case is tougher to analyze as all configurations are not solvable. However one can represent OP1 as a sequence of moves of following two operations:
- OP2 : Flip one whole column
- OP3 : Flip any row keeping any one element of this row unchanged.
- Case 3 : Both sides odd.
- OP4 : Flip whole grid
- OP5 : Flip any two rows while keeping 1 same column element unchanged in both
- OP4 : Flip whole grid
- OP6 : Flip any two columns while keeping 1 same row element unchanged in both.

Also both OP2 & OP3 can be created by sequence of moves of OP1(Find that, as homework ;-] ). Hence a board is solvable by OP1 move iff its solvable by OP2 & OP3 moves. Now take a solvable configuration and list the sequence of OP2 & OP3 moves that solve it. No operation as before is repeated on same location. Hence all moves are independent & we can change their order. Bring all OP2 moves before before all OP3 moves. When all OP2 moves have ended look at grid. As OP3 operation can’t change parity of ones in any row so each row much have an even number of 1s already. Now flip each row exactly as many times as there are 1s in it with not flipping those cells which have a 1 in them at this stage. All 1s get flipped odd times ( total 1s (even) - 1(for ownself) ). Also all 0s get flipped even times hence whole row is 0.

So now what could’ve happened in column phase ? A single column flips parity of all rows so all rows should’ve started with same parity. Convince yourself that this is in fact an if and only if condition. So only those configurations are solvable that have same parity in all rows. Counting it is not so tough. There are two choices for parity of first row : odd or even. Here is a combinatorial way of counting the same. Fill up first N-1 cells of first row arbitrarily. If parity of these N-1 match option chosen before keep Nth cell blank else put 1 in it. So number of ways of making a row have even(or odd) parity is 2^(N-1). As all rows have same parity, so for all rows number of ways of getting odd (or even) parity is : 2^( (N-1) * M). And as we have option of choosing even or odd : final answer is 2 * (2^ ((N-1) *M))

As before one can represnt OP1 as sequence of moves of two operations :

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.