Practice #019: Leetcode Weekly Contest 299

Leetcode: 2319. Check if Matrix Is X-Matrix

Problem Statement 

from typing import List


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


assert (
    Solution().checkXMatrix([[2, 0, 0, 1], [0, 3, 1, 0], [0, 5, 2, 0], [4, 0, 0, 2]])
    == True
)
assert Solution().checkXMatrix([[5, 7, 0], [0, 3, 1], [0, 5, 0]]) == False

Leetcode: 2320. Count Number of Ways to Place Houses

Problem Statement

The following Dynamic Programming can be reduced to computing the Fibonacci Numbers. 

class Solution:
    def countHousePlacements(self, n: int) -> int:
        M = 10**9 + 7
        f = [[0, 0] for _ in range(n + 1)]
        f[1][0] = 1
        f[1][1] = 1
        for i in range(2, n + 1):
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % M
            f[i][1] = f[i - 1][0]
        return ((sum(f[n]) % M) ** 2) % M


assert Solution().countHousePlacements(1) == 4
assert Solution().countHousePlacements(2) == 9

Leetcode: 2321. Maximum Score Of Spliced Array

Problem Statement

Can we simplify the problem while keeping it the same? We can solve the problem of swapping a subsequence of \(a\) by one in \(b\) and the other way around, since they contribute independently to the final answer. For each problem, we can compute \(f(i)\) which is the maximum value that we can get by either starting swapping on \(i\) or using the original values. On the end, we have to combine \(f(i)+a[0]+a[1]+...+a[i-1]\) to solve the original problem. Time and space complexity is \(O(n)\) 

from functools import cache

class Solution:
    def maximumsSplicedArray(self, a: List[int], b: List[int]) -> int:
        n = len(a)
        pa = [0]
        pb = [0]
        for i in range(0, n):
            pa.append(pa[-1] + a[i])
            pb.append(pb[-1] + b[i])

        ans = 0
        sa  = 0
        sb  = 0
        dpa = 0
        dpb = 0
        for i in range(n - 1, -1, -1):
            sa += a[i]
            sb += b[i]
            dpa = max(dpa + b[i], sa)
            dpb = max(dpb + a[i], sb)
            ans = max(
                ans,
                pa[i] + dpa,
                pb[i] + dpb
            )

        return ans6

Leetcode: 2322. Minimum Score After Removals on a Tree

Problem Statement

How can we find the solution knowing part of it? Suppose that we know one of the edges \((u, v)\) in the final solution where \(u\) is parent of \(v\) in the given tree. We can use a Depth-first search to traverse the tree and try to remove one of the other edges \((p, q)\) where \(p\) is parent of \(q\). Knowing the XOR of all values and XOR of subtrees with root on \(v\) and \(q\), we can derive XOR of \(p\) since \(a \oplus b = c\), \(a \oplus c = b\) and \(b \oplus c = a\). Time complexity is \(O(n^2)\) and space is \(O(n)\). 

from typing import List
from collections import defaultdict


class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        N = len(nums)

        A = defaultdict(lambda: list())
        for u, v in edges:
            A[u].append(v)
            A[v].append(u)

        X = [0] * N
        P = [None] * N

        def compute_xor_parent(parent, u):
            X[u] = nums[u]
            for v in A[u]:
                if v != parent:
                    P[v] = u
                    X[u] = X[u] ^ compute_xor_parent(u, v)
            return X[u]

        T = compute_xor_parent(None, 0)

        def dfs(parent, u, a):
            xor = nums[u]
            ans = float("inf")
            for v in A[u]:
                if v != parent:
                    b, cur = dfs(u, v, a)
                    c = T ^ a ^ b
                    ans = min(ans, max(a, b, c) - min(a, b, c), cur)
                    xor = xor ^ b
            return (xor, ans)

        ans = float("inf")
        for u, v in edges:
            if P[u] == v:
                u, v = v, u

            _, cur = dfs(v, u, X[v])
            ans = min(ans, cur)

        return ans


assert Solution().minimumScore([1, 5, 5, 4, 11], [[0, 1], [1, 2], [1, 3], [3, 4]]) == 9
assert (
    Solution().minimumScore(
        [5, 5, 2, 4, 4, 2], [[0, 1], [1, 2], [5, 2], [4, 3], [1, 3]]
    )
    == 0
)