### stefdasca's blog

By stefdasca, history, 7 months ago,

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.

• +152

 » 7 months ago, # |   +11 Really nice video .. looking forward to more of your upcoming videos :)
 » 7 months ago, # | ← Rev. 2 →   +45 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
•  » » 7 months ago, # ^ |   +76 He might also try writing code in the IDE instead of drawing it :)
•  » » » 7 months ago, # ^ |   +1 Yeah, i will do this from the next video
•  » » » 7 months ago, # ^ |   +29 there are four reasonable options actually: prepare slides write code in IDE type text in text fields in image editor like paint but a drawing tablet
•  » » 7 months ago, # ^ |   +6 Once COVID-19 ends, I will consider buying a drawing tablet. Until that point, I will probably prepare the drawings beforehand.
 » 7 months ago, # |   +16 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...
•  » » 7 months ago, # ^ |   0 I never experienced move semantics to be slower than working with pointers. Why would you say it would be?
•  » » » 7 months ago, # ^ |   +8 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.
•  » » » 7 months ago, # ^ |   +30 FYI swap(a,b) appears to be linear for unordered_sets, while a.swap(b) is constant.
•  » » » » 7 months ago, # ^ |   +21 Interesting, according to cppreference it should be overloaded for unordered_set with constant complexity:https://en.cppreference.com/w/cpp/container/unordered_set/swap2Did you run into a linear implementation of this somewhere?
•  » » » » » 7 months ago, # ^ |   +6 mnbvmar discovered that recently. The following code takes a few seconds: Spoiler#include #include #include using namespace std; using namespace __gnu_pbds; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; int main() { ordered_set S1, S2; for (int i = 0; i < 10 * 1000; ++i) { S1.insert((long long)i * i * i); } for (int i = 0; i < 10 * 1000; ++i) { swap(S1, S2); // faster with S1.swap(S2); } } 
•  » » » » » » 7 months ago, # ^ |   +56 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.
•  » » 7 months ago, # ^ |   0 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.
 » 7 months ago, # |   +13 Nice video!I am aware of two instances of this trick, both very similar to the problem described in the video: GCPC 2018, Problem M (Mountaineers): https://codeforces.com/gym/102021 NCPC 2014, Problem F (Particle Swapping): https://open.kattis.com/problems/particles
 » 7 months ago, # |   +13 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
 » 7 months ago, # |   +104 Still waiting for a comment saying that this is well known in China
•  » » 7 months ago, # ^ | ← Rev. 2 →   +12 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.
•  » » » 7 months ago, # ^ |   +1 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?
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   +8 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.
•  » » 7 months ago, # ^ |   +26 Why state the obvious?
 » 7 months ago, # |   +121 ...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.
•  » » 7 months ago, # ^ |   +28 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.
•  » » » 7 months ago, # ^ |   +1 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.
•  » » 7 months ago, # ^ |   +8 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.
•  » » 7 months ago, # ^ |   +29 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.
 » 7 months ago, # | ← Rev. 2 →   +22 you didn't need to make a 23 minutes video for itappreciate the effort, but it was unnecessarily too long
•  » » 7 months ago, # ^ |   0 I decided to briefly explain DSUit turned out it wasn't a brief explanation, sorry for thatAbout 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)
 » 7 months ago, # | ← Rev. 2 →   +80 LOL
•  » » 7 months ago, # ^ |   0 notorious coincidence, it won't happen next time though, since I'll move to prewritten text
•  » » » 7 months ago, # ^ |   0 How is that a notorious coincidence though?
•  » » » » 7 months ago, # ^ |   +5 I used this term only because it's a meme popular hereBack to a more serious reply, everyone probably knows at this point that my handwriting sucks
 » 7 months ago, # | ← Rev. 2 →   +6 I got to use this trick for the first time when I was solving Problem C from ECPC 2015: EditorialI 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
 » 7 months ago, # |   +3 Here's a nice problem as well: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1099Enjoy!
 » 7 months ago, # |   +21 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.