Leetcode for Fun

Starts from July 02, 2020


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

csp 2021 Apr No4:

04/24/2021 09:42

bloom filter

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
      • dp[light_length][#manually_turned_on] = dp[light_length-last_block_len-1][#manually_turned_on-lask_block_len] * 2^(lask_block_len) * C(#manually_turned_on, lask_block_len)
  • Takeaway:
    • think about the nature of the problem. Do rush into the dp.