For problem code COINS
this is my code
[1]
Approach i used is: if (n<12) max_value=n, else: max_value = calc_max(n/2) + calc_max(n/3) + calc_max(n/4) **along with saving the entries in HashMap with each value of n**
Test cases mentioned above have passed, but the problem is when I submit this code, it gives me TLE.
I ran the code in my local system, gave output of 4243218150, for input: 1000000000 in around 30 seconds.
Can you or anyone help me out here ?
[1]: https://www.codechef.com/viewsolution/21210211
Consider N=48,
Then You need calculate calc_max( 24) + calc_max(16) + calc_max(12)
Then again for calc_max(24) You need to calculate calc_max( 12) + calc_max(8) + calc_max(6)
For calc_max(16) = > calc_max( 8) + calc_max(5) + calc_max(4)
calc_max(12) => calc_max( 6 ) + calc_max(4) + calc_max(3) and so on…
Note : You are calculating same values of N for multiple time like 12, 8, 6 etc, consuming more time, resulting TLE.
So, When You Calculate a calc_max(K), store it in array / dictionary.
After that, when you see for a value K, their value is already calculated, just use that value instead of calculating again and again.
View My solution
I was storing the values in HashMap, but was not exiting from recursive function, even after getting value from map, i was going through whole function, few print statements made that clear, thanks 
1 Like