ahmadexe's blog

Why giving TLE?
By ahmadexe, history, 4 months ago, In English

So I am a newbie in DFS and BFS, and was solving this problem. Surprisingly, giving TLE in 3rd testcase. I can't seem to understand where code is inefficient since time complexity is looking fine to me.

I have added some comments, which don't use the ideal terminologies but would hopefully convey what I'm trying to do

https://codeforces.net/contest/1948/submission/267884593

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

I modified 3 things in your code and got Accepted. 1- I added a condition to check whether the variable s is out of the grid (aka s < 0 || s >= n) 2- Instead of 5 conditions to check whether the new position the robot is gonna move to is visited or not, I used one condition after the "q.pop()" line to handle the visited cases alongside with the "out of the grid" cases. 3- last but not lease, instead of marking the element visited[f][s][t] as visited, you only need to mark the element visited[f][s][0] as visited; not the visited[f][s][1]. That's because in case you reached a position with t = 1, it does not matter whether it is visited or not, cos the robot is going to follow the arrow nevertheless.

Here's the new submission: https://codeforces.net/contest/1948/submission/267898619

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

    Thanks alot for your explanation. Works now

    → Reply