This is my solution to this problem Restore Graph. I have used an approach which seems similar to that suggested in the editorial (which I translated from Russian) but I can't really understand it. Here's what I have done
1) Created a HashMap that maps distances from roots to nodes. For example, if I put in map[1], it will give me a list of nodes that are at distance 1 from the root.
2) Start from the root vertex for which D[start] = 0. I do a DFS search from the root. For each node, which is at distance dist, I check for neighbours that are at distance dist + 1 and visit only k of them if not already visited. Each time I visit another node, I add (current_node, neighbour) to the answer set.
3) That's about it. At the end, I check if the size of the visited map is not equal to n, then output -1. Otherwise I output the answers.
I am getting TLE on the 7th test case which has a considerable input size and I am using Java 8. Is my algorithm too slow or is it because of the language?
Thanks!
Java is usually not too slow for programming contests (if you care about doing in/out correctly).
You have a problem with a
DFS
routine — some LinkedLists of distances may be traversed very many times. Consider the following test (I broke the second line):For example, each node in distance
14
will try to traverse the list of vertices in distace15
from root; first one will check 2 numbers, the second one — 4 (two first were already considered), next one — 6 and so on. The last one will have to check 32768 elements! It's not hard to compute 2+4+6+...+32768 — it's quite large. And we considered only one level!I see two things you can do now:
removeFirst()
method, which also returns the first element, should do the trick).Thanks for the great advice! I used
removeFirst()
now each time I visit a node. It passed the test cases that I was previously failing in (#7), but now it is failing #19 and sometimes even #17 or #18. My submission is here. I seem to be using an algorithm that is too slow, is it? Because people have used Python 3 and passed the tests comfortably.The algorithm is not too slow. Maybe it's because you used the tools (e.g.
HashMap
) which usually have a quite large time constant, not only in Java. I'm rather a C++ user, so I'm not able to tell you what is the best way to go for you.However, I've rewritten the code a bit (the biggest mods are changing
HashMap
toArrayList
and moving some variables to the class definition so that DFS becomes only a 2-parameter routine) and I barely passed in Java 8 (7613045). What is more interesting is that Java 7 and 6 seem to be about 20% faster here... (Java 7: 7613048, Java 6: 7613049). I'm probably not the one who can tell you why this happens... :P