### Jack_sparrow_06's blog

By Jack_sparrow_06, history, 4 months ago, Could someone explain what did I did wrong for the question 1829D - Gold Rush. 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,

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);  Comments (7)
 » Auto comment: topic has been updated by Jack_sparrow_06 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by Jack_sparrow_06 (previous revision, new revision, compare).
 » try to return in terms of dp[n] wherever possible.
 » 4 months ago, # | ← Rev. 4 →   the recursion take from editorial O(n^(log3 (2))) ~ O(n^0.6) but initialize dp array will take O(n)
•  » » Thankyou for the explanation, understood now.
 » We can solve this problem recursively. Let the current pile have n gold nuggets. If n=m, then we can make a pile with exactly m gold nuggets by not doing any operations. If n is not a multiple of 3, then it is not possible to make a move, because after a move we split n into x and 2x, so n=x+2x=3x for some integer x, meaning n has to be a multiple of 3. Finally, if n is a multiple of 3, then we can split the pile into two piles with n/3 and 2n/3 gold nuggets, and we can recursively check if we can make a pile with exactly m gold nuggets. By the Master Theorem, the time complexity is O(n^0.631). Most compilers and languages optimize the recursion enough for this to pass comfortably. (The model solution in C++ runs in 15 milliseconds.)************
 » 4 months ago, # | ← Rev. 2 →   Here is my guess, since there is no statement in the problem which says: "the sum of all n over all test cases is less than 10^7," it is right to assume that there can be 1000 test cases where n = 10^7. To initialize your dp array of size n + 1, it takes O(n) time. And there are t test cases. Since you are making a new array each test case, the total amount of time to make your dp array is O(n * t). n is at most 10^7 and t is at most 1000, so multiplied this is 10^10. Those many operations will certainly time out.