Jack_sparrow_06's blog

By Jack_sparrow_06, history, 14 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);

• -5

| Write comment?
 » 14 months ago, # | ← Rev. 4 →   0 the recursion take from editorial O(n^(log3 (2))) ~ O(n^0.6) but initialize dp array will take O(n)
 » 14 months ago, # | ← Rev. 2 →   +8 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.