PinkRabbit's blog

By PinkRabbit, history, 3 weeks ago, In English,

Hello! I have a problem solving problem 150E — Freezing with Style.

It can be solved by Binary Search & Centroid Decomposition & a bit data structure in $$$\mathcal{O}(n\log^2 n)$$$.

But I'm wondering is there an $$$\mathcal{O}(n\log n)$$$ solution?

I suppose Binary Search should be preserved, so here is a $$$\log n$$$. So the problem is : given a tree with it's edge's weights are either $$$1$$$ or $$$-1$$$, determine whether there is a simple path with non-negative total weight and it's length is in $$$[l,r]$$$.

My idea is to use high-low decomposition, you can learn it here (solution of 1009F — Dominant Indices), it looks like DSU on tree but focus on depth of the subtree instead of size. Because this problem also have something to do with depth, I think this method may help.

I can't go any further this way. So I write this blog and hope someone can help me with this problem, thanks!

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

»
2 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

I'll just write centroid decomposition then...

»
2 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Yeah, I think a single logarithm is possible.

First, you indeed don't need centroid decomposition to get $$$\mathcal{O} (n \cdot \log (10^9) \cdot \log n)$$$. We should binary search the answer and then use bottom-up dp where you merge smaller to bigger subtrees (in terms of depth). When you iterate over depth $$$d$$$ in smaller subtree, you know what depth of vertex in the other subtree you need (between $$$l-d$$$ and $$$r-d$$$) and you query a segment tree for maximum in this interval.

My first idea to get rid of one logarithm is that values are $$$-1$$$ and $$$+1$$$ what means that max prefix sums are very special (every next one is greater by at most $$$1$$$). It didn't seem to work.

Instead, let's notice that we always query for an interval of size $$$r-l$$$ or prefix or suffix (if interval $$$[l-d, r-d]$$$ doesn't fully fit in bigger subtree). This can be maintained without a segment tree. We need a data structure that handles the following operations:

  1. Append new number at the beginning.
  2. Modify some prefix (when merging with smaller subtree): every number will be maximized with some new numbers. The complexity should be linear of the size of modified prefix.
  3. Ask for a maximum in prefix or suffix (of length at most $$$r-l$$$).
  4. Ask for a maximum in an interval of size $$$r-l$$$.

And we used the fact that the sum over depth of non-largest children is linear.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    crap. I have already used centroid decomposition and accepted it...

    I'll check this solution later, thanks a lot!

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      Well, your goal should be to learn something new rather than just get AC. Then it isn't bad at all that you solved it in one way and will now know (or even implement) another version.

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

I got this solution too, but I don't really understand why the complexity is $$$O(N \log^2 N)$$$.

In fact I think that it is $$$O(N \log^3 N)$$$ because first of all we have $$$1 \log N$$$ factor for the binary search, then for the centroid decomposition for each of the $$$O(N \log N)$$$ paths we look with $$$O(\log N)$$$ complexity in the bit data structure.

Combining this gives $$$O(N \log^3 N)$$$ total time complexity. Can someone tell me where I'm wrong and why the complexity is $$$O(N \log^2 N)$$$. Thanks in advance.

  • »
    »
    23 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    sorry, by "a bit data structure", I mean, truely a bit data structure, not Fenwick Tree. it's actually a non-decreasing queue, to get the minimum value in a sliding window.