Construct Matrix (Codeforces 1917E)
Tags: Math, constructive algorithms

You are given an even integer $$$n$$$ and an integer $$$k$$$. Your task is to construct a matrix of size $$$n \times n$$$ consisting of numbers $$$0$$$ and $$$1$$$ in such a way that the following conditions are true, or report that it is impossible:  the sum of all the numbers in the matrix is exactly $$$k$$$;  the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is the same for each $$$i$$$;  the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is the same for each $$$j$$$. 

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 130$$$) — the number of test cases. The description of the test cases follows.Each test case is described by a single line, which contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 1000$$$, $$$n$$$ is even, $$$0 \leq k \leq n^2$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output: For each test case, output $$$\texttt{Yes}$$$ if it's possible to construct a matrix that satisfies all of the problem's conditions, and $$$\texttt{No}$$$ otherwise.If it is possible to construct a matrix, the $$$i$$$-th of the next $$$n$$$ lines should contain $$$n$$$ integers representing the elements in the $$$i$$$-th row of the matrix.

Note: In the first example, all conditions are satisfied:   the sum of all the numbers in the matrix is exactly $$$0$$$;  the bitwise $$$\texttt{XOR}$$$ of all the numbers in the row $$$i$$$ is $$$0$$$ for each $$$i$$$;  the bitwise $$$\texttt{XOR}$$$ of all the numbers in the column $$$j$$$ is $$$0$$$ for each $$$j$$$. In the third example, it can be shown that it's impossible to find a matrix satisfying all the problem's conditions.

Sample Inputs:
5
4 0
6 6
6 5
4 2
6 36

Sample Outputs:
Yes
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Yes
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
No
No
Yes
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

Solution (Python):
def shest(x1, x2, k1):
    m = []
    kr = 0
    if (k1 - 6) % (n * 2) != 0:
        kr = 2
    rowcount = n - 4 - (k1 - 6) // (n * 2) * 2 - kr
    m.append([' '.join([x1, x1, x2] + [x2] * (n - 3))])
    m.append([' '.join([x1, x2, x1] + [x2] * (n - 3))])
    m.append([' '.join([x2, x1, x1] + [x2] * (n - 3))])
    m.append([' '.join([x2] * n)])
    if rowcount != 0:
        m.append([' '.join([x2] * n) for xx in range(rowcount)])
    if (k1 - 6) // (n * 2) > 0:
        m.append([' '.join([x1] * n) for x in range((k1 - 6) // (n * 2) * 2)])
    if (k1 - 6) % (n * 2) > 0:
        m.append([' '.join([x1] * ((k1 - 6) % (n * 2) // 2)) + ' ' + ' '.join([x2] * (n - (k1 - 6) % (n * 2) // 2)) for x in range(2)])
    return sum(m, [])

def kvadrat(x1, x2, k1):
    m1 = []
    kr1 = 0
    if k1 % (n * 2) != 0:
        kr1 = 2
    rowcount1 = n - k1 // (n * 2) * 2 - kr1
    if rowcount1 != 0:
        m1.append([' '.join([x2] * n) for xx in range(rowcount1)])
    if k1 // (n * 2) > 0:
        m1.append([' '.join([x1] * n) for x in range(k1 // (n * 2) * 2)])
    if k1 % (n * 2) > 0:
        m1.append([' '.join([x1] * (k1 % (n * 2) // 2)) + ' ' + ' '.join([x2] * (n - k1 % (n * 2) // 2)) for x in range(2)])
    return sum(m1, [])
for _ in range(int(input())):
    (n, k) = list(map(int, input().split()))
    res = []
    if n == 2:
        if k == 0:
            print('Yes')
            print('0 0', '0 0', sep='\n')
            continue
        if k == 2:
            print('Yes')
            print('0 1', '1 0', sep='\n')
            continue
        if k == 4:
            print('Yes')
            print('1 1', '1 1', sep='\n')
            continue
        else:
            print('No')
            continue
    if k % 4 == 0:
        if k <= n ** 2 // 2:
            print('Yes')
            print(*kvadrat('1', '0', k), sep='\n')
        elif k > n ** 2 // 2:
            print('Yes')
            print(*kvadrat('0', '1', n ** 2 - k), sep='\n')
    elif k % 2 == 0 and k != 2 and (k != n ** 2 - 2):
        if k <= n ** 2 // 2:
            print('Yes')
            print(*shest('1', '0', k), sep='\n')
        elif k > n ** 2 // 2:
            print('Yes')
            print(*shest('0', '1', n ** 2 - k), sep='\n')
    else:
        print('No')
''
''
''

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
    (n, kk) = map(int, input().split())
    if kk % 2 == 1:
        print('No')
        continue
    if kk == 2 or kk == n * n - 2:
        if n == 2:
            print('Yes')
            print('1 0')
            print('0 1')
        else:
            print('No')
        continue
    m = [[0 for k in range(n)] for j in range(n)]
    if kk % 4 == 0:
        print('Yes')
        for j in range(0, n, 2):
            for k in range(0, n, 2):
                if kk > 0:
                    m[j][k] = 1
                    m[j][k + 1] = 1
                    m[j + 1][k] = 1
                    m[j + 1][k + 1] = 1
                    kk -= 4
        for j in range(n):
            print(' '.join(map(str, m[j])))
        continue
    m[0][0] = 1
    m[0][1] = 1
    m[1][0] = 1
    m[1][2] = 1
    m[2][1] = 1
    m[2][2] = 1
    kk -= 6
    for j in range(0, n, 2):
        for k in range(0, n, 2):
            if j <= 2 and k <= 2:
                continue
            if kk > 0:
                m[j][k] = 1
                m[j][k + 1] = 1
                m[j + 1][k] = 1
                m[j + 1][k + 1] = 1
                kk -= 4
    if kk > 0:
        m[0][2] = 1
        m[0][3] = 1
        m[3][2] = 1
        m[3][3] = 1
    print('Yes')
    for j in range(n):
        print(' '.join(map(str, m[j])))

Solution (Python):
def solve(n, k):
    if k == 6:
        answer = [[0 for i in range(n)] for j in range(n)]
        answer[0][0] = 1
        answer[0][1] = 1
        answer[1][1] = 1
        answer[1][2] = 1
        answer[2][2] = 1
        answer[2][0] = 1
        return answer
    if k % 4 == 2:
        answer = [[0 for i in range(n)] for j in range(n)]
        answer[0][0] = 1
        answer[0][3] = 1
        answer[1][1] = 1
        answer[1][3] = 1
        answer[2][2] = 1
        answer[2][3] = 1
        answer[3][0] = 1
        answer[3][1] = 1
        answer[3][2] = 1
        answer[3][3] = 1
        cnt = 10
        for i in range(4, n, 2):
            for j in range(0, n, 2):
                if cnt == k:
                    return answer
                answer[i][j] = 1
                answer[i][j + 1] = 1
                answer[i + 1][j] = 1
                answer[i + 1][j + 1] = 1
                cnt += 4
        for i in range(0, 4, 2):
            for j in range(4, n, 2):
                if cnt == k:
                    return answer
                answer[i][j] = 1
                answer[i][j + 1] = 1
                answer[i + 1][j] = 1
                answer[i + 1][j + 1] = 1
                cnt += 4
        return answer
    if k % 4 == 0:
        answer = [[0 for i in range(n)] for j in range(n)]
        cnt = 0
        for i in range(0, n, 2):
            for j in range(0, n, 2):
                if cnt == k:
                    return answer
                answer[i][j] = 1
                answer[i][j + 1] = 1
                answer[i + 1][j] = 1
                answer[i + 1][j + 1] = 1
                cnt += 4
        return answer
t = int(input())
for _ in range(t):
    (n, k) = list(map(int, input().split()))
    if k % 2 == 1:
        print('No')
        continue
    if n == 2:
        print('Yes')
        if k == 0:
            print(0, 0)
            print(0, 0)
        elif k == 2:
            print(1, 0)
            print(0, 1)
        else:
            print(1, 1)
            print(1, 1)
        continue
    if k == 2 or k == n * n - 2:
        print('No')
        continue
    answer = solve(n, k)
    print('Yes')
    for i in range(n):
        print(' '.join(map(str, answer[i])))