Could someone explain what did I did wrong for the fourth question [problem:1829D]. When I submitted by recursive code it gets accepted, but when I memoized the code, I am getting TLE. Thanks for explanation in advance. Below is the code, ↵
[problem:1829D]↵
**RECURSIVE**↵
~~~~~↵
bool solve(int n, int m) {↵
if(n == m) return true;↵
if(m > n || n % 3 != 0) return false;↵
↵
int ind = n / 3;↵
bool left = solve(ind, m);↵
bool right = solve(n - ind, m);↵
return left || right;↵
}↵
// Invoking function↵
bool res = solve(n, m);↵
~~~~~↵
↵
**MEMOIZED CODE**↵
~~~~~↵
bool solve(int n, int m, vector<int> &dp) {↵
if(n == m) return true;↵
if(m > n || n % 3 != 0) return false;↵
if(dp[n] != -1) return dp[n];↵
↵
int ind = n / 3;↵
bool left = solve(ind, m, dp);↵
bool right = solve(n - ind, m, dp);↵
return dp[n] = (left || right);↵
}↵
↵
//Invoking function↵
vector<int> dp(n + 1, -1);↵
bool res = solve(n, m, dp);↵
~~~~~↵
↵
**RECURSIVE**↵
bool solve(int n, int m) {↵
if(n == m) return true;↵
if(m > n || n % 3 != 0) return false;↵
↵
int ind = n / 3;↵
bool left = solve(ind, m);↵
bool right = solve(n - ind, m);↵
return left || right;↵
}↵
// Invoking function↵
bool res = solve(n, m);↵
↵
**MEMOIZED CODE**↵
bool solve(int n, int m, vector<int> &dp) {↵
if(n == m) return true;↵
if(m > n || n % 3 != 0) return false;↵
if(dp[n] != -1) return dp[n];↵
↵
int ind = n / 3;↵
bool left = solve(ind, m, dp);↵
bool right = solve(n - ind, m, dp);↵
return dp[n] = (left || right);↵
}↵
↵
//Invoking function↵
vector<int> dp(n + 1, -1);↵
bool res = solve(n, m, dp);↵
↵
