BURARRAY - EDITORIAL

And why is there no good data to stop this obvious force algorithm?

  1. using only path compression O(log(n))
  2. using only rank O(log(n))
  3. using both O(log^*(n))
    Disjoint Set Union (Union Find) | HackerEarth
2 Likes

oops. was unaware of log*(n) function. Thanks!:smile:

1 Like

This should be the best solution for beginners!

1 Like

This one is O(log(n)) for each query.
Itā€™s basically ā€œpath compressionā€ I think. How can some data get TLE on it ?

1 Like

brute force! No itā€™s not.

I tried it with simple brutal force ,and time limit exceeded ā€¦ I donā€™t even got a single point in this question ā€¦
Although sample test case easily passed on my solution ā€¦

Donā€™t cry. I donā€™t think you were using path compression. were you using it ?
He used it.

2 Likes

Congratulations for getting sample correctšŸ˜”.

Yes, I found that I was wrong. In fact, it made up for my knowledge gap.

1 Like

So loopfree == freeloop :stuck_out_tongue: ?

1 Like

Guys, do try the bonus problem from the editorial. It has a nice solution, but it fails DSU with path compression.

Yes, I havenā€™t practiced algorithmic problems for a long time, so Iā€™m going to start over.:roll_eyes:

1 Like

Can someone please find the mistake in this

i think i need to study alot .:expressionless:

Yes, I found that I was wrong. In fact, I used a very silly algorithm.:sleepy:

1 Like

Can you explain your solution?

1 Like

My code was also similar but getting TLE in java

I have stopped crying now because I realised he also used path compression. Thanks dude, appreciate it.

1 Like

I just made a vector hash of all the indices that were set to 0, and checked in the query of type 2 if the largest index in the subset was 0 or not. I realised though that vector is not the best of all hashes and I had to use Path Compression also.