Dannypa's blog

Tree dp problems
By Dannypa, history, 2 years ago, translation, In English

Hi! I am in search for problems that can be solved using the following technique: if we need to merge two sets in dfs, we put elements of the larger one into the smaller one, and in total asymptotics is $$$O(nlogn)$$$. If anyone knows of this kind of problems, i would be very grateful if you post some in the comments.

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

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

Auto comment: topic has been translated by Dannypa (original revision, translated revision, compare)

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

You can see the "dsu"-taged problems.

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

    Thanks for narrowing the search space down to a couple hundreds

    → Reply
»
2 years ago, # |
  Vote: I like it -20 Vote: I do not like it

If your "set" means std::set or any self balancing tree, the total time complexity is $$$\mathcal{O}(n\log^2n)$$$, not $$$\mathcal{O}(n\log n)$$$.

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

The technique is called "small to large" you will find some problems here

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

    I thnk OP also meant small to large but just to be clear, the complexity is actually $$$\mathcal{O}(nlog^2n)$$$

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

      There are many ways to store a set. One of them is std::unordered_set, which has $$$O(1)$$$ insertion and $$$O(size)$$$ traversal, which yields $$$O(n\log n)$$$ total time for some problems. So, the "small to large" idea is not tied to a certain complexity.

      Also, sometimes we are allowed to store duplicates (or we can prove that there are no duplicates). Then, we can store sets in linked lists and merge two of them in just $$$O(1)$$$. This wouldn't require "small to large" then, but I've seen at least one problem in this comment section, which can be solved this way.

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

    Thanks!

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

    Great! This list is helpful.

    Can you share more lists of other topics? would be more helpful :)

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

https://usaco.guide/plat/merging?lang=cpp

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

https://codeforces.net/contest/1620/problem/E This one

→ Reply