Matrix Cascade (Codeforces 1864D)
Tags: Math, data structures

There is a matrix of size $$$n \times n$$$ which consists of 0s and 1s. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. The cell at the intersection of the $$$x$$$-th row and the $$$y$$$-th column is denoted as $$$(x, y)$$$.AquaMoon wants to turn all elements of the matrix to 0s. In one step she can perform the following operation:  Select an arbitrary cell, let it be $$$(i, j)$$$, then invert the element in $$$(i, j)$$$ and also invert all elements in cells $$$(x, y)$$$ for $$$x > i$$$ and $$$x - i \ge \left|y - j\right|$$$. To invert a value means to change it to the opposite: 0 changes to 1, 1 changes to 0. Help AquaMoon determine the minimum number of steps she need to perform to turn all elements of the matrix to 0s. We can show that an answer always exists.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 3000$$$).The $$$i$$$-th of the following $$$n$$$ lines contains a binary string only of characters 0 and 1, of length $$$n$$$.It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$9\,000\,000$$$.

Output: For each test case, print the minimum number of steps.

Note: In the first test case, we can use the following scheme:  perform the operation on the cell $$$(1, 3)$$$. Clearly, the elements of the initial matrix are not all 0, so at least one operation is required. Thus, $$$1$$$ is the answer.In the second test case, we use the following scheme:  perform the operation on the cell $$$(3, 3)$$$;  perform the operation on the cell $$$(1, 1)$$$. It can be shown that there is no way to convert all elements to 0s in $$$0$$$ or $$$1$$$ steps, so the answer is exactly $$$2$$$.

Sample Inputs:
3
5
00100
01110
11111
11111
11111
3
100
110
110
6
010101
111101
011110
000000
111010
001110

Sample Outputs:
1
2
15

Solution (Python):
""""""

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        d1 = [0] * (2 * n)
        d2 = [0] * (2 * n + 1)
        ans = 0
        for i in range(n):
            s = input()
            x = 0
            for j in range(-i, 0):
                x ^= d1[i + j]
            for j in range(n):
                x = x ^ d1[i + j] ^ d2[n + i - j]
                v = s[j] - ord('0')
                if x ^ v == 1:
                    ans += 1
                    d1[i + j] ^= 1
                    d2[n + i - (j + 1)] ^= 1
                    x ^= 1
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
""""""

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        grid = [[0 for __ in range(n)] for ___ in range(n)]
        for i in range(n):
            s = input()
            for j in range(n):
                grid[i][j] = s[j] - ord('0')
        d2 = [0] * (2 * n)
        ans = 0
        for J in range(2 * n):
            (i, j) = (0, J)
            while j >= n:
                i += 1
                j -= 1
            flips = 0
            d_i = 0
            while i < n and j >= 0:
                while d_i <= i - j + n:
                    flips += d2[d_i]
                    d_i += 1
                if (flips + grid[i][j]) % 2 == 1:
                    d2[i - j + n] += 1
                    flips += 1
                    ans += 1
                i += 1
                j -= 1
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
    n = int(input())
    grid = []
    for i in range(n):
        s = input().decode('utf-8')[:n]
        grid.append(s)
    ans = 0
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    accudp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for j in range(n):
        if grid[0][j] == '1':
            dp[0][j] = 1
            accudp[0][j] = 1
            ans += 1
    for i in range(1, n):
        for j in range(n):
            if j == 0:
                curr = accudp[i - 1][j + 1] + dp[i - 1][j]
            elif j == n - 1:
                curr = accudp[i - 1][j - 1] + dp[i - 1][j]
            else:
                curr = accudp[i - 1][j - 1] + accudp[i - 1][j + 1] - accudp[i - 2][j] + dp[i - 1][j]
            accudp[i][j] = curr
            if grid[i][j] == '1' and curr % 2 == 1:
                continue
            if grid[i][j] == '0' and curr % 2 == 0:
                continue
            dp[i][j] = 1
            accudp[i][j] += 1
            ans += 1
    print(ans)
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1