| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 163 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Recently, i found this topic here. Can anybody point me to a more detailed explanation of this technique?? or maybe some problems here in codeforces solvable using it ??
PD: I have seen this technique in the dynamic version of convex hull trick, maybe simpler problems can help me to understand the approach. Thanks in advance :D
Just check which set is bigger, then for loop the smaller set's items into the bigger one. That's it.
I think there's some method to do it in C++17 but I don't know what it is.
And that guarantee the logn factor amortized ??
Yes. Look at any individual item. Each time this item is moved to a new set, the size of the set that contains this item is at least doubled. If you have a total of n items, each item can only be moved to a new set O(log n) times.
Thanks! I was learning small to large and this comment helped a lot.
Yes, because every item will change its set at most
times.
When you merge two sets, you only move the elements from the smaller set to the larger one. This way if the two sets are S1 and S2, such that |S1| < |S2|, then the resulting set will be of size |S1 + S2| ≥ 2 * |S1|. From this we see that when we merge two sets, we move the elements from one of the sets to another one, which is at least twice as large. Well obviously we have a finite number of elements in the sets so this process will end. Well if every time we double the size of the component of an element then we will move each element at most
times and this way we achieve 
amortized complexity.
What is 'merging' in this context? If we have 3 sets S1, S2 and S3 of sizes k1, k2 and k3 respectively where k1 + k2 + k3 = N, then cant we just do something like this:
Isn't this O(N)?
Can someone explain a little bit, instead of simply downvoting?
look at the contents of S1. That's not a set if it has 3 of the same number. Also, you can't check if an element is in vector fast.
I suggest you to look for the binary counter example, used to explain the different methods for amortized analysis. And later try to apply that to sets instead of bits, and try to analyse complexity. That worked for me :D
On the other hand, don't worry about downvoting instead focus on learn and improve; thinking is difficult that's why most people judge ;). Good luck !!!
misof radoslav11 That's right Thanks for the explanation.
Is |S1+S2|=|S1|+|S2|....?? What if both the sets contain the same elements??
Can anybody explain this ?
To merge the smaller set into the bigger set:
To merge two sorted arrays: