Блог пользователя 15_percent_vat

Автор 15_percent_vat, история, 6 лет назад, По-английски

Contest Link in GYM

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

How to solve B and L?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
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/fM5nVp
O(N2) Solution: https://ideone.com/7pZh4R
O(N * log(N)) Solution: https://ideone.com/GHDnd1
O(N) Solution: https://ideone.com/L9o6dz

L: 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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks a lot. In L, what is the proof that answer will always be 2 or 3?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In L, can you please give me some hints on how to calculate the number of ways?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -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.