Chef and Pair Flips - CodeChef Solution| AskTheCode

CodeChef April Long Challenge Solution | Chef and Pair Flips (PAIRFLIP) solution | AskTheCode

---

Problem:

Chef has two matrices A and B, each with size N×M. Each cell of the matrix A contains a character '0' or '1', while each cell of the matrix B contains '?', '0' or '1'.

The matrix A can be modified using zero or more operations. In one operation, Chef can choose two cells in the matrix A which lie either in the same row or in the same column and flip the characters in each of these cells (flipping means changing '1' to '0' or '0' to '1').

Chef wants the matrix A to match the matrix B. Formally, for each row r and column c, if the cell in row r and column c of B contains '0' or '1', then he wants the cell in row r and column c of A to contain the same character; otherwise (for cells containing '?'), it may contain either '0' or '1'.

The difficulty of your task is described by a parameter E. If E=0, you should only find the smallest number of operations required to achieve this goal. If E=1, you should also find one sequence of operations with the smallest length which achieves it.

---

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

• The first line of each test case contains three space-separated integers N, M and E.

• N lines follow. For each valid i, the i-th of these lines contains a single string Ai with length M describing the i-th row of the matrix A.

• N more lines follow. For each valid i, the i-th of these lines contains a single string Bi with length M describing the i-th row of the matrix B.

---

Output:

For each test case:

• If it is not possible to make A match B, print a single line containing the integer −1.

• Otherwise, first, print a line containing a single integer K ― the smallest required number of operations.

• Then, if E=1, print K lines describing the sequence of operations you want to perform. An operation should be printed in one of the following formats:

  • R r i j to flip the characters in cells in row r and columns i and j (1≤r≤N, 1≤i,j≤M)

  • C c i j to flip the characters in cells in column c and rows i and j (1≤c≤M, 1≤i,j≤N)

If there are several possible answers, you may find any one of them.

---

Example Input:

3 3 3 1 010 101 101 100 110 ?00 2 2 0 10 01 0? ?? 1 3 1 101 010

---

Example Output:

3 C 2 1 2 C 3 2 3 C 1 3 1 1 -1

---

Explanation:

Example case 1: This is not the only solution ― a valid sequence of 3 row operations also exists.

Example case 2: We did not restore the sequence of operations because E=0.

---

Code:

/*Sorry but we don't promote cheating, and also follow rules, so, will provide the solution when the challenge will be over...*/
However, if you still want to see the code, then become our member by clicking Log In/Sign Up button present at the upper left corner of your screen, and ask us directly in message. And, you will get 100 points in this problem.