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 problem is, quite frankly, horrible. There are so many potential solutions you can have an algorithm come up with for connecting subgraphs that you would actually need a separate program to be 100% sure that the output given is correct or incorrect, and thus the entire evaluation of your answer simply does not work right in this format.
If you truly feel the need to torment yourself with this, here's what your program needs to accomplish:
Traverse the graph to determine how many subgraphs there are. O(n)
Color each subgraph so that the difference between white nodes and black nodes is minimized. O(n)
Add 1 fewer edges than there are subgraphs, ensuring that each edge connects a white node and a black node. O(n) worst case
Return the difference between white and black nodes, the number of edges you added, and the endpoints of each added edge.
Fix the way the given program outputs text because it does not do it in the way the problem says it should.
That last step is VERY IMPORTANT to note, as it shows you can't trust the expected outputs are correct. You're going to have to do a lot of debugging with the hidden test cases, because in the end having correct results from this problem may not be the same thing as having a program that achieves the stated goals of this problem.
Edit: after unlocking the editorial, you get to see that either essential information regarding the input constraints is missing from the problem, or the editorial is incorrect in its assumptions. The editorial claims that the minimum absolute difference in node colors will remain fixed even if subgraph colors are inverted -- this is patently false unless those are constraints that are not included in the problem description. If you have two (or more) subgraphs that consist of a single node connected to many other nodes, inverting the colors can change the minimum absolute difference drastically! A graph of 1 black node and 10 white nodes connected to an identical graph would have a minimum absolute difference of 18 (20 white - 2 black), whereas if it is connected to an identical graph with inverted colors the minimum absolute difference is 0 (1 white and 10 black cancels out 1 black and 10 white)!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Black and White Tree
You are viewing a single comment's thread. Return to all comments →
This problem is, quite frankly, horrible. There are so many potential solutions you can have an algorithm come up with for connecting subgraphs that you would actually need a separate program to be 100% sure that the output given is correct or incorrect, and thus the entire evaluation of your answer simply does not work right in this format.
If you truly feel the need to torment yourself with this, here's what your program needs to accomplish:
Traverse the graph to determine how many subgraphs there are. O(n) Color each subgraph so that the difference between white nodes and black nodes is minimized. O(n) Add 1 fewer edges than there are subgraphs, ensuring that each edge connects a white node and a black node. O(n) worst case Return the difference between white and black nodes, the number of edges you added, and the endpoints of each added edge. Fix the way the given program outputs text because it does not do it in the way the problem says it should.
That last step is VERY IMPORTANT to note, as it shows you can't trust the expected outputs are correct. You're going to have to do a lot of debugging with the hidden test cases, because in the end having correct results from this problem may not be the same thing as having a program that achieves the stated goals of this problem.
Edit: after unlocking the editorial, you get to see that either essential information regarding the input constraints is missing from the problem, or the editorial is incorrect in its assumptions. The editorial claims that the minimum absolute difference in node colors will remain fixed even if subgraph colors are inverted -- this is patently false unless those are constraints that are not included in the problem description. If you have two (or more) subgraphs that consist of a single node connected to many other nodes, inverting the colors can change the minimum absolute difference drastically! A graph of 1 black node and 10 white nodes connected to an identical graph would have a minimum absolute difference of 18 (20 white - 2 black), whereas if it is connected to an identical graph with inverted colors the minimum absolute difference is 0 (1 white and 10 black cancels out 1 black and 10 white)!