BakerHub

# A. Number of Arithmetic Triplets (opens new window)

Brute Force, focus on the largest number a, check if a - diff and a - diff * 2 all exist in the array.

DETAILS 
def arithmeticTriplets(self, A: List[int], diff: int) -> int:
        ans = 0
        for a in A:
            if a >= 2 * diff:
                ans += (a - diff in A) and (a - diff * 2 in A)
        return ans

# B. Reachable Nodes With Restrictions (opens new window)

BFS, record the number of visited nodes.

DETAILS 
def reachableNodes(self, n: int, E: List[List[int]], R: List[int]) -> int:
        ans = 0
        dq = collections.deque([0])
        
        R = set(R)
        G = collections.defaultdict(set)
        for a, b in E:
            G[a].add(b)
            G[b].add(a)
        seen = set([0])
        
        
        while dq:
            cur = dq.popleft()
            ans += 1
            for nxt in G[cur]:
                if nxt not in R and nxt not in seen:
                    seen.add(nxt)
                    dq.append(nxt)
        
        return ans

# C. Check if There is a Valid Partition For The Array (opens new window)

DP.

DETAILS 
def validPartition(self, A: List[int]) -> bool:
        n, dp = len(A), [False] * 3 + [True]
        for i in range(n):
            dp[i % 4] = False
            if i - 1 >= 0 and A[i] == A[i - 1]:
                dp[i % 4] |= dp[(i - 2) % 4]
            if i - 2 >= 0 and A[i] == A[i - 1] == A[i - 2]:
                dp[i % 4] |= dp[(i - 3) % 4]
            if i - 2 >= 0 and A[i] == A[i - 1] + 1 == A[i - 2] + 2:
                dp[i % 4] |= dp[(i - 3) % 4]
        return dp[(n - 1) % 4]

# D. Longest Ideal Subsequence (opens new window)

DP. For each letter ch, let's focus on its possible previous character prev. Apparently the distance between prev and ch must be no larger than k. Iterate over all such prev characters and get their longest subsequence pos[prev], then the longest subsequence ends by ch is 1 longer than the longest subsequence, that is pos[prev] + 1.

DETAILS 
def longestIdealString(self, s: str, k: int) -> int:
        pos = [0] * 26
        
        for ch in s:
            i = ord(ch) - ord('a')
            tmp = pos[i]
            for nxt in range(i - k, i + k + 1):
                if nxt >= 0 and nxt < 26:
                    tmp = max(tmp, pos[nxt] + 1)
            pos[i] = tmp
            
        return max(pos)

← Weekly Contest 304 →