Problem Link-https://www.codechef.com/problems/COINS
My Solution-
if((n/2)+(n/3)+(n/4)>cp)
System.out.println((n/2)+(n/3)+(n/4));
else
System.out.println(cp);
Im unable to understand what question actually demands.Please help me guys,please provide examples
Edit-Please explain your approach with code.
You missed one thing.
You can further divide those n/2 , n/3 , n/4 coins to maximise profit.
Eg-
Lets say we have 24.
We divide it into 12 , 8, 6.
As you see in sample case, we can again divide 12 to obtain 13. You have to go till that step when exchanging coins for notes no longer gets you profit. Its not a one time operation.
EDIT-
There, solved the Q (although not by the required method i guess)
My solution is here
Basically what i did was to use recursion. I created a function “change()” to get the answer. For a value, return the max(n, change(n/2)+change(n/3)+change(n/4))
Since we will be doing lots of unnecessary computations, its better to store the values (i.e. use dynamic programming).
But an array of 10^9 cant be created. I did by using an array of 10^8 (for values b/w 10^8-10^9, its simple brute force recursion, while values less than 10^8 are stored). I think some other data structure ahd to be sued, of which i am unaware of.
Get back to me if you have doubts.
great but please explain appproch.
You just asked for clarification lol. I havent attempted this Q yet, so i cant give approaches as of now. Dont worry, i think someone else will.
Thanks.You can try this question.
It is the problem of DP.
This problem is based on dynamic programming (Recursion + memoization).
Initially, you are given ONE gold coin and you are asked what is the maximum amount you can extract with it.
I will define each gold coin as one state. What you are doing is just checking the first state. You are breaking n into three states n/2, n/3, n/4 and checking if their sum (n/2 + n/3 + n/4) is greater than n. That is correct, but partially. What if the the new state n/2 can be further divided into three new states n/4, n/6, n/8 and whose sum is greater than n/2? Or what if the sum (n/2 + n/3 + n/4) is not greater than n but when n/3 is further divided into three new states the resultant sum is greater than n?
So here goes the solution:
map<int,int> m;
int dp(int n)
{
if(n==0)
return 0;
if(m[n])
return m[n];
m[n]=max(n,dp(n/2)+dp(n/3)+dp(n/4));
return m[n];
}
Here i am calling the function with n as argument which is my initial state. Now I divide n into three states and call the same function with each state as a new state and save all my answers in a map (this was to reduce the time complexity, as same n may repeat so only calling one of them will do). This is simple recursion. I hope it’s clear. 
For complete solution: https://www.codechef.com/viewsolution/11986905
In this problem u have one byte land coin of value N
Things u can do with these coin
Either make convert it into american currency for exchange of 1:1
Exchange it smaller american currency by converting it to N/2 + N/3 + N/4
Approch is fairly simple for every coin you have to output max( i , (N/2 + N/3 + N/4) )
This can be done easily with DP
For solution https://www.codechef.com/viewsolution/13068022
reason for this loop?-
for(i=0;i<=11;i++)
m[i]=i
why to use map instead of array?
Because i think you cannot create an rray of size 10^9 . Although an array of even 10^8 does the job here. I think map is the apt data structure here.
Also, that loop assigns initial values. We can mathematically see that its better to directly sell the coin for dollars (instead of that n/2+n/3+n/4) if the value of coin is <12. The first profit starts from value 12.
@vivek96 I did some hand-calculation and noticed that for any gold coin with value in the range from 0 to 11, the answer is the value of the gold coin itself. You may omit/ignore that loop.
And I can’t create an array with size 10^9, so used map.
map is only used for this purpose na? due to size problem?
Yes, I think its only due to size problem.
You just need to figure out the maximum currency you can get from the given number of coins.
Just need to take care of the conditions on how we can maximise our currency.
The condition is that we can divide a given number n as n/2, n/3 and n/4. Now we will check if n/2+n/3+n/4 is greater than n, then this value of n will be divided into n/2, n/3 and n/4 else not.
Also while dividing we need to take care that we can further divide those n/2, n/3 and n/4 again and again until this sum (n/2+n/3+n/4) is less than n
You can check my code here
Correct! For me a recursive dp (its called memonisation or something…) did the trick. BTW, is an iterative approach possible to this problem? Its a cakewalk with recursive approach, but is it same if we try to go for iterative approach?
Yep, simple recursion with memoisation will work. I have got an approach to solve it using iteration too, but never Implemented that. Will try that too positively