normal_cf_user's blog

Help needed for CSES problem Labyrinth, Getting TLE
By normal_cf_user, history, 3 days ago, In English

In the problem CSES-Labyrinth I have written a simple BFS solution but still getting TLE , The solution is O(N*M) solution means it should work fine , but don't know why I'm getting TLE. Any Help is appreciated.

My Submission : Here

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

From what I can see, you are storing the path for each iteration of the BFS in the queue. Since the maximum path length can be N*M and u are pushing each such path into the queue, the worst case tc is actually O((N*M)^2).

A hint:
→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the help, I agree that the max path can be N*M indeed but by pushing such path into queue how the tc will become O((N*M)^2) ? can you explain ?

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

      because pushing a string of length x to the queue itself will be an O(x) operation, the reason being the entire length of the string needs to be copied

      → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you have overcomplicated here you are storing the path at each point leading to TLE here i think here you can use the bfs, here you just need to store a boolean vector for visited and you need to store the parent value also so that you can trace the path. The point here is we know that the bfs always gives the shortest path as soon as we reach the ending point we will simple backtrack through the parent in order to the get the path.

→ Reply