GAPFILL - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

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 :slight_smile:

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.

      • 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))

  • Case 3 : Both sides odd.

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

    • OP4 : Flip whole grid
    • OP5 : Flip any two rows while keeping 1 same column element unchanged in both
    Try to represent OP1 using OP4 & OP5. Also try to represent OP4 using OP1 & similarly OP5 using OP1. As before each row should've even number of 1s as OP5 can't change parity. Similarly another decomposition of OP1 is using following 2 moves :
    • OP4 : Flip whole grid
    • OP6 : Flip any two columns while keeping 1 same row element unchanged in both.
    So by this, all columns too should've even number of ones. As grid flip is also allowed, so it suffices if each row and each column has same parity. This is infact an if and only if condition, convince yourself. Counting number of configurations where each row and each column has same parity is not so easy. Here is a combinatorial solution : Take N-1 * M-1 subgrid leaving last row and last column. Fill up this grid arbitrarily. Further suppose we wish to make parity of each row or column odd. So for each column if parity is even put 1 in last row of same column else keep it zero. Do same for rows. By now parity of last row and last column is same. If its even put 1 at (N,M) the cell else let it stay 0. So number of configurations which have odd parity in all rows and columns is 2 ^ ( ( N-1) * (M-1) ). As even parity case is similar (bijection being flipping of the grid), total number of solvable configurations are 2 * ( 2 ^( (N-1) * (M-1) ) )

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.