TLE in Tourists in Tourists in Mancunia jan long challenge

general
, ,
1

This is my solution for Tourists problem in January long challenge and I am getting TLE in one test case. I am not able to figure out why I am getting TLE. Can anyone help me with this.

2

The problem is the with findTour function! Here the removing index takes a O(n) in worst case (n=size of container). Optimize this with data structure that takes log(n) complexity.

private static void findTour(int u) {
    int v=0;
    for (int i = 0; i < adj[u].size(); i++) {
        v=adj[u].get(i);
        adj[u].remove((Integer)v);
        adj[v].remove((Integer) u);
        tour.add(new Edge(u,v));
        findTour(v);
    }
}
3

@bansal1232
can you suggest any.

4

U can use Treeset<>! It can perform insertion and deletion in Log(N) time

5

Hey @arpit728, although @bansal1232 is right about using a Set rather than an ArrayList, that will unfortunately not be enough to give you AC. I messed around with your code, and it seems that the bottleneck lies in the way you’re storing the correct edges. See this submission here, I have replaced your findTour with a simple loop that adds all edges to tour as they are, and it still gives TLE. It appears that storing at most 200000 edges in a HashSet and querying it 200000 times is not a good idea.

private static void findTour(int u) {
    int v=0;
    for (int i = 0; i < adj[u].size(); i++) {
        v=adj[u].get(i);
        adj[u].remove((Integer)v);
        adj[v].remove((Integer) u);
        tour.add(new Edge(u,v));
        findTour(v);
    }
}

Also I should mention that this code snippet above will NOT do what you want, because you are concurrently modifying the ArrayList. At i=0 you delete the 0th element, after which all elements get shifted to the left. The 1st element becomes the 0th element now. As you now do i++, the 2nd element (now at the 1st position) is what you will move on to. It is clear that you skipped an element. So the loop will just check half of the total number of edges in the adjacency list.

To avoid this situation you can make just one copy of each edge, and always deal with that by using a reference to it in the adjacency lists. That eliminates the need of a HashSet and also there is no need to remove edges from any adjacency list. This is my solution, which is one way to implement this. Feel free to ask if you don’t understand any part of the code.

1 Like