StORage room (Codeforces 1903B)
Tags: Greedy, bitmasks

In Cyprus, the weather is pretty hot. Thus, Theofanis saw this as an opportunity to create an ice cream company. He keeps the ice cream safe from other ice cream producers by locking it inside big storage rooms. However, he forgot the password. Luckily, the lock has a special feature for forgetful people! It gives you a table $$$M$$$ with $$$n$$$ rows and $$$n$$$ columns of non-negative integers, and to open the lock, you need to find an array $$$a$$$ of $$$n$$$ elements such that:  $$$0 \le a_i < 2^{30}$$$, and  $$$M_{i,j} = a_i | a_j$$$ for all $$$i \neq j$$$, where $$$|$$$ denotes the bitwise OR operation. The lock has a bug, and sometimes it gives tables without any solutions. In that case, the ice cream will remain frozen for the rest of eternity.Can you find an array to open the lock? 

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{3}$$$) — the size of the hidden array.The next $$$n$$$ lines describe the rows of $$$M$$$, line $$$i$$$ contains the table values $$$M_{i,1}, M_{i,2}, \ldots, M_{i,n}$$$ ($$$0 \le M_{i,j} < 2^{30}$$$).It is guaranteed that $$$M_{i,i} = 0$$$ and $$$M_{i,j} = M_{j,i}$$$ for all $$$1 \le i,j \le n$$$.It is also guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{3}$$$.

Output: For each test case, if there is a solution print YES and an array that satisfies the property, otherwise print NO.If there are multiple solutions, print any of them.You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.


Sample Inputs:
4
1
0
4
0 3 3 5
3 0 3 7
3 3 0 7
5 7 7 0
5
0 7 7 5 5
7 0 3 2 6
7 3 0 3 7
5 2 3 0 4
5 6 7 4 0
3
0 0 1
0 0 0
1 0 0

Sample Outputs:
YES
7
YES
1 3 2 5 
YES
5 2 3 0 4
NO

Solution (Python):
def find_and(arr):
    ans = arr[0]
    for i in range(1, len(arr)):
        ans = ans & arr[i]
    return ans
for _ in range(int(input())):
    n = int(input())
    mat = []
    for line in range(n):
        mat.append(list(map(int, input().split())))
    arr = []
    if n == 1:
        print('YES')
        print(mat[0][0])
        continue
    for (i, line) in enumerate(mat):
        new_line = line.copy()
        new_line.pop(i)
        arr.append(find_and(new_line))
    wrong = False
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] | arr[j] != mat[i][j]:
                print('NO')
                wrong = True
                break
        if wrong:
            break
    else:
        print('YES')
        print(*arr)

Solution (Python):
def check():
    for i in range(n - 1):
        for j in range(i + 1, n):
            if M[i][j] != r[i] | r[j]:
                print('NO')
                return
    else:
        print('YES')
        for i in r:
            print(i, end=' ')
        print()
for i in range(int(input())):
    n = int(input())
    if n == 1:
        input()
        print('YES\n0')
        continue
    M = []
    for i in range(n):
        M.append([int(i) for i in input().split()])
    r = []
    for i in range(n):
        t = M[i][0] if i != 0 else M[i][1]
        for e in M[i][1:i] + M[i][i + 1:]:
            t = t & e
        r.append(t)
    check()

Solution (Python):
for t in range(1, int(input()) + 1):
    n = int(input())
    ans = []
    flag = True
    if n == 1:
        print('YES')
        print(input())
        continue
    for i in range(n):
        arr = [int(x) for x in input().split()]
        if i == 0:
            val = arr[1]
        else:
            val = arr[0]
        for j in range(n):
            if i != j:
                val &= arr[j]
        for j in range(i):
            if arr[j] != val | ans[j]:
                flag = False
        ans.append(val)
    if not flag:
        print('NO')
    else:
        print('YES')
        print(*ans)