BakerHub

# A. Count Operations to Obtain Zero (opens new window)

DETAILS 
def countOperations(self, a: int, b: int) -> int:
        ans = 0
        while a > 0 and b > 0:
            if a >= b:
                a -= b
            else:
                b -= a
            ans += 1
        return ans

# B. Minimum Operations to Make the Array Alternating (opens new window)

Find the top-2 frequent numbers on odd indexes and even indexes.

DETAILS 
def minimumOperations(self, A: List[int]) -> int:
        if len(A) == 1:
            return 0
        c_e = collections.Counter([x for x in A[::2]])
        c_o = collections.Counter([x for x in A[1::2]])
        key_e = sorted(list(c_e.keys()), key = lambda x: c_e[x], reverse=True)
        key_o = sorted(list(c_o.keys()), key = lambda x: c_o[x], reverse=True)

        if key_e[0] != key_o[0]:
            return len(A) - c_e[key_e[0]] - c_o[key_o[0]]
        else:
            if len(key_e) == 1:
                if len(key_o) == 1:
                    return len(A) - max(c_e[key_e[0]], c_o[key_o[0]])
                else:
                    return len(A) - c_e[key_e[0]] - c_o[key_o[1]]
            else:
                if len(key_o) == 1:
                    return len(A) - c_e[key_e[1]] - c_o[key_o[0]]
                else:
                    res = max(c_e[key_e[0]] + c_o[key_o[1]], c_e[key_e[1]] + c_o[key_o[0]])
                    return len(A) - res

# C. Removing Minimum Number of Magic Beans (opens new window)

Sort and traverse, calculate the prefix sum and suffix sum.

DETAILS 
def minimumRemoval(self, A: List[int]) -> int:
        A.sort()
        n, suf, pre, ans = len(A), sum(A), 0, math.inf

        for i, a in enumerate(A):
            curr = pre + (suf - (n - i) * a)
            ans = min(ans, curr)
            pre += a
            suf -= a
        return ans

# D. Maximum AND Sum of Array (opens new window)

DP

DETAILS 
def maximumANDSum(self, A: List[int], num: int) -> int:
        n = len(A)
        @functools.cache
        def dfs(i, slots):
            if i == n:
                return 0
            ans = 0
            for j in range(num):
                if slots[j] > 0:
                    ans = max(ans, (A[i] & (j + 1)) + dfs(i + 1, slots[:j] + (slots[j] - 1,) + slots[j + 1:]))
            return ans
        
        return dfs(0, tuple([2] * num))

Monte-Carlo

DETAILS 
def maximumANDSum(self, A: List[int], n: int) -> int:
        ans = 0
        for i in range(4000):
            random.shuffle(A)
            cur, d = 0, defaultdict(int)
            for a in A:
                j = 0
                for i in range(1, n + 1):
                    if d[i] < 2 and a & i > a & j:
                        j = i
                d[j] += 1
                cur += a & j
            ans = max(ans, cur)
        return ans

← Weekly Contest 279 →