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.
In-order traversal (DFS), tracking start and end of each node's subtree (self inclusive)
Process each guess. A) If the parent-child relationship of the guess is correct in our arbitrarily rooted array from step 2, then we know that all nodes not in the child are closer to the parent, so increment the win count for the root node (as a proxy for all nodes, as it "covers" the whole tree), and decrement the win count for the child node (as a proxy for the whole subtree rooted at that child node). In other words - for all trees not rooted in the child node's subtree, this guess would be correct. B) If the parent-child relationship of the guess is incorrect, then we know the inverse (only if the tree were rooted at one of the nodes in the [incorrect] parent's subtree, would the given guess be correct). So we increment the win count of the parent node, as a proxy for it's whole subtree.
Count winners. The tree isn't necessarily binary, so don't think segment tree, per se. Rather, think about summing up the sum of correct guesses node-by-node, walking through our arbitrarily rooted tree array. But remember that we only marked the beginning of each (subtree) range. In order not to overcount the winning guesses as we roll past the end of a range, we need to go back to step 3, and decrement the wins for the node 1 past the winning the range, for each time we flag a range of winning tree roots. For each node, if our rolling sum is >= the threshhold for winning (k), then increment a variable that tracks total wins.
Return total wins / total nodes (because each node represents a different tree, rooted at that node); be sure to simplify your fractions (get the GCD, and divide both the numerator and denominator by the GCD).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Story of a Tree
You are viewing a single comment's thread. Return to all comments →