233

Rank Score Finish Time
1452/ 12037 13 1:36:34

Maximum Ascending Subarray Sum

Idea: greedy. 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        curCount = 0
        pre = 0
        ans = 0
        for n in nums:
            if n > pre:
                curCount += n
            else:
                curCount = n
            pre = n
            ans = max(curCount, ans)
        return ans

Number of Orders in the Backlog

Idea: Match making of a limit order book

ordered HashMap (Ordered List + unordered Map)

solution during contest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        MOD = 1000000007
        buy = []
        sell = []
        buypm = {}
        sellpm = {}
        for p, m, t in orders:
            if t == 0: 
                while m > 0 and len(sell) > 0 and sell[0] <= p:
                    if sellpm[sell[0]] > m:
                        sellpm[sell[0]] -= m
                        m = 0
                    else:
                        m -= sellpm[sell[0]]
                        del sellpm[sell.pop(0)] 
                if m > 0:
                    if p not in buy:
                        insort(buy, p)
                        buypm[p] = m
                    else:
                        buypm[p] += m
                    
            else:
                while m > 0 and len(buy) > 0 and buy[-1] >= p:
                    if buypm[buy[-1]] > m:
                        buypm[buy[-1]] -= m
                        m = 0
                    else:
                        m -= buypm[buy[-1]]
                        del buypm[buy.pop()]
                if m > 0:
                    if p not in sell:
                        insort(sell, p)
                        sellpm[p] = m
                    else:
                        sellpm[p] += m
        return (sum(sellpm.values()) + sum(buypm.values())) % MOD

priority queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from heapq import *

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        MOD = 1000000007
        buy = [] # a MAX priority queue
        sell = [] # a Min pririty queue
        
        for p, m, t in orders:
            if t == 0:
                while m > 0 and len(sell) > 0 and sell[0][0] <= p:
                    if sell[0][1] > m:
                        sell[0][1] -= m
                        m = 0
                    else:
                        m -= sell[0][1]
                        heappop(sell)
                if m > 0:
                    heappush(buy, [-p, m])
            else:
                while m >0 and len(buy) > 0 and abs(buy[0][0]) >= p:
                    if buy[0][1] > m:
                        buy[0][1] -= m
                        m = 0
                    else:
                        m -= buy[0][1]
                        heappop(buy)
                if m > 0:
                    heappush(sell, [p, m])
        ans = sum([i[1] for i in buy ]) % MOD + sum(i[1] for i in sell) % MOD
        
        return ans % MOD

Maximum Value at a Given Index in a Bounded Array

Binary Search

Tip: just use the template of binary search, convert the problem to find the minimum value to make g(m) true

1
2
3
4
5
6
7
8
9
10
''' find the value to make g(m) true '''

while l < r: # pay attention to the range also!
    m = l + (r-l)//2
    if g(m): 
        r = m
    else:
        l = m + 1
        
return l # l is the answer 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 10
# [2,3,2,1,0,0,0]
# find the maximum value that fits in 
# [1,2,1]
class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        maxSum -= n 
        if maxSum == 0:
            return 1
        def countM(i, p, l):
            if p == 0:
                return 0
            left = min(i, p-1)
            right = min(l - i, p)
            return (max(p-left,0 ) + max(p-1,0))* left /2 + (p + max(p - (right-1), 0))* right / 2
                                                  
        l = 0
        r = maxSum + n  # upper exclusive bound ！！！
        
        # find the min make g(m) valid  
        # find the max countM(index, m, n) <= maxSum  <=> find the min countM(index, m, n) > maxSum , index -= 1
        
        
        while l < r:
            m = l + (r-l)//2
            if countM(index, m, n) > maxSum: 
                r = m                        #[l, m)
            else:
                l = m + 1                    #[m+1, r) countM(index, m, n) <= maxSum
        return l

Count Pairs With XOR in a Range

I didn’t figure this hard problem out in the weekly contest.

235

Rank Score Finish Time
2965 / 11443 13 00:55:58

Q4. Number of Different Subsequences GCDs

cr. DBabichev

key idea:

For a group of numbers that have the same divider, the gcd of the group cannot less than the common divider.

solution1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    # Time 19.52%
    # Space 19.86%
    # Date 20210406
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        lru_cache(None)
        def divisors(n):
            for i in range(2, int(sqrt(n) + 1)):
                if n % i == 0:
                    s = divisors(n//i)
                    return list(set(s + [i * q for q in s]))
            return list(set([1,n]))
        
        dic = defaultdict(list)
        nums = set(nums)
        for num in nums:
            divs = divisors(num)
            for div in divs:
                dic[div].append(num)
        ans = 0
        for div in dic:
            num_list = dic[div]
            s = num_list[0]
            for num in num_list:
                s = gcd(s, num)
                if s == div:
                    break
            if div == s:
                ans += 1
        return ans

solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#from collections import defualtdict
class Solution:
    # Time 97.60% m + m/2 + m/3 + ... = O(mlogm)
    # Space 66.44% o(1)
    # Date 20210406
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
        T = max(nums) + 1
        nums = set(nums)
        
        ans = 0
        for div in range(1, T):
            g = 0
            for num in range(div, T, div):
                if num in nums:
                    g = gcd(g, num)
                    if g == div:
                        break
            if g == div:
                ans += 1
                
        return ans

236

Rank Score Finish Time
3025 / 12115 13 1:09:58(3 bugs in 3)

237

Rank Score Finish Time
2950 / 11446 13 0:47:44(1 bugs in 3)

1835. Find XOR Sum of All Pairs Bitwise AND

$$
{\displaystyle C\land (A\oplus B)=(C\land A)\oplus (C\land B)}
$$

1
2
3
4
5
6
7
8
9
class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        a1 = arr1[0]
        for a in arr1[1:]:
            a1 ^= a
        a2 = arr2[0]
        for a in arr2[1:]:
            a2 ^= a
        return a1 & a2

244

Rank Score Finish Time Date Count
5191 / 12835 7 0:47:50(1 bugs in 1) 20210530 0

1880. Check if Word Equals Summation of Two Words

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isSumEqual(self, firstWord: str, secondWord: str, targetWord: str) -> bool:
        def toNum(word):
            ans = 0
            for w in word:
                #print(ord(w) - ord('a'))
                ans = ans * 10 + (ord(w) - ord('a'))
            return ans 
        #print(toNum(firstWord), toNum(secondWord), toNum(targetWord))
        return toNum(firstWord) + toNum(secondWord) == toNum(targetWord)

1881. Maximum Value after Insertion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxValue(self, n: str, x: int) -> str:
        len0 = len(n)
        if n[0] != '-':
            for idx, w in enumerate(n):
                if (ord(w) - ord('0')) * 10 + x < x * 10 + (ord(w) - ord('0')):
                    # print(n, idx, w, (ord(w) - ord('0')) * 10 + x, x * 10 + (ord(w) - ord('0')))
                    n = n[:idx] + str(x) + n[idx:]
                    break
        else:
            for idx, w in enumerate(n[1:]):
                if (ord(w) - ord('0')) * 10 + x > x * 10 + (ord(w) - ord('0')):
                    # print(n, idx, w,  (ord(w) - ord('0')) * 10 + x, x * 10 + (ord(w) - ord('0')))
                    idx = idx + 1
                    n = n[:idx] + str(x) + n[idx:]
                    break
        if len0 == len(n):
            n = n + str(x)
        return n

1882. Process Tasks Using Servers

第三题压线做出来，没算上，/(ㄒoㄒ)/~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from heapq import *

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        freeServers = []
        for idx, er in enumerate(servers):
            freeServers.append([er, idx])
            
        heapify(freeServers)
        pendingTasks = [] # time
        ans = []          # server idx
        taskinProcess = []  # [Freetime, id] heap 
        
        for t, task in enumerate(tasks):
            pendingTasks.append(task)
            # print(t, pendingTasks, taskinProcess, freeServers)
            while taskinProcess and taskinProcess[0][0] <= t:
                server = heappop(taskinProcess)[1]
                heappush(freeServers, [servers[server], server])
            
            while pendingTasks and freeServers:
                server = heappop(freeServers)[1]
                heappush(taskinProcess, [pendingTasks.pop(0) + t, server])
                ans.append(server)
        
        while pendingTasks:
            # print(t, pendingTasks, taskinProcess, freeServers)
            if not freeServers and taskinProcess:
                t = taskinProcess[0][0]
            while taskinProcess and taskinProcess[0][0] <= t:
                server = heappop(taskinProcess)[1]
                heappush(freeServers, [servers[server], server])
            
            while pendingTasks and freeServers:
                server = heappop(freeServers)[1]
                heappush(taskinProcess, [pendingTasks.pop(0) + t, server])
                ans.append(server)
        return ans

246

Rank Score Finish Time
2493 / 13703 12 1:09:33

1906. Minimum Absolute Difference Queries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# cr:DBabichev
 
class Solution:
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        N, ans, dp = max(nums), [], [[0] * (max(nums) + 1)]
        
        for num in nums:
            t = dp[-1][:]
            t[num] += 1
            dp.append(t)
        
        # zip 用法
        # >>> a = [1, 2, 3]
        # >>> b = [4, 5, 6]
        # >>> list(zip(a,b,range(3)))
        # [(1, 4, 0), (2, 5, 1), (3, 6, 2)]
        
        # >>> [] or [-1]
        # [-1]
        for a, b in queries:
            cur_nums = [i for x, y, i in zip(dp[b+1], dp[a], range(N+1)) if y != x]
            
            ans.append(min([b - a for a, b in zip(cur_nums, cur_nums[1:])] or [-1] ))
        
        return ans