Блог пользователя sky_full_of_stars

Need help with resolving TLE on Dijkstra.

Автор sky_full_of_stars, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится -53 Проголосовать: не нравится

[DELETED]

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

    No proper question will use this optimization as a solution.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

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

          → Ответить
»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Even this approcah TLE'd on same testcase :(

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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;
      → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить