Infoshoc's blog

By Infoshoc, history, 6 weeks ago, In English

When I was a little child I learned a lot (indirectly via the website which also have a community-driven english transation) from e-maxx.(Orz).

In particular, there is a post about Dijkstra on sparse graphs (English version. It is mentioned there that priority_queue is based on heaps, thus has smaller hidden constant then set which is based on RB-trees. Explanation makes perfect sense.

I got back from quite a long break from CP and checked the recent Educational Codeforces Round 102 (рейтинговый для Див. 2) for a warm up. There was a nice problem 1473E - Минимальный путь authored by Neon which required Dijkstra's algorithm. So I used the priority_queue based one from my template 105061903 and got TLE 61. I thought of several bad words and started to optimize. Eventually, I tried the set-based solution and got AC 105066945. For your convenience, there is a diff between the submissions:

Is it some other hidden bug in my code, or is set-based Dijkstra works faster then priority_queue one? When and why?

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Uh, the two submission links are the same link. I thought that one of them was supposed to be TLE and the other is AC. Maybe link this one instead https://codeforces.com/contest/1473/submission/105061903

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Reverse happened with HealthyUG.His solution using set TLEed and priority queue worked. Here are submissions
With set(TLE): https://codeforces.com/contest/1473/submission/104326547
with pq (AC) : https://codeforces.com/contest/1473/submission/104327939

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This only the internal set VS PQ constant changes. Usually, when one codes Dijkstra with sets the old distance is removed from the queue on the update, and some memory is saved.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Yes that's right. Priority Queue method can be made faster though — make a custom comparator which compares only the first element of the pair. (It improves the constant factor by a lot in the worst case)

»
6 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

You should check after popping if the current minimum distance to this node equals to the one popped, since a node can be popped multiple times if you use priority_queue and if you process each one it'll result in wasting a lot of time. For example, look at my code without checking 105069884 and with checking 104306045

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh actually nvm you do that, then I don't know what causes your TLE.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +23 Vote: I do not like it

      He don't do it in a proper way: 105071086, without your comment I've never noticed this bug :)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, and I lived with this bug in the template! Thanks a lot!

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, I know this fill bro, some bugs are really hard to notice, they live in template even after N >> 1 AC submits. I've recently found bug it my Modular class: comment

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          This shows how bad it is to use pairs instead of classes with proper field names and comparator.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Infoshoc (previous revision, new revision, compare).