### Sumanto's blog

By Sumanto, 12 months ago,

https://cses.fi/problemset/task/1625 I am applying staright forward DFS to the problem but it's getting Time Limit Exceeded. How to optimise the code. I checked out William Lin's Livestream but did'nt get his approach to the problem

• +5

 » 11 months ago, # |   0 https://cses.fi/book/book.pdf page 52 (the printed page number) or 62 (the pdf page number)
•  » » 11 months ago, # ^ |   0 thanks
•  » » 10 months ago, # ^ |   0 i understood the optimisations, but can you explain the runtime mathematically? the explanations there looks more experimental.
 » 10 months ago, # |   0 Can anyone with a sharp eye help me please? I basically tried “to go by the the book”, and do the pruning of the T-shaped wall hits, — just as @tmwilliamlin168 does for this problem in his epic 11-hour stream.Still, however, I'm getting 30+ seconds on the all-question-marks 88418 paths case. What am I missing? I tried to code it up in a clean way, so you probably won't have any trouble following the logic.Thanks! The code#include using namespace std; static constexpr int RO_MAX = 6; static constexpr int CO_MAX = 6; static constexpr int DEST_I = (RO_MAX + 1) * (CO_MAX + 1) - 1; static constexpr pair DEST_COORD{RO_MAX, 0}; template constexpr pair operator+(const pair &lhs, const pair &rhs) { return {lhs.first + rhs.first, lhs.second + rhs.second}; } constexpr pair delta(const char dir) { switch (dir) { case 'U': return {-1, 0}; case 'D': return {1, 0}; case 'L': return {0, -1}; case 'R': return {0, 1}; default: assert(false && "Invalid direction char"); return {0, 0}; } } constexpr bool in_bounds(const pair &coord) { const auto [ro, co] = coord; return ro >= 0 && ro <= RO_MAX && co >= 0 && co <= CO_MAX; } constexpr bool is_possible(const vector> &covered, const pair &coord) { const auto [ro, co] = coord; return in_bounds(coord) && !covered[ro][co]; } int matching_paths_count(const string &pattern) { vector> covered(RO_MAX + 1, vector(CO_MAX + 1, false)); covered[0][0] = true; int ans = 0; function)> recur; recur = [&recur, &pattern, &ans, &covered](const int i, const pair &coord) { if (coord == DEST_COORD) { if (i == DEST_I) ++ans; return; } for (const auto dir : pattern[i] == '?' ? string("UDLR") : string(1, pattern[i])) { const auto coord_prime = coord + delta(dir); if (!is_possible(covered, coord_prime)) continue; if ((dir == 'U' || dir == 'D') && !is_possible(covered, coord_prime + delta(dir)) && is_possible(covered, coord_prime + delta('L')) && is_possible(covered, coord_prime + delta('R'))) continue; if ((dir == 'L' || dir == 'R') && !is_possible(covered, coord_prime + delta(dir)) && is_possible(covered, coord_prime + delta('U')) && is_possible(covered, coord_prime + delta('D'))) continue; covered[coord_prime.first][coord_prime.second] = true; recur(i + 1, coord_prime); covered[coord_prime.first][coord_prime.second] = false; } }; recur(0, {0, 0}); return ans; } int main() { string s; cin >> s; cout << matching_paths_count(s) << '\n'; return 0; } 
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 I've shaved off about 50% of time by removing all that pairs instantiations. Still not good enough. 16 seconds on the 88418 paths case. Help! Version 2#include using namespace std; static constexpr int RO_MAX = 6; static constexpr int CO_MAX = 6; static constexpr int DEST_I = (RO_MAX + 1) * (CO_MAX + 1) — 1; static const string ALL_DIRS{"UDLR"}; constexpr pair delta(const char dir) { switch (dir) { case 'U': return {-1, 0}; case 'D': return {1, 0}; case 'L': return {0, -1}; case 'R': return {0, 1}; default: assert(false && "Invalid direction char"); return {0, 0}; } } constexpr bool in_bounds(const int ro, const int co) { return ro >= 0 && ro <= RO_MAX && co >= 0 && co <= CO_MAX; } constexpr bool is_possible(const vector> &covered, const int ro, const int co) { return in_bounds(ro, co) && !covered[ro][co]; } int matching_paths_count(const string &pattern) { vector> covered(RO_MAX + 1, vector(CO_MAX + 1, false)); covered[0][0] = true; int ans = 0; function recur; recur = [&recur, &pattern, &ans, &covered](const int i, const int ro, const int co) { if (ro == RO_MAX && co == 0) { if (i == DEST_I) ++ans; return; } for (const auto dir : pattern[i] == '?' ? ALL_DIRS : string(1, pattern[i])) { const auto [delta_ro, delta_co] = delta(dir); const int ro_prime = ro + delta_ro; const int co_prime = co + delta_co; if (!is_possible(covered, ro_prime, co_prime)) continue; if (!is_possible(covered, ro_prime + delta_ro, co_prime + delta_co)) { switch (dir) { case 'U': case 'D': if (is_possible(covered, ro_prime, co_prime - 1) && is_possible(covered, ro_prime, co_prime + 1)) continue; break; case 'L': case 'R': if (is_possible(covered, ro_prime - 1, co_prime) && is_possible(covered, ro_prime + 1, co_prime)) continue; break; } } covered[ro_prime][co_prime] = true; recur(i + 1, ro_prime, co_prime); covered[ro_prime][co_prime] = false; } }; recur(0, 0, 0); return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); string s; cin >> s; cout << matching_paths_count(s) << '\n'; return 0; } 
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 So, seems like, the constraints are really tight, and the constant factor caused by all the nice code factorizations was simply killing it. After I unrolled all the DRY-ness, and uglified the code to the point listed below, it got accepted.UPD: Ah, btw, the absolute numbers in seconds I quoted above are not quite representative, as I ran the code with memory sanitization, and all the optimizations disabled. So, it should be, like, 7 times faster, when run by the OJ. Version 3#include using namespace std; static constexpr int RO_MAX = 6; static constexpr int CO_MAX = 6; static constexpr int DEST_I = (RO_MAX + 1) * (CO_MAX + 1) - 1; constexpr bool in_bounds(const int ro, const int co) { return ro >= 0 && ro <= RO_MAX && co >= 0 && co <= CO_MAX; } constexpr bool is_possible(const vector> &covered, const int ro, const int co) { return in_bounds(ro, co) && !covered[ro][co]; } void recur(const string &pattern, int &ans, vector> &covered, const int i, const int ro, const int co) { if (ro == RO_MAX && co == 0) { if (i == DEST_I) ++ans; return; } if ((pattern[i] == '?' || pattern[i] == 'U') && is_possible(covered, ro - 1, co)) { bool locked = !is_possible(covered, ro - 2, co) && is_possible(covered, ro - 1, co - 1) && is_possible(covered, ro - 1, co + 1); if (!locked) { covered[ro - 1][co] = true; recur(pattern, ans, covered, i + 1, ro - 1, co); covered[ro - 1][co] = false; } } if ((pattern[i] == '?' || pattern[i] == 'D') && is_possible(covered, ro + 1, co)) { bool locked = !is_possible(covered, ro + 2, co) && is_possible(covered, ro + 1, co - 1) && is_possible(covered, ro + 1, co + 1); if (!locked) { covered[ro + 1][co] = true; recur(pattern, ans, covered, i + 1, ro + 1, co); covered[ro + 1][co] = false; } } if ((pattern[i] == '?' || pattern[i] == 'L') && is_possible(covered, ro, co - 1)) { bool locked = !is_possible(covered, ro, co - 2) && is_possible(covered, ro - 1, co - 1) && is_possible(covered, ro + 1, co - 1); if (!locked) { covered[ro][co - 1] = true; recur(pattern, ans, covered, i + 1, ro, co - 1); covered[ro][co - 1] = false; } } if ((pattern[i] == '?' || pattern[i] == 'R') && is_possible(covered, ro, co + 1)) { // R bool locked = !is_possible(covered, ro, co + 2) && is_possible(covered, ro - 1, co + 1) && is_possible(covered, ro + 1, co + 1); if (!locked) { covered[ro][co + 1] = true; recur(pattern, ans, covered, i + 1, ro, co + 1); covered[ro][co + 1] = false; } } } int matching_paths_count(const string &pattern) { vector> covered(RO_MAX + 1, vector(CO_MAX + 1, false)); covered[0][0] = true; int ans = 0; recur(pattern, ans, covered, 0, 0, 0); return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); string s; cin >> s; cout << matching_paths_count(s) << '\n'; return 0; } 
•  » » » 4 months ago, # ^ |   0 This is my simple code within 1s(https://ideone.com/r9lZ5z)
•  » » » » 3 weeks ago, # ^ |   0 thanks for the beautiful code
•  » » » 2 months ago, # ^ |   0 I have also tried many optimization but still getting TLE after spending too much time on the problem. If could you please suggest me some improvements Code//JSD #include #define ll long long using namespace std; bool check[7][7]; int direction[7][7]; // 0, 1, 2, 3 -- L, R, U, D bool inline valid(int x, ll y){ if(x<0 or y<0 or x>6 or y>6) return false; return true; } ll inline findDirection(ll sx, ll sy, ll dx, ll dy){ if(sx == dx and dysy) return 1; if(sy == dy and dx forward(ll x, ll y, ll directions){ if(directions == 0) y--; if(directions == 1) y++; if(directions == 2) x--; if(directions == 3) x++; return {x, y}; } bool inline moveTo(ll sx, ll sy, ll dx, ll dy){ if(sx == 6 and dx == 6 and (dy>sy)) return false; if(sx == 0 and dx == 0 and (dy F = forward(sx, sy, dir); if(valid(F.first, F.second) and check[F.first][F.second]){ if(dir == direction[F.first][F.second]) return false; } return true; } bool inline proceed(ll sx, ll sy, ll dx, ll dy){ if(valid(dx, dy) and !check[dx][dy] and moveTo(sx, sy, dx, dy)){ direction[dx][dy] = findDirection(sx, sy, dx, dy); return true; } return false; } bool inline checkEnd(ll x, ll y){ if(x == 6 and y == 0) return true; return false; } bool inline final(ll x, ll y, ll move){ if(checkEnd(x, y) and move == 48) return true; return false; } ll solve(ll x, ll y, ll move, string &s){ if(final(x, y, move)) return 1; if(checkEnd(x, y)) return 0; check[x][y] = 1; ll ans = 0; if(s[move] == 'L' or s[move] == '?'){ if(proceed(x, y, x, y-1)) ans += solve(x, y-1, move+1, s); } if(s[move] == 'R' or s[move] == '?'){ if(proceed(x, y, x, y+1)) ans += solve(x, y+1, move+1, s); } if(s[move] == 'U' or s[move] == '?'){ if(proceed(x, y, x-1, y)) ans += solve(x-1, y, move+1, s); } if(s[move] == 'D' or s[move] == '?'){ if(proceed(x, y, x+1, y)) ans += solve(x+1, y, move+1, s); } check[x][y] = 0; return ans; } int main(){ string s; cin>>s; memset(direction, -1, sizeof(direction)); memset(check, 0, sizeof(check)); cout<
•  » » » » 2 months ago, # ^ |   0 It doesn't seem like the code is pruning the impossible paths early enough. Am I right, that it recurs until it runs out of moves, or hits the end point?Did you read “Pruning the search” section starting from the page 51 of the CSES book?
•  » » » » » 2 months ago, # ^ |   0 the moveTo method is doing the pruning part as mentioned in the book. whenever I reach the boundary I avoid atleast one direction of movement. Other optimization which I have done is the generalized part as mentioned in the book. Though I am not sure the way I have implemented is correct or not.
•  » » » » » » 2 months ago, # ^ |   0 Ah! I see, indeed. So, right, there's pruning in case of hitting a wall. For me it was not enough. It was also necessary to prune when hitting an already visited cell, and forming a T-shape, not just a T-shape on the boundary. x--x | | x->| x-- 
•  » » » » » » » 2 months ago, # ^ |   0 I have handled that too, by using the concept of direction. For each cell I have stored the direction from which I have arrived that cell, and in case (the one which you have mentioned about) suppose I reach cell (i, j) and I notice that cell (i, j+1) is already visited so in that case I have only two directions to move, out of which only one direction is good. I tried some examples and deduced that the direction which is not favourable is the direction specified by me in proceed() method [which is the direction of arrival at that cell]. so if up direction is stored in direction[i, j+1] then I will avoid going upwards from cell (i, j). I think that's what you mean by the T-shape. I am not sure if my way of handling is inappropriate or it is just time consuming.
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 Oh… Ok.Could it be that in such a case — $(i, j + 1)$ visited, you shouldn't even consider visiting the $(i, j)$?Here's my code handling that exact situation: if ((pattern[i] == '?' || pattern[i] == 'R') && is_possible(covered, ro, co + 1)) { // R bool locked = !is_possible(covered, ro, co + 2) && is_possible(covered, ro - 1, co + 1) && is_possible(covered, ro + 1, co + 1); if (!locked) { covered[ro][co + 1] = true; recur(pattern, ans, covered, i + 1, ro, co + 1); covered[ro][co + 1] = false; } } So, if $(i, j + 1)$ is visited, and the path would form a T-shape, I don't even go from $(i, j - 1)$ to $(i, j)$. The $locked$ boolean here means “there would be a T-shape”.
•  » » » » » » » » » 2 months ago, # ^ |   0 thought of something like that but got confused regarding the correctness. Thanks by the way!!
•  » » » » » » » » » 2 months ago, # ^ |   0 one update!! I did one more optimization which is if somehow I have created an Island of zeroes surrounded by ones in the matrix then again the answer is not possible. For that I am doing an explicit dfs for checking the number of connected components with zeroes if such number is greater then one then the answer is not possible in such case and we need to do backtrack rather than moving on. But still I am getting TLE on some cases. updated code (10/20 testcases passed)... //JSD #include #define ll long long using namespace std; bool check[7][7]; int direction[7][7]; // 0, 1, 2, 3 -- L, R, U, D string s; bool inline valid(int x, ll y){ if(x<0 or y<0 or x>6 or y>6) return false; return true; } ll inline findDirection(ll sx, ll sy, ll dx, ll dy){ if(sx == dx and dysy) return 1; if(sy == dy and dx inline forward(ll x, ll y, ll directions){ if(directions == 0) y--; if(directions == 1) y++; if(directions == 2) x--; if(directions == 3) x++; return {x, y}; } bool inline moveTo(ll sx, ll sy, ll dx, ll dy){ if(sx == 6 and dx == 6 and (dy>sy)) return false; if(sx == 0 and dx == 0 and (dy F = forward(sx, sy, dir); if(valid(F.first, F.second) and check[F.first][F.second]){ if(dir == direction[F.first][F.second]) return false; } int comps = components(); if(comps>1) return false; return true; } bool inline proceed(ll sx, ll sy, ll dx, ll dy){ if(valid(dx, dy) and !check[dx][dy] and moveTo(sx, sy, dx, dy)){ direction[dx][dy] = findDirection(sx, sy, dx, dy); return true; } return false; } bool inline checkEnd(ll x, ll y){ if(x == 6 and y == 0) return true; return false; } bool inline final(ll x, ll y, ll move){ if(checkEnd(x, y) and move == 48) return true; return false; } ll solve(ll x, ll y, ll move){ if(final(x, y, move)) return 1; if(checkEnd(x, y)) return 0; check[x][y] = 1; ll ans = 0; if(s[move] == 'L' or s[move] == '?'){ if(proceed(x, y, x, y-1)) ans += solve(x, y-1, move+1); } if(s[move] == 'R' or s[move] == '?'){ if(proceed(x, y, x, y+1)) ans += solve(x, y+1, move+1); } if(s[move] == 'U' or s[move] == '?'){ if(proceed(x, y, x-1, y)) ans += solve(x-1, y, move+1); } if(s[move] == 'D' or s[move] == '?'){ if(proceed(x, y, x+1, y)) ans += solve(x+1, y, move+1); } check[x][y] = 0; return ans; } int main(){ cin>>s; memset(direction, -1, sizeof(direction)); memset(check, 0, sizeof(check)); cout<
•  » » » » » 11 days ago, # ^ |   0 Nope! actually these optimizations came from discussion between 1 of friends. We are coding partners. But i checked in the book i'm you mentioned and i'm glad to know that we arrived at same solution. It's just our good luck!
 » 6 weeks ago, # | ← Rev. 2 →   0 Hello everyone, I also tried implementing it but in 4-5 cases it gives TLE, can someone please tell me what optimizations I am missing. My code#include #include #include #include #include #include #include using namespace std; #define endl "\n" #define ll long long int #define vi vector #define vll vector #define vvi vector < vi > #define pii pair #define pll pair #define bug(n) cout<<#n<<": "<mp1{}; mapmp2{}; bool vis[8][8]; ll res{}; bool is_valid(int x, int y){ if(x < 1 || x > 7 || y < 1 || y > 7) return false; if(vis[x][y]) return false; return true; } void search_grid(string &path, int index, int blk_cnt, int x, int y, char prev_step){ vis[x][y] = true; // Base Case if(x == 7 && y == 1){ if(blk_cnt == 49){ res++; } return; } if(index > 47){ return; } // we know direction if(path[index] != '?'){ int new_x = x + mp1[ path[ index ] ].f; int new_y = y + mp1[ path[ index ] ].s; //validity check of the move if(is_valid(new_x, new_y)){ //if seedha jaara hai to badiya if(prev_step == path[index]){ search_grid(path, index+1, blk_cnt+1, new_x, new_y, path[index]); //backtrack step vis[new_x][new_y] = false; } //if not seedha then bad splitting check else{ //if saamne is not blocked and valid then challo int samne_x = x + mp1[prev_step].f; int samne_y = y + mp1[prev_step].s; if(is_valid(samne_x, samne_y)){ search_grid(path, index+1, blk_cnt+1, new_x, new_y, path[index]); //backtrack_step vis[new_x][new_y] = false; } //if saamne is blocked or wall then check bad split else{ //check bad split here (opposite turns must be visited) //left or right turns if(new_x == x){ int opp_x = x; int opp_y = y - mp1[ path[ index ] ].s; // changed bool valid_cell = (opp_x >= 1 && opp_x <= 7 && opp_y >= 1 && opp_y <= 7); //checking opposite cell status if((valid_cell && vis[opp_x][opp_y]) || !valid_cell){ // safe hai turn lena search_grid(path, index+1, blk_cnt+1, new_x, new_y, path[index]); //backtrack_step vis[new_x][new_y] = false; } } // up or down turns else if(new_y == y){ int opp_x = x - mp1[ path[ index ] ].f; //changed int opp_y = y; bool valid_cell = (opp_x >= 1 && opp_x <= 7 && opp_y >= 1 && opp_y <= 7); //checking opposite cell status if((valid_cell && vis[opp_x][opp_y]) || !valid_cell){ // safe hai turn lena search_grid(path, index+1, blk_cnt+1, new_x, new_y, path[index]); //backtrack_step vis[new_x][new_y] = false; } } } } } } //we don't know where to go else{ for(int i{}; i<4; ++i){ int new_x = x + dx[i]; int new_y = y + dy[i]; //validity check of the move if(is_valid(new_x, new_y)){ //if seedha jaara hai to badiya if(prev_step == mp2[ {dx[i], dy[i]} ]){ search_grid(path, index+1, blk_cnt+1, new_x, new_y, mp2[ {dx[i], dy[i]} ]); //backtrack step vis[new_x][new_y] = false; } //if not seedha then bad splitting check else{ //if saamne is not blocked and valid then challo int samne_x = x + mp1[prev_step].f; int samne_y = y + mp1[prev_step].s; if(is_valid(samne_x, samne_y)){ search_grid(path, index+1, blk_cnt+1, new_x, new_y, mp2[ {dx[i], dy[i]} ]); //backtrack_step vis[new_x][new_y] = false; } //if saamne is blocked or wall then check bad split else{ //check bad split here (opposite turns must be visited) //left or right turns if(new_x == x){ int opp_x = x; int opp_y = y - dy[i]; // changed bool valid_cell = (opp_x >= 1 && opp_x <= 7 && opp_y >= 1 && opp_y <= 7); //checking opposite cell status if((valid_cell && vis[opp_x][opp_y]) || !valid_cell){ // safe hai turn lena search_grid(path, index+1, blk_cnt+1, new_x, new_y, mp2[ {dx[i], dy[i]} ]); //backtrack_step vis[new_x][new_y] = false; } } // up or down turns else if(new_y == y){ int opp_x = x - dx[i]; // changed int opp_y = y; bool valid_cell = (opp_x >= 1 && opp_x <= 7 && opp_y >= 1 && opp_y <= 7); //checking opposite cell status if((valid_cell && vis[opp_x][opp_y]) || !valid_cell){ // safe hai turn lena search_grid(path, index+1, blk_cnt+1, new_x, new_y, mp2[ {dx[i], dy[i]} ]); //backtrack_step vis[new_x][new_y] = false; } } } } } } } return; } void solve(){ string path{}; cin >> path; vis[1][1] = true; if(path[0] != '?'){ search_grid(path, 1, 2, 1 + mp1[path[0]].f, 1 + mp1[path[0]].s, path[0]); } else{ search_grid(path, 1, 2, 2, 1, 'D'); vis[2][1] = false; search_grid(path, 1, 2, 1, 2, 'R'); vis[1][2] = false; } // if(flag) res *= 2; cout << (res) << endl; } signed main() { fastio; int T{1}; // cin>>T; mp1['D'] = {1, 0}; mp1['U'] = {-1, 0}; mp1['L'] = {0, -1}; mp1['R'] = {0, 1}; mp2[{1, 0}] = 'D'; mp2[{-1, 0}] = 'U'; mp2[{0, -1}] = 'L'; mp2[{0, 1}] = 'R'; mem(vis, false); // cin.ignore(); must be there when using getline(cin, s) while(T--) { solve(); } return 0; } 
•  » » 6 weeks ago, # ^ | ← Rev. 12 →   0 whenever you post a code/solution on codeforces you should add it inside spoiler so that it is easier for other user to read. you can use spoiler like this like thislooks good right? :)
•  » » » 6 weeks ago, # ^ |   0 Oh, I'm sorry, I didn't knowthat. I will edit it. Thank you
•  » » » 6 weeks ago, # ^ |   0 Also, can you suggest to me some optimization that I need to do in my code to make it pass all the test cases?
•  » » 6 weeks ago, # ^ |   0 Great comments lol
 » 6 weeks ago, # |   0 A normal dfs/backtracking approach would take exponential time. So in such type of questions we use dfs with pruning, we prune the unnecessary states such that they are not explored further. So a normal dfs would have 4^48 calls (at max) which is astronomical but with dfs and pruning method it would take us nearly 1s to process some million recursive calls