BURARRAY - EDITORIAL

editorial
, , , , ,
23

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

24
  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
25

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

1 Like
26

This should be the best solution for beginners!

1 Like
27

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
28

brute force! No itā€™s not.

29

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 ā€¦

30

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

2 Likes
31

Congratulations for getting sample correctšŸ˜”.

32

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

1 Like
33

So loopfree == freeloop :stuck_out_tongue: ?

1 Like
34

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

35

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

1 Like
36

Can someone please find the mistake in this

37

i think i need to study alot .:expressionless:

38

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

1 Like
40

Can you explain your solution?

1 Like
41

My code was also similar but getting TLE in java

43

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

1 Like
44

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.