A. Check if Matrix Is X-Matrix (opens new window)

Check every cell, if a cell doesn't meet the rule, return False, if all the cells meet the conditions, return True.

DETAILS

def checkXMatrix(self, A: List[List[int]]) -> bool:
        n = len(A)
        for i in range(n):
            for j in range(n):
                if (i == j or i + j == n - 1) and A[i][j] == 0:
                    return False
                if i != j and i + j != n - 1 and A[i][j]:
                    return False
        return True

B. Count Number of Ways to Place Houses (opens new window)

The two sides are independent, thus we just need to find the number of ways N to fill one side without adjacent houses, and the answer equals the square of N.

DETAILS

def countHousePlacements(self, n: int) -> int:
        mod = 10 ** 9 + 7
        house, empty = 1, 1
        for i in range(n - 1):
            house, empty = empty, house + empty
            house %= mod
            empty %= mod
        return pow((house + empty), 2, mod)

C. Maximum Score Of Spliced Array (opens new window)

Kadane Algorithm

DETAILS

def maximumsSplicedArray(self, A, B):
        n = len(A)
        def solve(A, B):
            ans = cur = 0
            for i in range(n):
                cur = max(0, cur + A[i] - B[i])
                ans = max(ans, cur)
            return ans + sum(B)
        return max(solve(A, B), solve(B, A))

D. Minimum Score After Removals on a Tree (opens new window)

Please refer to This LC Discussion (opens new window) for my solutions in English.

BFS

DETAILS

def minimumScore(self, N: List[int], E: List[List[int]]) -> int:
        n, m = len(N), len(E)
        
        G = collections.defaultdict(list)  # Graph
        C = collections.defaultdict(set)   # Children
        A = N[:]                  # subtree XOR value
        degree = [0] * n        # degree of each node 

        for x, y in E:
            G[x].append(y)
            G[y].append(x)
            degree[x] += 1
            degree[y] += 1
        
        V = 0   # XOR of all the nodes
        
        seen = set()
        dq = collections.deque()
        for i in range(n):
            V ^= N[i]
            if degree[i] == 1:
                dq.append(i)
                seen.add(i)
                
        # BFS, starting from the leaf nodes     
        while dq:
            cur = dq.popleft()
            for nxt in G[cur]:
                if nxt not in seen:
                    C[nxt].add(cur)
                    C[nxt] |= C[cur]
                    A[nxt] ^= A[cur]
                degree[nxt] -= 1
                if degree[nxt] == 1:
                    seen.add(nxt)
                    dq.append(nxt)
        ans = math.inf
        for i in range(m - 1):
            for j in range(i + 1, m):
                # Let a, c be the lower break points
                a, b = E[i]
                if b in C[a]: a, b = b, a 
                
                c, d = E[j]
                if d in C[c]: c, d = d, c
                
                # 3 cases: a is c's child, c is a's child, or a and b are two independent subtrees.
                if c in C[a]:
                    cur = [A[c], A[a]^A[c], V^A[a]]
                elif a in C[c]:
                    cur = [A[a], A[c]^A[a], V^A[c]]
                else:
                    cur = [A[a], A[c], V^A[a]^A[c]]
                ans = min(ans, max(cur) - min(cur))
            
        return ans