A. Count Hills and Valleys in an Array (opens new window)

Iteration and compare.

DETAILS

def countHillValley(self, A: List[int]) -> int:
        ans, n = 0, len(A)
        for i in range(1, n - 1):
            if A[i] == A[i+1]:
                A[i] = A[i-1]
            ans += int(A[i - 1] > A[i] < A[i + 1] or A[i - 1] < A[i] > A[i + 1])
        return ans  

Use itertools.groupby

DETAILS

def countHillValley(self, A: List[int]) -> int:
        A = [k for k, g in itertools.groupby(A)]
        ans, n = 0, len(A)
        for i in range(1, n - 1):
            ans += int(A[i - 1] < A[i] > A[i + 1] or A[i - 1] > A[i] < A[i + 1])
        return ans

B. Count Collisions on a Road (opens new window)

We just need to count how many cars collide finally. All the L cars from left part and R car from right part will not collide (for example: LLL......RRR), while all the rest cars beside S collide finally.

DETAILS

def countCollisions(self, S: str) -> int:
        ans, n = len(S), len(S)
        i, j = 0, n - 1
        while i < n and S[i] == "L":
            i += 1
            ans -= 1
        while j >= 0 and S[j] == "R":
            j -= 1
            ans -= 1
        return ans - collections.Counter(S).get("S", 0)

C. Maximum Points in an Archery Competition (opens new window)

Bitmask.

There are 12 sections, so the number of winning states for Alice is 2 ** 12 ~ 5000, thus its okay to iteration over all states. We use binary string of length 12 to represent each state.

For each state, check if its possible, and calculate the score of Alice if so.

DETAILS

def maximumBobPoints(self, n: int, A: List[int]) -> List[int]:
        ans, anss = 0, -1
        
        def helper(s):
            tmp, curr, res = bin(s)[2:], 0, n
            tmp = "0" * (12 - len(tmp)) + tmp
            for i, ch in enumerate(tmp):
                if ch == "1":
                    a = A[i]
                    if res < a + 1:
                        return -1
                    else:
                        res -= (a + 1)
                        curr += i
            return curr
        
        for i in range(1 << 12):
            if helper(i) >= ans:
                ans, anss = helper(i), i

        k, ans, tmp = -1, [0] * 12, bin(anss)[2:]
        tmp = "0" * (12 - len(tmp)) + tmp

        for i, ch in enumerate(tmp):
            if ch == "1":
                k = i
                ans[i] = A[i] + 1
        res = n - sum(ans)
        ans[k] += res
        
        return ans

D. Longest Substring of One Repeating Character (opens new window)

Segment Tree.

DETAILS