kaiyu's blog

TLE for DSU with Path Compression and Union By Size
By kaiyu, history, 5 years ago, In English

Problem:

https://codeforces.me/contest/893/problem/C

My solution:

https://codeforces.me/contest/893/submission/79402491

why does it give TLE?

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

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It looks like you are calling std::set methods find() and erase() in your union_sets function. They are O(log N), moreover, the constant is really huge. Consider getting rid of those calls.

By the way, what you are using looks like union by size, not union by rank.

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Your solution is simply not optimal. Before you read any further, I urge you to once again quickly go through your code.

Let's begin. Your logic is correct but its implementation is weak. You are storing the roots (or heads) of each disjoint set in a separate set called 'tmp'. In your Union function, you are making a total of 5 calls on this set 'tmp'. So let's make a rough estimate of the total complexity of your Union function. 2 calls for find_set (to find root) and 5 calls on 'temp' (each O(lg(n)) so it is O(7 * lg(n)). [lg(n) is log n base 2]. With given constraints, total time complexity = O(n * 7 * lg(n) + 2 * n * lg(n)) as you are initialising the set 'tmp' and finally iterating through it at the end to get answer too. When n = 10^5, then complexity = O(9 * 10^5 * lg(10^5)) , which is approximately O(1.5 * 10^7). Add to this the overhead of all these operations and you realize why you get the TLE!! In any decent problem, at most 10^6 (10^7 in rare cases) complexity is required with the most optimal solution (operations can reach 10^8 with the overhead, which is still rare). While on the surface your algorithm looks like O(n * log(n)), it's really not.

So what could you have done better? It's simple really. You need not have to keep the 'tmp' set to store the roots at all. Notice that if a vertex/node 'a' is a root, then parent[a] = a. This way you can identify your root vertex without needing to store it elsewhere. As far as the given problem is concerned, since you are only adding the minimum gold from each disjoint set, you can just store this minimum gold for the whole set in the root vertex itself. That is, gold[a] = min gold from disjoint set where a is the root vertex. The gold[v] value for other vertices which are not root (parent[v] != v) doesn't matter.

I made minimum modifications to your code to show this. It now gets AC.

DSU is one of my favourite topics and I suggest you build a template that you can quickly use. If you are interested, this is my code that I wrote when I saw your question. You can use the template if you wish to. Or you can check out submissions of top coders.

Best of luck!

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

    Oh, I will go through your code. Yeah I will build a template for that.

    Thank you so much for your time!Genuinely

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

    can you share your dsu template? just for reference

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      vector<int> par;
void init_dsu(int n) { par.clear(); par.resize(n, -1); }
int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); }
void Union(int x, int y) {
    if((x = root(x)) == (y = root(y)))  return;
    if(par[y] < par[x])   swap(x,y);
    par[x] += par[y];
    par[y] = x;
}

      The vector par holds the parent of each node, but for root node, it stores the negative of the size of the respective set. This way root i can be identified if par[i] < 0. Furthermore, -par[i] gives the size of that set. Using this format, you do not require an additional array to store size.

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

You should keep things simple, I tried with DSU, here is the link

A=> parent array and other things are simple.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
void make_set(int v) {
	parent[v] = v;
	size[v] = 0;
}
 
int get_parent(int v) {
	if (v == parent[v]) {
		return v;
        }
	return parent[v] = get_parent(parent[v]);
}
 
void union_sets(int a, int b) {
	a = get_parent(a);
	b = get_parent(b);
	if (a != b) {
		if (size[a] > size[b]) {
			swap (a, b);
                }
		parent[a] = b;
		size[b] += size[a];
	}
}
→ Reply