XOR Folding Codechef Solution in Python | AskTheCode

Jun 20, 20212 min read

Codechef June Cook-Off 2021 Solution | XOR Folding (XORFOLD) solution in Python | AskTheCode

Problem:

You are given a grid with size N×M. Each cell of this grid contains either 0 or 1.

We should perform the following operation until the size of the grid becomes 1×1:

Suppose the present size of the grid is x×y.
Choose one of the x−1 horizontal lines or y−1 vertical lines crossing the grid.
Fold the grid along this line. For each pair of cells which overlap after this folding, replace them by a single cell such that the value in this cell is the XOR of the values in the two overlapping cells. Thus, we obtain a new grid.

Example: If the initial grid is

000
111
010

1) After folding along 1-st horizontal line, the grid is

111
010

2) After folding along the 2-nd vertical line, the grid is

10
01

3) After folding along the 1-st horizontal line, the grid is

4) After folding along the 1-st vertical line, the grid is

Determine whether there is a sequence of folds such that in the final 1×1 grid, the only cell contains 1.

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 two space-separated integers N and M.
N lines follow. For each valid i, the i-th of these lines contains a single binary string Si with length M describing the i-th row of the grid.

Output:

Print a single line containing the string "YES" if it is possible to obtain 1 in the final 1×1

grid or "NO" if it is impossible (without quotes).

You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

Sample Input:

Sample Output:

YES
NO

EXPLANATION:

Example case 1: There is only 1 possible move, which is to fold along the only vertical line. The resulting grid contains only 1.

Example case 2: There is no sequence of moves which would result in a 1×1 grid containing only 1.

Code:

import sys

test = int(sys.stdin.readline().strip())
for i in range(test):
    n, m = list(map(int, sys.stdin.readline().split()))
    ans = 0
    for i in range(n):
        a = list(sys.stdin.readline().strip())
        len_a = len(a)
        for i in range(len_a):
            ans ^= int(a[i])
    if ans == 0:
        print("NO")
    else:
        print("YES")

XOR Folding Codechef Solution in Python | AskTheCode

Recent Posts

Comments