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.
This passes the first three tests, but doesn't work for the rest. I get timeouts/stack-overflows. Are there cycles in the tree/graph? I tried testing for them but did not find any. The data sets are so large that I can't really tell what's going on...
I was unable to formulate an algorithm to correctly identify the root such that all chains are at least twice as large as the next chain lower in the order. I was able to make it so that each chain is larger than the next lower in the order.
My approach was as follows:
Working from the "leaves" in to a center node, establish parents, and find the root.
Determine the size of the tree
Establish levels for each node. Root's level is 0; lowest nodes in the tree are at the level corresponding to the size of the tree.
Establish weights for each node. Weight of a node is the sum of the weights of all non-parent edge-nodes + 1; Note: Weight of root will be "N".
Establish "special" edge for each node: This is the (non-parent) edge-node belonging to the sub-tree with the largest size, or, if two are equal in that regard, the edge with the larger weight. I originally tried/wanted to put emphasis on weight, but doing so resulted in some sub-chains with smaller weight but longer length...
Establish disjoint chains, beginning with the root: Chains follow each node's "special" edge down to the bottom of the tree. Non-special edges begin their own chains, which maintain a reference back up to the originating node.
Nodes know what chain they're in, and their position in that chain.
Finding LCA for two nodes is a matter of climbing up successive chains to find a common chain, then choosing the node with the higher index in that chain.
Finding highest value on path between two nodes is a matter of finding the highest value between each node and the LCA
I expected this approach to give ~O(log(n)) for a reasonably balanced tree/graph, though for data that looks like a straight line, it might be as bad as O(n);
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Heavy Light White Falcon
You are viewing a single comment's thread. Return to all comments →
This passes the first three tests, but doesn't work for the rest. I get timeouts/stack-overflows. Are there cycles in the tree/graph? I tried testing for them but did not find any. The data sets are so large that I can't really tell what's going on...
My approach followed this approach: https://blog.anudeep2011.com/heavy-light-decomposition/
I was unable to formulate an algorithm to correctly identify the root such that all chains are at least twice as large as the next chain lower in the order. I was able to make it so that each chain is larger than the next lower in the order.
My approach was as follows:
I expected this approach to give ~O(log(n)) for a reasonably balanced tree/graph, though for data that looks like a straight line, it might be as bad as O(n);