jrarias's blog

Merging many sets in nlogn amortized
By jrarias, history, 6 years ago, In English

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

  • Vote: I like it
  • -3
  • Vote: I do not like it

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

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.

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

    And that guarantee the logn factor amortized ??

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

      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.

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

        Thanks! I was learning small to large and this comment helped a lot.

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

      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.

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

        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<int> A(N);
vector<int> 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)?

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

          Can someone explain a little bit, instead of simply downvoting?

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

            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.

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

            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 !!!

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

        misof radoslav11 That's right Thanks for the explanation.

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

        Is |S1+S2|=|S1|+|S2|....?? What if both the sets contain the same elements??

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -17 Vote: I do not like it

          Can anybody explain this ?

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

    To merge the smaller set into the bigger set:

    set<ll> small, big;
big.insert(begin(small), end(small));
small.clear();

    To merge two sorted arrays:

    vector<ll> small, big, res;
merge(begin(small), end(small), begin(big), end(big), begin(res));
big = move(res);
small.clear();
    → Reply