0 like 0 dislike
1,068 views
| 1,068 views

0 like 0 dislike

Image of Questions

by Expert (111,350 points)
0 like 0 dislike

Q2 dp

``````    adj=collectiosn.defaultdict(set)
costs=Counter()
for u,v,w in edges:
costs[v,u]=w

@cache
def dfs(cur,prev):
return sum(dfs(nxt,cur)+costs[cur,nxt] for nxt in adj(cur)-{prev})

return min(dfs(node,-1) for node in adj)``````
by Expert (111,350 points)
0 like 0 dislike

Q3 sliding window

``````    s=list(map(int,s))
ct=[0,0]
tot=l=0
res=float('inf')

for r in range(len(s)):
ct[s[r]]+=1
tot+=ct[0]*(1-s[r])

while tot>=k:
res=min(res,r-l+1)
tot-=ct[1]*(1-s[l])
ct[s[l]]-=1
l+=1
return [res,-1][res==foat('inf')]  ``````
by Expert (111,350 points)
0 like 0 dislike

Q1:

1.

we sort pairs by B from high to low.

2.

given B[i] is the smallest b, we can only choose pairs before B[i] from the sorted arr because only those pairs have B[j]>=B[i]

3.

if k is odd, we pick the largest k//2 nums and the smallest k//2 nums, depending on the sign of B[i], either largest -smallest or smallest-largest
if k is even, we either pick k//2-1 largest and k//2 smallest, or k//2 largest and k//2-1 smallest

`````` A=[1,4,-3,4,-6,-4,6,7,8]
B=[1,2,-4,5,-6,-7,2,1,2]

k=3

low,high=[],[]               # store the largest k//2 A[i] and the smallest k//2 A[i]
th=tl=0                      # sum of the largest k//2 A[i] and  sum of the smallest k//2 A[i]
res=float('-inf')
for b,a in sorted(zip(B,A),reverse=True):          # sort pairs by B from high to low
if k%2:
res=max([res, (th-tl+a)*b,(tl-th+a)*b])    #  if b is negative, smallest minus the largest;  else, largest-smallest

elif high and low:
i,j=th-high[0]+a-tl,tl+low[0]+a-th
res=max([res,i*b,-i*b,j*b,-j*b ])

heapq.heappush(high,a)
heapq.heappush(low,-a)
th+=a
tl-=-a
if len(high)>k//2:
th-=heapq.heappop(high)
if len(low)>k//2:
tl+=heapq.heappop(low)
return res``````
by Expert (111,350 points)