jrarias's blog

By jrarias, history, 3 years ago,

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

• -3

 » 3 years ago, # |   +6 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.
•  » » 3 years ago, # ^ |   0 And that guarantee the logn factor amortized ??
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +9 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.
•  » » » » 9 months ago, # ^ |   0 Thanks! I was learning small to large and this comment helped a lot.
•  » » » 3 years ago, # ^ |   +9 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.
•  » » » » 3 years ago, # ^ |   -27 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: vector A(N); vector S1, S2, S3; int main() { for(int i = 0; i < 5; ++i) { S1.push_back(i+1); S2.push_back(i+1); S3.push_back(i+1); } for(int i = 0; i < S2.size(); ++i) S1.push_back(S2[i]); for(int i = 0; i < S3.size(); ++i) S1.push_back(S3[i]); return 0; } Isn't this O(N)?
•  » » » » » 3 years ago, # ^ |   0 Can someone explain a little bit, instead of simply downvoting?
•  » » » » » » 3 years ago, # ^ |   +1 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.
•  » » » » » » 3 years ago, # ^ |   0 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 :DOn 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 !!!
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 misof radoslav11 That's right Thanks for the explanation.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Is |S1+S2|=|S1|+|S2|....?? What if both the sets contain the same elements??
•  » » » » » 7 weeks ago, # ^ |   -17 Can anybody explain this ?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +1 To merge the smaller set into the bigger set: set small, big; big.insert(begin(small), end(small)); small.clear(); To merge two sorted arrays: vector small, big, res; merge(begin(small), end(small), begin(big), end(big), begin(res)); big = move(res); small.clear();