### 15_percent_vat's blog

By 15_percent_vat, history, 4 years ago,

Could not find any discussion on problems, so I am posting here.

How to solve B and L?

• 0

 » 4 years ago, # | ← Rev. 2 →   +8 B:An interval [L,R] of 1s (0 at the L-1 and R+1) is possible if and only if, the number of fallen boxes in this interval equals R-L+1 and also there's no boxes in L-1 and R+1. So we can use a dp solution. After this observation and O(N3) dp solution it's easy to decrease complexity.O(N3) Solution: https://ideone.com/fM5nVpO(N2) Solution: https://ideone.com/7pZh4RO(N * log(N)) Solution: https://ideone.com/GHDnd1O(N) Solution: https://ideone.com/L9o6dzL: Answer is always 2 or 3, I think it's easy to come up with a solution to calculate the number of ways after that.
•  » » 4 years ago, # ^ |   0 Thanks a lot. In L, what is the proof that answer will always be 2 or 3?
•  » » » 4 years ago, # ^ |   +11 The number of the edges is 4(n - 1) and there are only n nodes. So there must be a node with degree  ≤ 3.
•  » » 4 years ago, # ^ |   0 In L, can you please give me some hints on how to calculate the number of ways?
•  » » » 4 years ago, # ^ |   -6 The solution after being aware of that the answer is 2 or 3, can be enumerate the cutting edge on a tree, and calculate which of the edges should be cut on the other tree. A trick solution is to use LCA and cal sum of subtree when using DFS. Another solution is just use dsu on tree, then u can easily calculate the answer.