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

Автор Gagandeep98, история, 4 года назад, По-английски

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

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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.

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

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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