0%

Weekly Contest 200

Q1. 1534. Count Good Triplets

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c
Where |x| denotes the absolute value of x.

Return the number of good triplets.

Note

From constrain 3 <= arr.length <= 100, we know this can be solved by complete search aka Brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def countGoodTriplets(self, A: List[int], a: int, b: int, c: int) -> int:
ret = 0
def dfs(arr, idx):
nonlocal ret
if len(arr) == 3:
if abs(arr[0]-arr[1]) <= a and abs(arr[1]-arr[2]) <= b and abs(arr[0]-arr[2]) <= c:
ret += 1
return
for i in range(idx, len(A)):
dfs(arr+[A[i]], i+1)
dfs([], 0)
return ret

Q2. 1535. Find the Winner of an Array Game

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Note

Stuck here for a long time.
Key point is once we have visited the entire array once, the greatest number will be kept at idx-0.
Hence, we can simply simulate the game and find the first number win k times.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def getWinner(self, arr: List[int], k: int) -> int:
cur, win = arr[0], 0
for i in range(1, len(arr)):
if arr[i] > cur:
cur = arr[i]
win = 1
else:
win +=1
if win == k:
return cur
return cur

3. 1536. Minimum Swaps to Arrange a Binary Grid

See details in link

Note

After you realize that this question is about permutation of array, it is not that hard.
Convert matrix into array of numbers by counting the length of continuous 0 from right side.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def minSwaps(self, grid: List[List[int]]) -> int:
nums = []
for row in grid:
size = 0
i = len(row) - 1
while i >= 0 and row[i] == 0:
i -= 1
nums.append(len(row) - i - 1)
n = len(grid)
ret = 0
for i in range(n-1):
expect = n - i - 1
for j in range(i, n):
if nums[j] >= expect:
nums = nums[:i] + [nums[j]] + nums[i:j] + nums[j+1:]
ret += j - i
break
else:
return -1
return ret

Q4. 1537. Get the Maximum Score FAILED

See details in link

Note

I thought this must be a DP problem hence we can easily tell how the state is transit from previous state.

Start with a 2-D DP which cause TLE/MLE.

Was not realize that we should have 2 dictionaries to store the states.
That will reduce the memory/time complexity from M^2 to 2M.

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
idx1 = {v: i for i, v in enumerate(nums1)}
idx2 = {v: i for i, v in enumerate(nums2)}
idxs = [idx1, idx2]
arrs = [nums1, nums2]
memo = {}
def dp(arr_id, idx):
if (arr_id, idx) in memo: return memo[(arr_id, idx)]
if idx >= len(arrs[arr_id]): return 0
val = arrs[arr_id][idx]
ret = val + dp(arr_id, idx+1)
if val in idxs[not arr_id]:
ret = max(ret, val + dp(not arr_id, idxs[not arr_id][val]+1))
memo[(arr_id, idx)] = ret
return memo[(arr_id, idx)]
return max(dp(0, 0), dp(1, 0)) % (10**9+7)

Greedy

1
2
3
4
5
6
7
8
9
10
class Solution:
def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
idx1 = {v: i for i, v in enumerate(nums1)}
idx2 = {v: i for i, v in enumerate(nums2)}

keys = [i for i in idx1 if i in idx2]
vals = [max(sum(nums1[idx1[k1]:idx1[k2]]), sum(nums2[idx2[k1]:idx2[k2]])) for k1, k2 in zip(keys, keys[1:])]

if not keys: return max(sum(nums1), sum(nums2))
return (sum(vals) + max(sum(nums1[:idx1[keys[0]]]+[0]), sum(nums2[:idx2[keys[0]]]+[0])) + max(sum(nums1[idx1[keys[-1]]:]+[0]), sum(nums2[idx2[keys[-1]]:]+[0]))) % (10**9+7)

Summary

  1. Usually, Q1 Q2 has not magic. Simple complete search or simulation is enough.
  2. Surprisingly, @lru_cache cause MLE while native dictionary works.