LouisCK's blog

How do I optimize my solution for Restore Graph? (404 — C)
By LouisCK, 10 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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).
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply