sky_full_of_stars's blog

Need help with resolving TLE on Dijkstra.

By sky_full_of_stars, history, 4 years ago, In English

Hi All,

I was trying to solve this using Dijkstra.

Solution here.

I'm getting TLE in the last few test cases. Can someone suggest me any further optimizations I can make?

thanks! have a good day!

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

Comments Comments (11)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -53 Vote: I do not like it

[DELETED]

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +25 Vote: I do not like it

    No proper question will use this optimization as a solution.

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

      i am just a beginner,i was just trying to help with the relatively little information i had that's all.

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

        Ah, I see. However, this trick should only be used as a crutch when your solution barely doesn't pass the TL.

        For practice sessions however, I would recommend avoiding this command, as it usually doesn't help you learn how to properly optimize your code

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          i understand, i only started CP a few weeks ago. so it's a pretty good opportunity to learn optimization techniques.

          → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Your code actually runs in $$$O(\sum deg_i \cdot K_i)$$$. This is due to the addWaitingCost(node, time) code having $$$O(K_{node})$$$ complexity, and you calculate this value $$$O(deg_i)$$$ times for each vertex.

An alternative idea will be to calculate addWaitingCost(node, time) when you reach a node and add the value to the current distance. This will be optimal as the faster you reach a node, the faster you can exit out of that node.

Whilst this might seem slow at first, this will have an amortized complexity of $$$O(\sum K_i)$$$, since you compute the value only once for each vertex.

I would recommend reading the tutorial of the contest if you are stuck.

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

    Even this approcah TLE'd on same testcase :(

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

      Problem of modified code next: let's we can come to vertex $$$v$$$ at times $$$t_1 < t_2 < t_3 < \cdots < t_d$$$. Right code would process only pair ($$$v$$$, $$$t_1$$$) and skip all others. For that reason you have next line of code:

      if (curDist > dist[curNode]) continue;

      And it is correct line of code. Correct, but not in your case. That condition assumes that $$$dist[curNode] == t_1$$$, but later in dijkstra you update $$$dist[curNode]$$$:

      dist[curNode] += addWaitingCost(curNode, curDist);

      And it breaks all! There could be test where $$$t_1 < t_2 < t_3 < \cdots < t_d < t_1 + waitingCost$$$. Because of that you'll actually process all pairs ($$$v$$$, $$$t_1$$$), ($$$v$$$, $$$t_2$$$), ($$$v$$$, $$$t_3$$$), ..., ($$$v$$$, $$$t_d$$$) — and it would be TL.

      It could be easily fixed by updating $$$curDist$$$, not $$$dist[curNode]$$$:

      curDist += addWaitingCost(curNode, curDist);
 
for (pi& child : gp[curNode])
{
	int to = child.ff;
	int w =  child.ss;

	if (dist[to] > curDist + w)
	{
		dist[to] = curDist + w;
		//dist[to] += addWaitingCost(to, dist[to]);
		pq.push({dist[to], to});
	}
}

      Full AC version of code

      P.S.

      You had very strange output:

      (dist[n] >= INF) ? (cout << -1 << endl) : (cout << dist[n] << endl);

      I think that this version a bit more convenient:

      int ans = (dist[n] >= INF ? -1 : dist[n]);
cout << ans << endl;
      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I solved this problem a few months ago, and used two binary searches.

  • First binary search is used to find whether you will queue or not. That is, for example, if you arrived at planet x at time t, does planet x have a traveler that is planning to travel at exactly time t? (This is equivalent to a classic binary search of finding whether an exact value exists in an array). Obviously, if the element doesn't exist, then you don't have to find a suitable time t`. Otherwise, we do another binary search.
  • Second binary search is then used to find the "smallest missing number" t`(an open space for you to travel) in planet x where the lower bound is the time that you arrived in that planet (again, a classic binary search technique, just google "find smallest missing number, binary search").

Haven't read the editorial for this problem, but this is how I solved it, at least.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Just use Dijkstra's algorithm to find shortest path from node 1 to any node and while on a node just wait till the current node is "OK" to go. You can simply find the first time after you reach it which is "OK" to go, just this can be done just by simply traversing the arrival list at that node.

See my implementation for more details:

Solution

PS:By "OK" I mean you can go from that node after all consecutive arrivals gone.

Sorry for my English.

→ Reply