WayBig's blog

ABC305 Problem E: Why is this code giving TLE?
By WayBig, history, 10 months ago, In English

In today's ABC305, I used multisource BFS to solve problem E. But it is giving TLE. Can anyone please point out the mistake? Moreover, an almost similar question also happened to appear in Codechef STARTERS 93. And an almost similar code, written by me, got accepted in it.

Problem Link: https://atcoder.jp/contests/abc305/tasks/abc305_e

Solution Link: https://atcoder.jp/contests/abc305/submissions/42175490

Code
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Consider a simple linked list as an example: 1 — 2 — 3 — ... — n. Lets say, there is a security guard at each node, and the max_distance, the ith guard can cover is i. If the indices of the guards are given in increasing order of the maximum distances they cover. You will push elements in the order: 1, 2, 3, ... n, in the queue.

Then, for the ith node in the queue: you will be visiting all the nodes from (1, 2, ... i). Hence this is too slow and bound to give TLE.

Try to use multi-source dijkstra instead.

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

    But why dijikstra what are we gonna minimise here , isnt we just need to minimise the stamina of guard at each level by 1 if possible

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The main issue with the BFS approach is that you could be updating a node multiple times and in worst case, order of updates could be quadratic, as in the above (linked list) example.

      Think of dijkstra as a way of picking the best node from those present in the queue (the one with the maximum remaining distance in our case), instead of just doing FCFS like BFS. It will ensure that when a node is selected from our queue it has the maximum remaining_distance this node will ever have, i.e., no other node will update the remaining_distance of the current node. This solves the time complexity issue. Read more about it in the proof here: link

      You can implement dijkstra to maximize the remaining_distance of a node.

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

        Thanks! I reviewed the proof and your example and understood the reason for TLE.

        Just one more thing: according to proof of Dijkstra, why even do we ever need a queue? Can't we just use priority_queue in every question of BFS, 0-1 BFS, or Dijkstra? With just an extra logV complexity we can solve any question without worries of getting TLE.

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

          Well, I don't really think I am smart enough to comment on an approach for all problems in general. Maybe some higher rated coder will respond to your query.

          However, I think you shouldn't think so less of this extra logn. There are a lot of problems where an extra logn results in a TLE. For example if the expected time complexity of a question is O(nlogn), in most cases the constraints are such that O(nlog^2n) fails.

          There could be a question where you have to perform a BFS inside a binary search. If you use dijkstra there, most likely your solution will TLE.

          → Reply