# Biweekly Contest 63
# Leetcode 2037
2037. Minimum Number of Moves to Seat Every
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
seats.sort()
students.sort()
res = 0
for i in range(len(seats)):
res += abs(students[i] - seats[i])
return res
# Leetcode 2038
2038. Remove Colored Pieces if Both Neighbors
class Solution:
def winnerOfGame(self, colors: str) -> bool:
alice = 0
bob = 0
for i in range(len(colors) - 2):
if colors[i:i+3] == 'AAA':
alice += 1
if colors[i:i+3] == 'BBB':
bob += 1
if alice <= bob:
return False
else:
return True
# Leetcode 2039
2039. The Time When the Network Becomes Idle
First build graph, and calculate the distance d between each node to node[0], the time for the first reply to arrive is 2d. And the delay time if , special case is when , in this case, when the node receive the reply message, it won't send out a new message, so the delay for the last message is . And the delay time is the time for the last message to arrive at node, there would be one more second for the whole area to become idle.
class Solution:
def networkBecomesIdle(self, edges, patience) -> int:
connected = {}
dist = {}
for i in range(len(patience)):
connected[i] = []
dist[(i, 0)] = 10 ** 9
for src, dest in edges:
connected[src].append(dest)
connected[dest].append(src)
dist[(0, 0)] = 0
stack = []
for element in connected[0]:
stack.append(element)
cnt = 1
stack.append(None)
visited = set()
visited.add(0)
flag = False
while len(stack) > 0:
node = stack.pop(0)
if node is None:
if flag is True:
break
stack.append(None)
flag = True
cnt += 1
continue
flag = False
if node in visited:
continue
visited.add(node)
dist[(node, 0)] = min(cnt, dist[(node, 0)])
for element in connected[node]:
if element not in visited:
stack.append(element)
res = 0
for i in range(1, len(patience)):
time = dist[(i, 0)] * 2
res = max(time + 1, res)
if time > patience[i]:
delay = time % patience[i]
if delay == 0:
delay += patience[i]
total = time + time - delay + 1
res = max(res, total)
return res
# Leetcode 2040
2040. Kth Smallest Product of Two Sorted Array
Didn't finish during contest, this is the reference of Leetcode User: lee215
class Solution:
def kthSmallestProduct(self, A, B, k):
n, m = len(A), len(B)
A1,A2 = [-a for a in A if a < 0][::-1], [a for a in A if a >= 0]
B1,B2 = [-a for a in B if a < 0][::-1], [a for a in B if a >= 0]
neg = len(A1) * len(B2) + len(A2) * len(B1)
if k > neg:
k -= neg
s = 1
else:
k = neg - k + 1
B1, B2 = B2,B1
s = -1
def count(A, B, x):
res = 0
j = len(B) - 1
for i in xrange(len(A)):
while j >= 0 and A[i] * B[j] > x:
j -= 1
res += j + 1
return res
left, right = 0, 10**10
while left < right:
mid = (left + right) / 2
if count(A1, B1, mid) + count(A2, B2, mid) >= k:
right = mid
else:
left = mid + 1
return left * s