Gagandeep98's blog

CSES Graph Algorithms Monsters
By Gagandeep98, history, 5 years ago, In English

It is becoming very common that I am failing some of the test cases of CSES problems. I am getting WA on 3 out of 17 test cases. I am unable to figure out what is wrong in my approach.

Logic:

Step 1: Apply BFS for all monsters. Store in dist array, dist[i][j], shortest time among all monsters to reach, coordinate (i, j).

Step 2: Apply BFS for A. Store in d array, shortest time from A to coordinate (i, j). It is only possible to reach that coordinate if d[i][j] < dist[i][j]. Check if we have reached the border.

Step 3: Backtrack to generate the path.

PROBLEM LINK CODE LINK

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

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

update the size of dist and d matrix to 1001 as the constraints are n<=1000 and m<=1000.

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Since you have done this problem can you let me know why is the answer for this test case NO

4 4

hash hash hash hash

dot dot A hash

hash dot hash hash

hash M hash hash

My code gives the answer as:

YES

2

LL

Update: I got it... I was looking at wrong output.

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

Can anyone help me why I am getting TLE for the below code. https://cses.fi/paste/48434fbc6c787d57222ddb/

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

    Changed lines 82 and 88. As you were initializing ans = path[x][y] + ans, you were actually creating the ans string every time you reinitialized it (which caused the TLE as it O(len ^ 2)). But if you do it with the help of shorthand method ans += path[x][y] and then reverse it finally, the compiler optimizes to O(len) in total and hence we can avoid TLE;

    Code
    → Reply