XORMIN - Editorial

editorial
, , , , ,
22

Wouldn’t the merge over all tries be O(n^2) on a tree of the following form?

1--3--5--7 ...
|  |  |   
2  4  6  ...
23 
if(a == NULL)
      return b;
if(b == NULL)
      return a;

This snippet of merge function will tend to give complexity of order O(n) in example given by you.

I think the worst case time complexity may be of order O(n * n^1/2) in the case where root node have n^1/2 children and each children’s subtree have n^1/2 nodes…
Use of compressed trie might have balanced this.

24

Can someone explain how the author’s solution uses O(N * log N * log C ) space for the persistent data structure ? Also, for a node, why are we excluding it’s child with largest subtree size, while calling update ? I’m guessing both are linked… it would be really helpful if someone could explain this… Thanks

25

The author’s solution was to apply persistence to each node in the tree and you can do this while traversing the tree in bottom-up fashion. Computing the tries for childrens you can build the trie for the parent. It requires merging and thus merging as explained here is done(small to large trick) .
Thus the merging part takes N * logN thereby making the overall space complexity just
O(N * log N * log C ).

3 Likes
26

Thanks for the reply… I had already gone through this post on codeforces. For the proof of complexity they just gave a reference to HLD/dsu, without details… I tried deriving it on my own, but I couldn’t… Is there any proof that clearly explains how merging takes N * log N time, in this case space ?

27

I am not sure why you mean by compressed trie, but my solution is very similar to yours and doesn’t use compressed trie. I think there is just difference in the merge function (union of 2 tries) we have used. CodeChef: Practical coding for everyone

1 Like
28

This piece of code will bring 1-2 log factor apart from n. So complexity is O(n*log^2).
Read about DSU/Sack to know a reason why.

Didnt check your code rigorously.

I did used it recently Submission #54568930 - Codeforces My soln is O(n*logn). Added along with it logAi bit of trie. Should be O(n*log^2)

1 Like
29

As far as I know, O(N*Log^2(n)) appears only when we use some other D.S like map/set with this technqiue (DSU on trees). But typically for our case, it must be O(LogN*LogC*N), where additional LogC is because of insertion in a trie.

1 Like
30

Yep. That’s true. I deliberately avoided writing C or N here. Just mentioned there are 2 log factors.

1 Like