Jack_sparrow_06's blog

COULD SOMEONE EXPLAIN PLEASE ?
By Jack_sparrow_06, history, 11 months ago, In English

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);
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jack_sparrow_06 (previous revision, new revision, compare).

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jack_sparrow_06 (previous revision, new revision, compare).

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

try to return in terms of dp[n] wherever possible.

→ Reply
»
11 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

the recursion take from editorial O(n^(log3 (2))) ~ O(n^0.6) but initialize dp array will take O(n)

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.)************

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply