### LouisCK's blog

By LouisCK, 6 years ago, ,

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!

• +3

 » 6 years ago, # | ← Rev. 3 →   0 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): 65535[?] 3 0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 4 ... 4 [16 numbers] 5 5 ... 5 [32 numbers] ... 14 14 ... 14 [16384 numbers] 15 15 ... 15 [32768 numbers] For example, each node in distance 14 will try to traverse the list of vertices in distace 15 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: either for each distance keep an eye on the next element in the ArrayList that is to be visited (if there is any), or remove each visited element from LinkedList (removeFirst() method, which also returns the first element, should do the trick).
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 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 to ArrayList 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
•  » » » » 6 years ago, # ^ |   0 Thanks for your effort!This is strange! I submitted the same code in Java 7 that failed in Java 8 and it passed! It's also 20% faster, as you said. :S