Editorial for DMOPC '15 Contest 3 P4 - Contagion

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: cheesecake

Knowledge required: Dijkstra's algorithm, binary search.

The given graph is a complete graph, where the countries are the vertices and the infection times are the edges. The number of countries infected at a given hour is the number of vertices with a shortest path \le Q_i from the source.

Note that on a complete graph, both priority queue Dijkstra's and SPFA will time out at their worst case complexities. The correct solution uses "classical" \mathcal{O}(N^2) Dijkstra's to find the shortest path to every country. After sorting the array containing the shortest paths, we can binary search to find the answer to each query.

Time Complexity: \mathcal{O}(N^2+Q \log N)

Bonus: What is the worst case complexity of priority queue Dijkstra's and SPFA on a complete graph? Why?

Comments


  • 2
    Dingledooper  commented on Jan. 28, 2020, 1:52 a.m. ← edited

    In fact it's possible to pass all the cases using the C++ priority_queue, by encrpyting the node stored in the queue, and using fast input and output.


    • 2
      wleung_bvg  commented on Jan. 28, 2020, 8:23 a.m.

      Why do it in C++ when you can do it in Java!

      If you use an Indexed Priority Queue, which allows for modifications of a key, it is possible to reduce the runtime of Dijkstra's from \mathcal{O}(E \log E) to \mathcal{O}(E \log V) where V is the number of vertices and E is the number of edges. Since E \in \mathcal{O}(V^2), this doesn't seem like a huge improvement (in theory it's at most a constant factor of 2); however, given how close the time limit is, and the fact that implementing most data structures yourself in Java often leads better performance than using the built-in data structures, the difference is noticeable (in fact, I was unable to get a solution to pass without this optimization).


      • 0
        Dingledooper  commented on Jan. 28, 2020, 11:53 p.m.

        You're right, using Java's built-in PriorityQueue would TLE, unless you use SPFA, that is. Contrary to what the editorial says, even an unoptimized SPFA + built-in priority-queue implementation easily passes all the cases, at least in C++, Java, and PyPy :(


  • 4
    Ninjaclasher  commented on June 17, 2017, 3:14 p.m.

    Can someone explain why you would use Dijkstra's in the first place? Why wouldn't you just find the direct distance between the source of the outbreak and each country? Wouldn't that always be the shortest distance?


    • 13
      wleung_bvg  commented on June 17, 2017, 5:26 p.m. ← edit 4

      While calculating the direct distance would be the shortest distance, the time it takes for the disease to spread is equal to the shortest distance squared. Consider 3 points at (0, 0), (0, 3), and (0, 4). Although the distance between points (0, 0) and (0, 4) is 4, the time is not 16. It is equal to the distance squared between (0, 0) and (0, 3) plus the distance squared between (0, 3) and (0, 4) for a total of 10.


  • 1
    mpsbotelho  commented on Dec. 9, 2015, 1:28 p.m. ← edited

    Why using dijkstra with priority queue gives TLE?


    • 3
      jeffreyxiao  commented on Dec. 9, 2015, 2:06 p.m. ← edit 2

      Using a binary heap, the time complexity of Dijkstra's is \mathcal{O}(E \log V). Since the graph can be a complete graph, the worst case of Dijkstra's is \mathcal{O}(V^2 \log V).