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.
Really nice video .. looking forward to more of your upcoming videos :)
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
He might also try writing code in the IDE instead of drawing it :)
Yeah, i will do this from the next video
there are four reasonable options actually:
Once COVID-19 ends, I will consider buying a drawing tablet.
Until that point, I will probably prepare the drawings beforehand.
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 ifs[c].lower_bound(it)iss[c].end(). Better would be something likeif (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 toais alwayss[a]. This might be a bit slower but I get easily confused if I have to keep track of a separatewherearray...I never experienced move semantics to be slower than working with pointers. Why would you say it would be?
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.
FYI
swap(a,b)appears to be linear for unordered_sets, whilea.swap(b)is constant.Interesting, according to cppreference it should be overloaded for
unordered_setwith constant complexity:https://en.cppreference.com/w/cpp/container/unordered_set/swap2
Did you run into a linear implementation of this somewhere?
mnbvmar discovered that recently. The following code takes a few seconds:
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_setis, so if it didn't that would be a bug.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.
Nice video!
I am aware of two instances of this trick, both very similar to the problem described in the video:
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
Still waiting for a comment saying that this is well known in China
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.
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?
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.
Why state the obvious?
...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.
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.
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.
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.
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.
you didn't need to make a 23 minutes video for it
appreciate the effort, but it was unnecessarily too long
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)
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.
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.
LOL
notorious coincidence, it won't happen next time though, since I'll move to prewritten text
How is that a notorious coincidence though?
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
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
Here's a nice problem as well: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1099
Enjoy!
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.