BakerHub

# A. Divide Array Into Equal Pairs (opens new window)

Check if all the frequencies are even.

DETAILS 
def divideArray(self, A: List[int]) -> bool:
        c = collections.Counter(A)
        return all(x % 2 == 0 for x in c.values())

# B. Maximize Number of Subsequences in a String (opens new window)

Given P = AB, either add A to the front of S or add B to the back of S can reach maximum number.

DETAILS 
def maximumSubsequenceCount(self, S: str, P: str) -> int:
        tmp = ""
        for ch in S:
            if ch == P[0] or ch == P[1]:
                tmp += ch
        n = len(tmp)  
        if P[0] == P[1]:
            return ((n + 1) * n) // 2
        else:
            tmp1 = P[0] + tmp
            ans1 = 0
            pre1 = 0
            for ch in tmp1:
                if ch == P[0]:
                    pre1 += 1
                else:
                    ans1 += pre1
            tmp2 = tmp + P[1]
            ans2 = 0
            pre1 = 0
            for ch in tmp2:
                if ch == P[0]:
                    pre1 += 1
                else:
                    ans2 += pre1
            return max(ans1, ans2)

# C. Minimum Operations to Halve Array Sum (opens new window)

Priority Queue Always cut the largest number by half.

DETAILS 
def halveArray(self, A: List[int]) -> int:
        A, ans, s = [-a for a in A], 0, sum(A)/2
        heapq.heapify(A)
        
        while True:
            p = -heapq.heappop(A)
            s -= p/2
            ans += 1
            if s <= 0:
                return ans
            heapq.heappush(A, -p/2)

# D. Minimum White Tiles After Covering With Carpets (opens new window)

DP

DETAILS 
def minimumWhiteTiles(self, A: str, N: int, clen: int) -> int:        
        if N * clen >= len(A):
            return 0
        A = "0" * clen + A
        n = len(A)
        tot = A.count("1")
        
        dp = [[0] * (n + 1) for _ in range(N + 1)]
        prefix, curr = [0] * (n + 1), 0
        for i, ch in enumerate(A):
            curr += int(ch == "1")
            prefix[i + 1] = curr
        #print(prefix)
        for start in range(n - clen + 1):
            dp[1][start] = max(dp[1][start - 1], prefix[start + clen] - prefix[start])
        for i in range(1, N):
            for start in range(clen, n - clen + 1):
                dp[i + 1][start] = max(dp[i + 1][start - 1], dp[i][start - clen] + prefix[start + clen] - prefix[start])
        #print(dp)
        return tot - max(dp[-1])

← Biweekly Contest 73 →