stefdasca's blog

A quite interesting trick involving Disjoint Set Union
By stefdasca, history, 5 years ago, In English

Hi!

While I was solving some National Olympiad problems, I came up with an interesting DSU trick which can be used instead of Parallel Binary Search.

Now that I started an YouTube channel, I decided to make a video based on it.

If you enjoyed watching, please leave a like and press the subscribe button.

Also, if you know the name of this trick, please share it here or on Youtube comment section.

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

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Really nice video .. looking forward to more of your upcoming videos :)

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

You might want to try getting a drawing tablet. It makes sketching in your pc a lot easier.

I think it's a nice gadget to have if you plan to continue making videos like this

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

    He might also try writing code in the IDE instead of drawing it :)

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

      Yeah, i will do this from the next video

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

      there are four reasonable options actually:

      1. prepare slides
      2. write code in IDE
      3. type text in text fields in image editor like paint
      4. but a drawing tablet
      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Once COVID-19 ends, I will consider buying a drawing tablet.

    Until that point, I will probably prepare the drawings beforehand.

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

This is indeed a neat trick. As some feedback on the video, the implementation is a bit unpolished -- you wrote int x = *s[c].lower_bound(it);, but as I'm sure you know this is an error if s[c].lower_bound(it) is s[c].end(). Better would be something like if (s[c].count(it)) { ... Maybe write a reference implementation first so you can refer to it to avoid these kinds of issues.

Maybe I missed it, but you also didn't say what the complexity was? I know about the small-to-large trick but I imagine someone that doesn't know DSU wouldn't.

And (this bit is personal preference), but I usually swap() the sets so that the set corresponding to a is always s[a]. This might be a bit slower but I get easily confused if I have to keep track of a separate where array...

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

    I never experienced move semantics to be slower than working with pointers. Why would you say it would be?

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

      By "might" be, I actually meant that I don't really know whether it is or not :)

      But I've also never had any issues with it, and it's simpler to work with for me.

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

      FYI swap(a,b) appears to be linear for unordered_sets, while a.swap(b) is constant.

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

        Interesting, according to cppreference it should be overloaded for unordered_set with constant complexity:

        https://en.cppreference.com/w/cpp/container/unordered_set/swap2

        Did you run into a linear implementation of this somewhere?

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

          mnbvmar discovered that recently. The following code takes a few seconds:

          Spoiler
          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +56 Vote: I do not like it

            This is a very different thing since __gnu_pbds::tree is an extension type, which is not required to have an std::swap overload by the standard. unordered_set is, so if it didn't that would be a bug.

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

    The complexity is O(n log n) or O(n log^2 n), depending on the implementation.

    For example, in some cases, we can use std::vector instead of std::set, but in other cases, we can't.

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

Nice video!

I am aware of two instances of this trick, both very similar to the problem described in the video:

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

Nice video, thanks!

The same problem appeared in ECPC 2015, problem C if someone wants to submit a solution.

Another similar problem: SpbKOSHP 19 C

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

Still waiting for a comment saying that this is well known in China

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

    Well to be fair, this trick is pretty easy to come up with, the number of applicable problems is small, and there's a better/easier to implement trick called persistent dsu (not the roll-back one).

    So what I mean is, it's not well-known, but it's also not a surprise if a lot of people have already came up with this themselves.

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

      Can you link an implementation/explanation of this persistent dsu?

      To solve the problem OP proposed, would you do a binary search for each query?

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

        A really similar problem. Idk if this is called persistent dsu, but the idea is to maintain the time that each link was made in the dsu tree, so the time that a and b are linked is the maximum in the path from a to b in the dsu tree, since the depth is less than log(n), we can go up in a naive manner.

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

    Why state the obvious?

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

...And not a single comment with a text summary.
Looks like people are ready to accept video as the base medium.
As a person who greatly prefers reading rather than watching or listening, I find it sad.

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

    There's a clear disadvantage to making a video about something: some people don't watch videos. I, for example, watch videos only when the content is necessarily visual, like AOE2 matches. Others don't even do that.

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

      Yeah, that. Hard to imagine people that are good at competitive programming but don't read.

      With the current environment forcing a shift to online education, however, some of us readers may be forced to embrace the other ways to convey information.

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

    I agree.

    Another argument supporting this is that in some countries (such as Cuba) internet until 2 years ago was unreasonable slow and downloading/watching videos was almost impossible. Right now, we improved a lot in downloading speed, but internet is so expensive that you might better know if downloading that video will worth it or not, so at least a text summary is quite convenient.

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

    My opinion about it is evolving but right now I would say the following.

    Harder topics should be written down so that you could spend more time looking at some particular difficult fragment and analyze it (sometimes one needs a lot of time to get something complicated), and first of all you can decide if the content is useful for you or not (if you're experienced, you can make this decision). For example, I plan to make a blog "how to make fft fast" without any video.

    Easier topics should (or at least can) be videos to popularize CP and encourage more people, including casual coders and complete beginners, plus it's less formal, thus easier to understand for them. And written editorials/tutorials are oversaturated already. For example, I don't see a point in writing a CF article on binary search but I made a video for YT.

    If you disagree with something, please tell me because it will very likely affect my actions in the near future.

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

you didn't need to make a 23 minutes video for it

appreciate the effort, but it was unnecessarily too long

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

    I decided to briefly explain DSU

    it turned out it wasn't a brief explanation, sorry for that

    About that trick, I felt like I need to explain it in detail, since I haven't seen it anywhere before(it turned out there were other problems featuring it, thanks to this blog I found this out)

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

      Hello, reflecting back, I think it was quite rude to say it like that. Sorry :( It was actually pretty good, considering those were the first videos.

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

        Pretty interesting to read such a comment, ngl :).

        You don't have to be sorry, criticizing that aspect of the video was alright, it helped me improve my content and as you said, it was a good video for a beginner youtuber.

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

LOL

photo-2020-03-30-19-19-47

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

    notorious coincidence, it won't happen next time though, since I'll move to prewritten text

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

      How is that a notorious coincidence though?

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

        I used this term only because it's a meme popular here

        Back to a more serious reply, everyone probably knows at this point that my handwriting sucks

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

I got to use this trick for the first time when I was solving Problem C from ECPC 2015: Editorial

I didn't like juggling sorted vectors and dsu data back then, so I came up with an alternative implementation based on labeling edges of the dsu tree.

When we merge 2 sets' parents, we label the edge between them with their current update query time. This way, the first time 2 nodes become connected will be the maximum edge label on the path between the 2 nodes in the dsu tree. Since edge labels increase as you go up, we only care about the 2 edges connected to their LCA

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

Here's a nice problem as well: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1099

Enjoy!

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

You can enhance the complexity to $$$O(nlog(n)\alpha(n))$$$ by replacing the sets with vectors and checking if 2 nodes are in the same component with normal dsu.

Also, there's a pretty easy $$$O(log(n))$$$ per query online solution. You can iterate over the edges in input order and make a spanning tree of the edges that join new components (aka label each edge with its index and take the MST.) The answer to a query $$$(u,v)$$$ is just the maximum edge across the path $$$(u,v)$$$ in this tree. You can even answer queries online in $$$O(1)$$$ using tricks from these blogs.

→ Reply