Gagandeep98's blog

By Gagandeep98, history, 14 months ago,

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.

• 0

 » 14 months ago, # |   +3 update the size of dist and d matrix to 1001 as the constraints are n<=1000 and m<=1000.
•  » » 14 months ago, # ^ |   0 Yes, it was very silly of me. Thanks
 » 7 months ago, # | ← Rev. 4 →   0 Since you have done this problem can you let me know why is the answer for this test case NO4 4hash hash hash hash dot dot A hashhash dot hash hashhash M hash hashMy code gives the answer as:YES2 LLUpdate: I got it... I was looking at wrong output.
 » 2 months ago, # |   0 Can anyone help me why I am getting TLE for the below code. https://cses.fi/paste/48434fbc6c787d57222ddb/
•  » » 2 months ago, # ^ |   +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#include using namespace std; char s[1005][1005]; char path[1005][1005]; int n , m; bool isBoundary ( int x ,int y) { return (x ==0 || x==n-1 || y == 0 || y == m-1); } bool isValid( int x , int y) { return ( x>=0 && x=0 && y> n >> m; int x1 = 0 , y1 = 0; queue < pair > q; for (int i = 0 ; i < n ; i++) { for (int j = 0 ; j < m ; j++) { cin >> s[i][j]; if(s[i][j] == 'A') { x1 = i; y1 = j; } else if(s[i][j] == 'M') { q.push({i,j}); } } } q.push({x1,y1}); if(isBoundary(x1,y1)) { cout << "YES" << endl; cout << 0 << endl; return 0; } while(q.size()) { int x = q.front().first; int y = q.front().second; q.pop(); if(s[x][y] == 'M') { if(isValid(x+1,y)) { s[x+1][y] = 'M'; q.push({x+1,y}); } if(isValid(x-1,y)) { s[x-1][y] = 'M'; q.push({x-1,y}); } if(isValid(x,y-1)) { s[x][y-1] = 'M'; q.push({x,y-1}); } if(isValid(x,y+1)) { s[x][y+1] = 'M'; q.push({x,y+1}); } } else if(s[x][y] == 'A') { if(isBoundary(x,y)) { string ans; while(x!=x1 || y!=y1) { ans += path[x][y]; if(path[x][y] == 'D') x--; else if(path[x][y]=='U') x++; else if(path[x][y]=='R') y--; else y++; } reverse(ans.begin(), ans.end()); cout<<"YES"<< endl; cout<
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anyone help me why I am getting TLE for the below code https://cses.fi/paste/a391ee7c282f459d24732d/ (test case 19)Problem Link: https://cses.fi/problemset/task/1194/