# Leetcode for Fun

Starts from July 02, 2020

Introduction:

Some logs to document the Leetcode questions (after found a job)

07/02/2020 15:55

#### 1478. Allocate Mailboxes

Classical DP:

• f[house_i][k]: least cost if we set the k-th mailbox at house_i
• f[house_i][k] = min(f[last_house_j][k-1] + cost=sum(min(dist(house_mid, house_i), dist(house_mid, house_j)) for i < mid < j)
• with pre-calculated cost, T(N) = O(NK * N).
• f[house_i][k]: least cost if we use k mailbox in range(i, n)
• f[house_i][k] = f[house_j][k-1] + cost in range(i, j)
• with pre-calculated cost, T(N) = O(N*N*K)

04/16/2021 00:54

#### from sortedcontainers import SortedList

Key takeaways from the doc:
The library uses `insort` to insert or remove an element. Although `insort` is O(N) in theory because all the elements might have to shift, but based on the doc, `insort` is very fast in reality because some processor optimization. To prevent `insort` taking long time on a long List, the library split the List into multiple Lists (split when larger than a threshold and merge with neighbors if possible).

04/23/2021 00:24

04/24/2021 09:42

05/06/2021 22:03

#### CF 1515E

• Original thought:
• dp[light_length][left_on][right_on][#manually_turned_on] = dp[left_part][left_on][True][j] * dp[right_part][True][right_on][k]
• which requires O(n*2*2*n*n*n)
• Key observation:
• If we mark manually turned on lights as 1 and automatic ones as 0, one valid plan should look like 11101110111011
• The first and last should be manually turned on
• there will no two consecutive 0
• In other words, we can split the array by 0s. And for each consecutive 1s, we can process them one block by one block
• In a 1-block with k 1s, there are 2^(k-1) ways to turn it on. This can reduce the calculation
• Final dp