0%

Weekly Contest 207

Q1. 1592. Rearrange Spaces Between Words

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def reorderSpaces(self, text: str) -> str:
words = text.split()
spaces, n = text.count(' '), len(words)
ret = ''

for i, word in enumerate(words):
ret += word
if n > 1 and i != n-1:
ret += ' ' * (spaces // (n-1))

return ret + ' ' * ((spaces % (n-1)) if n>1 else spaces)

Q2. 1593. Split a String Into the Max Number of Unique Substrings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def maxUniqueSplit(self, s: str) -> int:
ret = 0

def dfs(idx, cnt, exist):
nonlocal ret

if idx == len(s):
ret = max(cnt, ret)
return

for i in range(idx+1, len(s)+1):
word = s[idx:i]
if word in exist:
continue
exist.add(word)
dfs(i, cnt+1, exist)
exist.discard(word)

dfs(0, 0, set())
return ret

Q3. 1594. Maximum Non Negative Product in a Matrix

Intuition

Only max or min can contribute to the possible answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def maxProductPath(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
MOD = 10 ** 9 + 7

@lru_cache(None)
def dp(x, y):
if x == 0 and y == 0:
return grid[0][0], grid[0][0]
if x < 0 or y < 0:
return ()

vals = [val * grid[x][y] for prev in [(x-1, y), (x, y-1)] for val in dp(*prev)]
# print(vals)
return max(vals), min(vals)

return (dp(m-1, n-1)[0] % MOD) if dp(m-1, n-1)[0] >= 0 else -1

Q4. 1595. Minimum Cost to Connect Two Groups of Points

Intuition

Use bit mask for represent the state of each group.

This problem is difficult since it require 2 advanced DP technic

  1. Bit Mask
  2. Optimization on State Representation
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
class Solution:
def connectTwoGroups(self, M: List[List[int]]) -> int:
def get_full(n):
ret = 0
while n:
ret <<= 1
ret += 1
n -= 1
return ret

m, n = len(M), len(M[0])
full2 = get_full(n)
conn = [min(M[j][i] for j in range(m)) for i in range(n)]

@lru_cache(None)
def dp(idx, s2):
if idx == m and s2 == full2:
return 0

ret = math.inf if idx != m else 0

if idx == m:
for i in range(n):
if (1 << i) & s2 == 0:
ret += conn[i]
else:
for i in range(n):
ret = min(ret, M[idx][i] + dp(idx+1, s2 | (1 << i)))

return ret

return dp(0, 0)

Summary

  1. Understand the problem correctly before coding. (Incorrect submission to Q1 due to misinterpretation )
  2. Optimize State Representation when TLE happens.