You are not logged in. Please login at www.codechef.com to post your questions!

×

TLE in Tourists in Tourists in Mancunia jan long challenge

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.

asked 26 Jan '17, 12:57

arpit728's gravatar image

1★arpit728
6831562
accept rate: 10%

edited 14 Feb '17, 13:04

admin's gravatar image

0★admin ♦♦
19.7k350498541


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.

link

answered 26 Jan '17, 15:51

meooow's gravatar image

6★meooow ♦
7.0k718
accept rate: 48%

edited 27 Jan '17, 15:09

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);
    }
}
link

answered 26 Jan '17, 13:42

bansal1232's gravatar image

5★bansal1232
2.8k1418
accept rate: 16%

@bansal1232 can you suggest any.

(26 Jan '17, 13:54) arpit7281★

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

(26 Jan '17, 14:13) bansal12325★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,197
×715
×73

question asked: 26 Jan '17, 12:57

question was seen: 676 times

last updated: 14 Feb '17, 13:04