https://www.codechef.com/problems/COINS

can someone please tell what is wrong with this solution for the question code: COINS

#include
using namespace std;
int main()
{
int n,t;
cin>>t;
for (int i=0;i<t;i++)
{
int max=0;
cin>>n;
if(n<8)
{
max+=n;

	}
	else
	{
		max=(n/2)+(n/3)+(n/4);
	}
	
	
	
cout<<max<<endl;	
}



return 0;

}

Here, you are just breaking the initial number into n/2 ,n/3 and n/4 parts and adding them up to give the result but you have to look carefully into those n/2 ,n/3 and n/4 parts to see if they can be further maximized by breaking each of them and adding to the final result. This can be done using recursion but plane recursion won’t help you get full AC ,try working on some optimization through memoization. This is a problem of recursion and DP. Hope it helps. :wink:

The problem is classic Dynamic Programming example where you need to find out the maximum amount of American Dollars you can accumulate with a Bytelandian Gold Coin of value n.

I am gonna give you the recursive equation using which you can solve the problem under the given time-constraint.

dp[i] = \begin{cases} 0, & \text{i = 0} \\ 1, & \text{i = 1} \\ 2, & \text{i = 2} \\ 3, & \text{i = 3} \\ 4, & \text{i = 4} \\ max(i, dp[i >> 1] + dp[i / 3] + dp[i >> 2] & \text{i > 4} \\ \end{cases}

In the above recursive equation dp[i >> 1] is equivalent to dp[i / 2] and dp[i >> 2] is equivalen to dp[i / 4].

If you want to refer to my solutions:

  1. Byteladian Gold Coins Solution.

Thanks for reading.
Peace :v: