BakerHub

# A. Count Vowel Substrings of a String (opens new window)

Brute Force.

DETAILS 
def countVowelSubstrings(self, A: str) -> int:
        n = len(A)
        ans = 0
        s = set(["a", "e", "i", "o", "u"])
        for i in range(n - 4):
            for j in range(i + 5, n + 1):
                c = collections.Counter(A[i : j])
                if s == set(c.keys()):
                    ans += 1
        return ans

# B. Vowels of All Substrings (opens new window)

Get the accumulative total from all prefix sums.

DETAILS 
def countVowels(self, A: str) -> int:
        ans, n = 0, len(A)
        prev = ans = int(A[0] in "aeiou")
        for i in range(1, n):
            if A[i] in "aeiou":
                prev += i + 1
            ans += prev  
        return ans

# C. Minimized Maximum of Products Distributed to Any Store (opens new window)

Binary Search.

DETAILS 
def minimizedMaximum(self, n: int, A: List[int]) -> int:
        left, right = 1, max(A)
        while left < right:
            num = 0
            mid = (left + right) // 2
            for a in A:
                num += math.ceil(a / mid)
            if num > n:
                left = mid + 1
            else:
                right = mid
                
        return left

# D. Maximum Path Quality of a Graph (opens new window)

DFS

DETAILS 
def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        graph = collections.defaultdict(list)
        for a, b, c in edges:
            graph[a].append([b, c])
            graph[b].append([a, c])
        self.ans = 0
        def dfs(node, visited, gain, cost):
            if node == 0:
                self.ans = max(self.ans, gain)
            for nxt, c in graph[node]:
                if c <= cost:
                    k = int(nxt not in visited)
                    dfs(nxt, visited | set([nxt]), gain + k * values[nxt], cost - c)
        dfs(0, set([0]), values[0], maxTime)
        return self.ans

← Biweekly Contest 90 →