Grid Xor (Codeforces 1629E)
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):
def nxt(curr, dir):
    (x, y) = curr
    if dir == 'u':
        return (x, y - 1)
    if dir == 'd':
        return (x, y + 1)
    if dir == 'l':
        return (x - 1, y)
    if dir == 'r':
        return (x + 1, y)
for _ in range(int(input())):
    n = int(input())
    mat = [(*map(int, input().split()),) for i in range(n)]
    l = 0
    r = n - 1
    ans = 0
    f = 0
    while True:
        curr = (l, l)
        for dir in ('r', 'd', 'l', 'u'):
            for i in range(r - l):
                if f < 2:
                    (x, y) = curr
                    ans ^= mat[x][y]
                f = (f + 1) % 4
                curr = nxt(curr, dir)
        l += 2
        r -= 2
        if l >= r:
            break
    print(ans)

Solution (Python):
n = 0
a = []

def calc():
    res = 0
    for i in range(0, n, 4):
        j = 0
        while i - j >= 0:
            res ^= a[i - j][j]
            j += 2
    for i in range(n - 3, 0, -4):
        j = 0
        while i + j < n:
            res ^= a[i + j][n - 1 - j]
            j += 2
    return res
t = int(input())
for _ in range(t):
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    ans = calc()
    for i in range(n // 2):
        for j in range(n // 2):
            (a[i][j], a[j][n - 1 - i], a[n - 1 - i][n - 1 - j], a[n - 1 - j][i]) = (a[j][n - 1 - i], a[n - 1 - i][n - 1 - j], a[n - 1 - j][i], a[i][j])
    ans ^= calc()
    print(ans)

Solution (Python):
""""""

def solve(n, grid):
    rg = [[0] * (n + 2) for _ in range(n + 2)]
    res = 0
    for i in range(1, n):
        for j in range(n):
            rg[i + 1][j + 1] = rg[i][j] ^ rg[i - 1][j + 1] ^ rg[i][j + 2] ^ grid[i - 1][j]
            res ^= rg[i + 1][j + 1]
    return res

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