Grid Xor (Codeforces 1628C)
Tags: Greedy, interactive

Note: The XOR-sum of set $$$\{s_1,s_2,\ldots,s_m\}$$$ is defined as $$$s_1 \oplus s_2 \oplus \ldots \oplus s_m$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.After almost winning IOI, Victor bought himself an $$$n\times n$$$ grid containing integers in each cell. $$$n$$$ is an even integer. The integer in the cell in the $$$i$$$-th row and $$$j$$$-th column is $$$a_{i,j}$$$.Sadly, Mihai stole the grid from Victor and told him he would return it with only one condition: Victor has to tell Mihai the XOR-sum of all the integers in the whole grid.Victor doesn't remember all the elements of the grid, but he remembers some information about it: For each cell, Victor remembers the XOR-sum of all its neighboring cells.Two cells are considered neighbors if they share an edge — in other words, for some integers $$$1 \le i, j, k, l \le n$$$, the cell in the $$$i$$$-th row and $$$j$$$-th column is a neighbor of the cell in the $$$k$$$-th row and $$$l$$$-th column if $$$|i - k| = 1$$$ and $$$j = l$$$, or if $$$i = k$$$ and $$$|j - l| = 1$$$.To get his grid back, Victor is asking you for your help. Can you use the information Victor remembers to find the XOR-sum of the whole grid?It can be proven that the answer is unique.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single even integer $$$n$$$ ($$$2 \leq n \leq 1000$$$) — the size of the grid.Then follows $$$n$$$ lines, each containing $$$n$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th of these lines represents the XOR-sum of the integers in all the neighbors of the cell in the $$$i$$$-th row and $$$j$$$-th column.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$1000$$$ and in the original grid $$$0 \leq a_{i, j} \leq 2^{30} - 1$$$.Hack FormatTo hack a solution, use the following format:The first line should contain a single integer t ($$$1 \le t \le 100$$$) — the number of test cases.The first line of each test case should contain a single even integer $$$n$$$ ($$$2 \leq n \leq 1000$$$) — the size of the grid.Then $$$n$$$ lines should follow, each containing $$$n$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th of these lines is $$$a_{i,j}$$$ in Victor's original grid. The values in the grid should be integers in the range $$$[0, 2^{30}-1]$$$The sum of $$$n$$$ over all test cases must not exceed $$$1000$$$.

Output: For each test case, output a single integer — the XOR-sum of the whole grid.

Note: For the first test case, one possibility for Victor's original grid is:$$$1$$$$$$3$$$$$$2$$$$$$4$$$For the second test case, one possibility for Victor's original grid is:$$$3$$$$$$8$$$$$$8$$$$$$5$$$$$$9$$$$$$5$$$$$$5$$$$$$1$$$$$$5$$$$$$5$$$$$$9$$$$$$9$$$$$$8$$$$$$4$$$$$$2$$$$$$9$$$For the third test case, one possibility for Victor's original grid is:$$$4$$$$$$3$$$$$$2$$$$$$1$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$$$$8$$$$$$9$$$$$$9$$$$$$1$$$

Sample Inputs:
3
2
1 5
5 1
4
1 14 8 9
3 1 5 9
4 13 11 1
1 15 4 11
4
2 4 1 6
3 7 3 10
15 9 4 2
12 7 15 1

Sample Outputs:
4
9
5

Solution (Python):
import io
import os
FILE_INPUT_MODE = -1
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve(n, a):
    ans = 0
    di = ((0, 1), (1, 0), (0, -1), (-1, 0))
    for cycle in range(0, n // 2, 2):
        (u, v) = (cycle, cycle)
        cnt = 0
        for i in range(4):
            for j in range(n - cycle * 2 - 1):
                if cnt % 4 <= 1:
                    ans ^= a[u][v]
                u += di[i][0]
                v += di[i][1]
                cnt += 1
    return ans

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = []
        for _ in range(n):
            a.append([int(word) for word in input().strip().split()])
        print(solve(n, a))
if __name__ == '__main__':
    main()

Solution (Python):
def query():
    n = int(input())
    b = [[-1] * n for i in range(n)]
    hx = [-1, 1, 0, 0]
    hy = [0, 0, -1, 1]

    def fill(sz, px, py, cr):
        if sz == 2:
            b[px][py] = cr
            b[px][py + 1] = cr
            b[px + 1][py] = 1 - cr
            b[px + 1][py + 1] = 1 - cr
            return
        if sz == 4:
            b[px][py] = cr
            b[px][py + 1] = cr
            b[px][py + 2] = cr
            b[px][py + 3] = cr
            b[px + 1][py] = 1 - cr
            b[px + 1][py + 1] = cr
            b[px + 1][py + 2] = cr
            b[px + 1][py + 3] = 1 - cr
            b[px + 2][py] = cr
            b[px + 2][py + 1] = cr
            b[px + 2][py + 2] = cr
            b[px + 2][py + 3] = cr
            b[px + 3][py] = 1 - cr
            b[px + 3][py + 1] = 1 - cr
            b[px + 3][py + 2] = 1 - cr
            b[px + 3][py + 3] = 1 - cr
            return
        for i in range(1, sz - 1):
            b[px + 1][py + i] = cr
        for i in range(1, sz - 1):
            b[px + i][py + 1] = cr
        for i in range(1, sz - 1):
            b[px + sz - 2][py + i] = cr
        for i in range(1, sz - 1):
            b[px + i][py + sz - 2] = cr
        for i in range(sz):
            b[px][py + i] = cr
        for i in range(sz):
            b[px + sz - 1][py + i] = 1 - cr
        for i in range(sz):
            b[px + i][py] = (cr + i) % 2
        for i in range(sz):
            b[px + i][py + sz - 1] = (cr + i) % 2
        fill(sz - 4, px + 2, py + 2, 1 - cr)
    fill(n, 0, 0, 1)
    a = []
    for i in range(n):
        a.append(list(map(int, input().split())))
    res = 0
    for i in range(n):
        for j in range(n):
            if b[i][j] == 1:
                res ^= a[i][j]
    print(res)
t = int(input())
for i in range(t):
    query()

Solution (Python):
import sys

def check(n):
    a = [[1] * n for i in range(n)]
    for i in range(n):
        print(''.join(map(str, a[i])))
    print('====')
    for i in range(1, n):
        for j in range(n):
            if a[i - 1][j]:
                a[i - 1][j] ^= 1
                if j > 0:
                    a[i][j - 1] ^= 1
                if j + 1 < n:
                    a[i][j + 1] ^= 1
                if i + 1 < n:
                    a[i + 1][j] ^= 1
        for i in range(n):
            print(''.join(map(str, a[i])))
        print('====')
    for i in range(n):
        print(''.join(map(str, a[i])))

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    b = [[1] * n for i in range(n)]
    a = [list(map(int, inp().split())) for i in range(n)]
    res = 0
    for i in range(1, n):
        for j in range(n):
            if b[i - 1][j]:
                b[i - 1][j] ^= 1
                res ^= a[i][j]
                if j > 0:
                    b[i][j - 1] ^= 1
                if j + 1 < n:
                    b[i][j + 1] ^= 1
                if i + 1 < n:
                    b[i + 1][j] ^= 1
    print(res)

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()