Petr's blog

A pseudobubble week
By Petr, history, 3 years ago, In English

https://petr-mitrichev.blogspot.com/2021/12/a-pseudobubble-week.html

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

»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

How to solve D with centroid decomposition?

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

    Never mind, I understood. You can maintain dynamic diameter and greedily take it :)

    Btw if you thought about that greedy, there is a much better way to solve it. By the algorithm, one end of diameter is always in a solution. And the connected subgraph with $$$2k$$$ leaves can be covered with $$$k$$$ paths. Thus you can root the tree and find the $$$2k-1$$$ leaves. It can be done with same greedy (with much easier segtree) or even simpler greedy in linear time.

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

      Good point! So, just a bit more thinking could have saved me a lot of implementation trouble :)

      By the way, well done getting the Voronoi problem accepted, you clearly don't shy away from implementation trouble!

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

        For problem F, I'm not really sure why you needed both persistence and a 2D data structure; I just statically built up a 2D data structure representing the pre-flip rectangles, and then used its nodes as my graph nodes. For the 2D DS, I recommend static (offline) segtree of segtrees. For each outer segtree node, gather the set of all inner coordinates which will be updated/queried at this node and then coordinate compress to build an appropriately sized inner segtree. It uses O(n log n) memory and has O(log^2 n) query time, and also lets you just use segtree book code if you want. The static outer segtree is also easier to use than persistence.

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

          I guess I didn't know a 2D data structure that supports both range updates and range queries. When I thought about a segtree of segtrees, I was not sure how to handle the following case: when one of the rectangles is very narrow, it will only be handled very deep inside the outer segtree, and then when the query is very wide, it will be handled at the top of the outer segtree and thus we won't notice the intersection?

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

            In general, it's hard to do 2D range update/range query, lazy propagation in particular doesn't work. For this problem, we only care about whether two rectangles intersect, not the size/amount/location of intersection, so we can use this trick:

            Two 1D ranges [a,b) and [c,d) intersect, iff either a is in [c, d) or c is in [a, b). In 1D, we can these solve with a point-query/range-update segtree and a range-query/point-update segtree. In the 2D case, we can take either choice for x and either choice for y, so there are 4 possibilities, and we solve it using 4 2D seg trees. One of these seg trees is point-in-rectangle queries, another is rectangle-contains-point queries, and two are horizontal/vertical line intersection queries.

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

        For E, I did expected implementation trouble in the beginning, but in the end it turned out to be rather straightforward. If you take the Voronoi cells with half-plane intersection, the rectangular boundary doesn't make the problem harder, you just put all adjacent vertices in Delaunay triangulation with four more halfplanes. Then you can get a polygonal representation which transforms the problem into pure graph problem (although with some real-number hassle)

        → Reply
»
3 years ago, # |
  Vote: I like it +59 Vote: I do not like it

what do you do with machine of 64GB of RAM ?

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

Thanks for that!

→ Reply