COULD SOMEONE EXPLAIN PLEASE ?

Revision en1, by Jack_sparrow_06, 2023-06-07 15:25:44

Could someone explain what did I did wrong for the fourth question. 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, 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 &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 dp(n + 1, -1); bool res = solve(n, m, dp); ~~~~~

Tags help needed

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Jack_sparrow_06 2023-06-07 15:28:05 42
en2 English Jack_sparrow_06 2023-06-07 15:26:54 58
en1 English Jack_sparrow_06 2023-06-07 15:25:44 944 Initial revision (published)