15_percent_vat's blog

Help needed in SEERC 2017 problems
By 15_percent_vat, history, 6 years ago, In English

Contest Link in GYM

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

How to solve B and L?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      The number of the edges is 4(n - 1) and there are only n nodes. So there must be a node with degree  ≤ 3.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      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.

      → Reply