meiniak's blog

Help needed in problem D from today's LeetCode Weekly contest
By meiniak, history, 4 years ago, In English

Here is the problem link and the solution. I have wrote a recusive solution with memoization to not re compute the sub-problems which have been computed. But i am getting Runtime error due to too much memory allocation in unordered map. How can i optimize it to get A.C ?

My solution : 

long long recur(long long n){
    if(n==0) return 0;
    else if(memo.find(n)!=memo.end()){
        return memo[n];
    }
    else{
        long long a = n%3 == 0 ? 1 + recur(n-(2*n)/3) : INT_MAX;
        long long b = n%2 == 0 ? 1 + recur(n-(n/2)) : INT_MAX;
        long long c = 1 + recur(n-1);
        vector<long long> v = {a,b,c};
        memo[n] = *min_element(v.begin(),v.end());
        return memo[n];
    }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial of the contest

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have couple of question,

  1. Is bfs sometimes can act as a more faster way than dfs ?

  2. Also,the states in dfs fashion are more intuitive as dp[n] = min(dp[n-1],dp[n/2],dp[n/3) + 1 as i did in the above solution , if i can't reach x'th state from n state i return INT_MAX.

  3. Why my solution is having stack overflow, is it due to c++ recursion limit, or my map is having 1e9 keys which is causing overlimit.

  4. Can you explain me how to define dp states if we use bfs approach

  5. What paradigm of dp it is called when using dfs or bfs .

Thank you for the kind patience. Will appreciate a lot.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. The problem is that your function will visit each state from $$$0...n$$$ and since n can be up $$$10^9$$$ the function is too slow.
    2. -
    3. Visiting too many states

    4. In bfs it would be other way around, dp[x] = minimum number of steps to make x from n

    5. ???

    Btw, you can fix your dfs dp by changing it to dp[n] = min(n % 2 + recur(n / 2), n % 3 + recur(n / 3)).

    → Reply