Could anyone plz help with this time out error?

help
,
1

Here’s my solution, given time limit is 3 sec and my code runs for 3.63 sec

my code–

#include <iostream>
using namespace std;

long int  maxdollar( long int  p)
{    if (p==0)
      return 0;
    if(p>=12)
    {
        long int x= maxdollar(p/2);
        long int  y= maxdollar(p/3);
        long int  z= maxdollar(p/4);
        
        return x+y+z;

    }
    
    return p;
}


int main() 
{
	 ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
	 long int  n; 
	 
	while(cin>>n )
	{  // while()
	    
	   cout<<maxdollar(n)<<"\n";
	    
	}
	
	return 0;
}

problem code- COINS Problem - CodeChef

I looked through submissions and found that many solutions with same algo have been accepted.

one such solution- CodeChef: Practical coding for everyone

2

Memoize your solution, other recursive non c++ solutions are passing because of the extra multiplier given to them.

3

Hi,

this is a link for similar C++ solution.

Also could explain how could I memoize it, perhaps with the help of example? Thanks

4

I couldn’t find the link, can you please share it.

5

yeah sure,

https://www.codechef.com/viewsolution/45820121

could you see it now ?

6

Yeah, that’s what I’m saying this solution isn’t pure recursion it has been memoized using the dp map that you can see in the code.
What we do exactly is whenever we calculate solve function we store the values of solve(i) in dp[i] so that we can straightaway return the value in constant time instead of wasting another exponential amount of time to recalculate the same thing. See this commented code.

map<ll, ll> dp;

ll solve(ll n){
// base case.
    if (n == 0) return 0;

 //  In the next line we first check if we already have evaluated calculated 
//   dp[n]  in some step, if we have then just return it otherwise proceed.
    if (dp.count(n)) return dp[n];



//  calculate the the value of dp[n] since we don't have it already.
    ll n2 = solve(n/2);
    ll n3 = solve(n/3);
    ll n4 = solve(n/4);

// store the calculated value of solve(n) in dp[n] so that we don't have to calculate
// it again in exponential time whenever it's called again in future.
    dp[n] = max(n, n2+ n3+ n4);
    return dp[n];
}
2 Likes
7

ohh, I noticed the map dp but didn’t really understand it’s purpose.
Thanks for the explanation, I understand it now.

1 Like