szawinis's blog

By szawinis, history, 10 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

»
10 years ago, hide # |
 
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

»
10 years ago, hide # |
 
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.

»
5 years ago, hide # |
← 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