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 was a fun problem. A few tips to help you get started...
1) The input for the "tree" is an undirected graph. There is no parent/child relationship implied. The edges are not ordered in any meaningful way. So you might get 1-2, then 3-4 (which looks like 2 separate collections) and finally get 4-2. This would create a graph like 1-2-4-3. Where's the root? It doesn't really matter. Imagine grabbing any node, and letting the others hang-down. You are assured that once connected, all of the nodes create a single graph (with no loops/cycles) - so by picking any node as root, you have a tree. I suggest that after the graph is built, you might want to choose a root and establish parent/child relationships in your tree.
2) In case it wasn't clear, this is not a binary tree. Any node can have many children. (Example: Every node in the tree could be connected to node 3 with input like 2-3, 3-1, 4-3, 3-5. This is still a tree, and any node could be root.)
3) The number of "coins" at the given nodes is >= 1, but the number of coins added in the final node (node cw) is >= 0 ("any non-negative integer")
4) The wording of the problem indicates that you add node cw and then make 2 cuts. But you don't know where you will have to add. You could have a case where you split the existing tree in half and the added node forms the 3rd tree. To avoid worrying about these cases, you can create a dummy node with 0 coins as a leaf node (only 1 connecting edge). Now, with 2 cuts, it's possible to have one of the trees as empty. Then you can "add" cw where needed to balance the trees.
5) To get started on an algorithm, consider what would happen if you iterate through the tree, trying to cut each edge. As you cut an edge, you have 2 trees. Since you can only add (not subtract) coins to achieve the final balance, we would need two equal larger trees, and one smaller (or equal) tree. Given this, with 2 trees, we can only perform a second split on the larger tree.
6) Though the value of each node can fit in an int, don't forget that there can be 50000 nodes. The sum of all nodes will need a long.
Please don't follow up with a "here's my code" post.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Balanced Forest
You are viewing a single comment's thread. Return to all comments →
This was a fun problem. A few tips to help you get started...
1) The input for the "tree" is an undirected graph. There is no parent/child relationship implied. The edges are not ordered in any meaningful way. So you might get 1-2, then 3-4 (which looks like 2 separate collections) and finally get 4-2. This would create a graph like 1-2-4-3. Where's the root? It doesn't really matter. Imagine grabbing any node, and letting the others hang-down. You are assured that once connected, all of the nodes create a single graph (with no loops/cycles) - so by picking any node as root, you have a tree. I suggest that after the graph is built, you might want to choose a root and establish parent/child relationships in your tree.
2) In case it wasn't clear, this is not a binary tree. Any node can have many children. (Example: Every node in the tree could be connected to node 3 with input like 2-3, 3-1, 4-3, 3-5. This is still a tree, and any node could be root.)
3) The number of "coins" at the given nodes is >= 1, but the number of coins added in the final node (node cw) is >= 0 ("any non-negative integer")
4) The wording of the problem indicates that you add node cw and then make 2 cuts. But you don't know where you will have to add. You could have a case where you split the existing tree in half and the added node forms the 3rd tree. To avoid worrying about these cases, you can create a dummy node with 0 coins as a leaf node (only 1 connecting edge). Now, with 2 cuts, it's possible to have one of the trees as empty. Then you can "add" cw where needed to balance the trees.
5) To get started on an algorithm, consider what would happen if you iterate through the tree, trying to cut each edge. As you cut an edge, you have 2 trees. Since you can only add (not subtract) coins to achieve the final balance, we would need two equal larger trees, and one smaller (or equal) tree. Given this, with 2 trees, we can only perform a second split on the larger tree.
6) Though the value of each node can fit in an
int, don't forget that there can be 50000 nodes. The sum of all nodes will need along.Please don't follow up with a "here's my code" post.