Please Explain the logic for this problem

help
, ,
3

It is the problem of DP.

4

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. :slight_smile:

For complete solution: CodeChef: Practical coding for everyone

2 Likes
5

In this problem u have one byte land coin of value N

Things u can do with these coin

  1. Either make convert it into american currency for exchange of 1:1

  2. 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 CodeChef: Practical coding for everyone

1 Like
6

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

2 Likes
7

great but please explain appproch.

8

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.

1 Like
9

Thanks.You can try this question.

10

reason for this loop?-
for(i=0;i<=11;i++)
m[i]=i

11

why to use map instead of array?

12

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.

13

@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.

14

map is only used for this purpose na? due to size problem?

15

Yes, I think its only due to size problem.

16

@vivek96 Yes.

17

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?

18

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 :slight_smile:

19

But im getting WA.
Link-CodeChef: Practical coding for everyone

20

im getting wa please tell me what i did wrong,CodeChef: Practical coding for everyone

21

Here’s the working code : CodeChef: Practical coding for everyone

You did not take no of test cases into consideration, and few other things like that filldp() function were not needed (although not incorrect)

1 Like
22

Thanks a lot…Happy Coding