Try graphviz.
1 Like
Thank you very much !
It is exactly what is needed 
I think I found a rigorous solution (ie it works for all tests) but I am not sure it can be proven exact. However it works and its all that matters.
My method for searching is a BFS starting from each node, keeping the id responsible for the lowest hours in memory. the problem is that for some tests (test 1 for example) node 1 and 2 give the same hours (two hours) ā¦ my program outputs id:1 while the expected output is id:2 ā¦ how am i supposed to decide on this ?
Maybe the answer is the number of hours.
absolutely, it was thatā¦ i changed that and got 100%! im happy
Maybe Magusās solution used to work and the test has changed? In any case, it no longer works. The node ids may now start at zero, and the larger problem is that the nodes are not guaranteed to be numbered consecutively. With the inputs on test case 10, the nodes are numbered 0 to 10 and 13 to 15. (11 and 12 are missing.)
This solution did help me solve all test cases except 10 (instead of timing out on 8 and 9). But where my previous solution worked on 10, this now fails. sigh
So I am still struggling (in Java) to figure out a way to build the graph, ensure the uniqueness of the node IDs, and not time out in the building the graph portion. (My algorithm itself seems to be fast enough).
Iām also curious about all the mention of BFS. I saw this as a longest path problem, so Iām doing two DFS to find the longest path then returning the ceiling of longestPath / 2. Any thoughts on whether a BFS from every node is more or less efficient than two DFS?
Oh hey, I think maybe I figured it out. Thank you for your help, Magus!
My solution involved using two sets as it initialized the data in python. Then it removed all the nodes that appeared only once. (The purpose of the two sets). Incremented count. Repeat the process on the remaining nodes. Solved case 8 and 9 pretty quickly this way.
4 Likes
I reached the same solution - a āreverse BFSā starting from the leafs.
With the reverse BFS, you can still use only one queue (as usual for BFS), with O(n), assuming max number of links for any node is much smaller than total number of nodes.
In the provided test cases, it creates a very fast solution indeed
The problem is well-defined and has a textbook solution, only issue is that timeout is too harsh for high level langs.
Iāve had to jump through hoops to get Python version working, but C++ worked fine with the solution youād expect.
If anybody solved it with BFS on Python, Iād be really interested in hearing how.
I solved it with a BFS in Python but I carefully start the algorithm with the right nodes.
1 Like
i use python and hashes only but i end up with 70% 
i check for every point that has at least 2 connections wether it is the one with the best connection but i dont know what to improve
I solved it with Python 100% by trimming nodes. When I posted about trying to run two bfs to solve, I kept timing out as well, but someone posted some code that does in fact run two bfs without timing out on even the largest cases, so it is definitely possible.
Hi,
I solved the puzzel with Java 100%, all 10 tests pass.
BUT in the validator it is not making test 6. All other validation tests are passt.
I gues its no timout becouse 8 and 9 is passed.
Has somone help me with an idea what could be wrong, or a custom test that demonstrates the problem in validation test 6?
Hi,
i have the same problem, all puzzles complete without error, but the validator complains about test 6. I have no idea how to find the error, because there are no error messages and i donāt know the input values. Has anyone a hint how to find out why test 6 went wrong?
Please help, i am desperate!
Thanks in advance!
Hi,
same problem here, 100% in ide and test 6 fails in the validator.
Can you explain what solution you implemented?
EDIT:
My solution is something like:
- take a node at random
- find the farthest leaf of the graph from that node
- find the farthest leaf from the leaf you just found
- the distance between the two, halved, is the solution (you may have to do (value + 1) / 2 tho)
My code:
class Node {
- public final List linkedNodes = new ArrayList();
- private int distanceFromEndOfGraph;
- private Node furthestNode;
}
I have an array of nodes that store them by id (id is what is given as input at the beginning)
For each links (pair of node ids) given as input,
I get the node from the array (or create a new node in the array if the node doesnāt exists yet)
and I add each node to the list of linkedNodes of the other node
thatās it for init.
Note that the array as a size of 200 000 (max id possible), since they, sometimes, ignore certain ids (so the amount of links given as input may be lower than the biggest id given)
that way, for any node, I can go through the entire graph, using the linkedNodes
I take a random node (I actually take the first one given as input)
I call a method called floodFill that recursively sets distanceFromEndOfGraph for all nodes:
- if a node is a leaf, the value is 0
- then the value set is 0 + i, i being the distance from the leaf
- when you have a choice between two values (or more, ie when a node has three or more linked nodes) you set distanceFromEndOfGraph with the higgest value (we only care about the farthest leafs)
the goal is for each node to know how far they are from the farthest leaf
I then call a method that gives me the farthest leaf from a node (using the previously computed distanceFromEndOfGraph)
so now I have the farthest node from the starting node
you then have to call floodFill on this farthest node.
the value of this nodeās distanceFromEndOfGraph after the floodFill is the distance to the farthest leaf, which you then have to divide by 2 to get the answer.
I donāt know if the answer is clear enough, hope it can help someone.
I tried to not give too many details, so you still have to actually implement the solution 
1 Like
I am getting a strange error. For the code:
for node, links in G.iteritems():
I get the error:
AttributeError: 'dict' object has no attribute 'iteritems'
Why does it think iteritems is an attribute?
Because a method is an attribute that has the special _call_ method.