We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Lazy White Falcon
Lazy White Falcon
Sort by
recency
|
14 Discussions
|
Please Login in order to post a comment
PyPy 3 solution
here is hackerrank lazy white falcon solution
Hello. Please can anyone help me with this problem? I'm getting a timeout for the testcase with 100000 queries. I suspect the problem is from my algorithm to calculate the sum. The code is below:
Is there a better way to implement it?
Finally AC with HLD with Segment Trees ;)
Quite a tedious problem. The catch is in the fact that the tree may be very unbalanced, so you cannot directly “walk” the tree to aggregate.
Don't know if there is an official name for the summarized tree representation, but I'm reasonably proud that invented it independently:
First modification we make is node set operation has to be expressed in terms of node increment operation (just remember the last value independently)
Then we come to the concept of aggregate tree representation where each child node has a summary of all parents up to the root. That way the answer is L + R - LCA(L,R)
We will get such aggregate tree if every node increment operation will be performed as entire subtree increment.
Here is how to perform all children increment efficiently:
The strategy lies in the DFS tree representation, where all children lay sequentially. That way updates turn into interval increment commands which we can perform using Fenwick or segment tree with O(logN) update and O(logN) to summarize.
Lowest common ancestor (LCA) routine has to be accelerated too. That part is relatively straightforward, just have pointers to 1, 2, 4, 8, 16th, etc parent above in each node to perform ascend operation in O(logN). Then use a binary search to find LCA in O(logN * logN).