Блог пользователя jrarias

Merging many sets in nlogn amortized
Автор jrarias, история, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    And that guarantee the logn factor amortized ??

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← 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.

      → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится -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<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)?

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +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.

            → Ответить
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 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 :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 !!!

            → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        misof radoslav11 That's right Thanks for the explanation.

        → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    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();
    → Ответить