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

Help needed for CSES problem Labyrinth, Getting TLE
Автор normal_cf_user, история, 5 дней назад, По-английски

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

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

»
5 дней назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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:
→ Ответить
  • »
    »
    5 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

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

      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

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

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.

→ Ответить