### sumantopal07's blog

By sumantopal07, 3 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 Comments (6)
 » https://cses.fi/book/book.pdf page 52 (the printed page number) or 62 (the pdf page number)
•  » » thanks
•  » » i understood the optimisations, but can you explain the runtime mathematically? the explanations there looks more experimental.
 » 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 = 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; } 
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   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 = 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; } 
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   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 = 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; }