szawinis's blog

How to solve YATP from Kattis?
By szawinis, history, 8 years ago, In English

Problem Statement: Click

It definitely requires convex hull optimization, but I'm not sure how to merge the sets properly. I've thought about the usual "merge the small subtree to the large subtree" trick, but it doesn't seem to work. Is there anything I'm missing? And also, which variant of the convex hull optimization should I use? Does it require the fully dynamic variant?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can view judge solutions and I/O here: http://serjudging.vanb.org/?cat=28

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

    Thanks, but it there also an explanation available?

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

      I haven't solved it yet, but my teammate tells me it uses centroid decomposition.

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

        No wonder I couldn't solve it. Anyways, the solution looked like it used a special trick with DSU. I'm not sure what that's about though.

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

It can be solved with static version of convex hull trick where you can pre-sort slopes. You want to combine it with centroid decomposition. It's simplified when you notice that you don't have to consider strict paths. Walks that have repeated edges are always worse than paths with no repeated edges.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the hint. I'll go ahead and learn centroid decomposition now (btw tehqin's episode on it is about to come out!)

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

      My most recent episode covers the idea behind both solutions with the problem author: https://www.youtube.com/watch?v=vueL8tDDwfE

      We assume the prerequisites from the previous two episodes.

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

        This is really helpful. For those who are searching for the editorial, you can get it here, nicely explained by the setter.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I would like to share my AC code, for those who get stuck with the problem and cannot find any code on the net like me.

code
→ Reply