BURARRAY - EDITORIAL

editorial
, , , , ,
45

Basically you implemented DSU using maps

47

I used pbds(ordered set) instead of treap but got TLE in all except first subtask although its time complexity is O(Q∗log(N)) per test case :neutral_face:
Can someone explain what mistake I am doing Code

1 Like
50

i also tried same approach but complexity of this algo this O(Q*log(q)*log(q)) which is around 4 * 10^9 which is resulting in TLE.

51

what is O(log*(n)) ? what is * ?

52

I thought segment tree will be used and my mind was moving around segment tree only. I just managed to get 20 points, but now when i see the editorial, i am like…:expressionless:

53

A very nice solution indeed!

1 Like
54

\log_2(2*10^5)=19 whereas log^*_2(2*10^5)=4
Google it.

55

atleast give me a key word to search :joy:

56

Already gave. Search log^*(n)

1 Like
57

The input size is huge, 10^{18}. Lazy propogation won’t make a difference. Dsu with path compression using maps will work fine as mentioned by editorialist.

1 Like
58

yes…(20 char limit)

59

Thnks! got it now…

1 Like
60

Is the bonus problem also for people who are using path compression??

61

Is it possible to solve this problem using Square Root decomposition?
By storing all the updated elements in an array of vectors and querying only those buckets which lie in the range l to r.

63

Works for all cases.
Using path compression/using union by rank/using both.
Easy modification.

64

yep
solution:- add a query of type 3 with 3 followed by the index of the element.

If the element is not zero before the update:
     Do nothing.
Else:
      set par[par[node]]=node and del par[node]:
 
This modification is for the code which is using path compression
65

wrong using only path compression complexity is q*α(q).
α is the inverse of the ackermann function and in CP terms α of a number is not more than 4.So linear complexity.

1 Like
66

Okay. Cool. \hspace{1mm}
My solution with and without path compression takes equal time.
Does that mean union by rank is also O(4) ? :sweat_smile:

67

I am not sure about union by rank

68

I have used a similar approach as the tester, but I am getting TLE on the last subtask. Link to my solution : CodeChef: Practical coding for everyone