lord_vinayak's blog

DP : Minimum no. of coins needed to make given amount — for large values
By lord_vinayak, history, 12 days ago, In English

I am trying to attempt 996A - Hit the Lottery and have written its solution using memoization. The code works for smaller values but it fails to execute for large inputs. What changes I need to make to get the problem accepted?

const int N = 1e5;
int dp[N]; int coins[5]={1,5,10,20,100};
int func(int amt){
	if(amt==0) return 0;
	int ans = INT_MAX;
	if(dp[amt]!=-1) return dp[amt];
	for(int coin:coins){
		if(amt-coin>=0)
			ans = min(ans, func(amt-coin)+1);
	}
	return dp[amt]=ans;
}
int main()
{
	FAST_IO
	int amt; cin>>amt;
	memset(dp, -1, sizeof(dp));
	
	int ans = func(amt);
	if(ans==INT_MAX) cout<<"-1";
	else cout<<ans;

}

I tried changing ans = min(ans, func(amt-coin)+1) to ans = min(ans+0LL, func(amt-coin)+1LL) but it still doesn't show any output. Help me out with changes I need to do.

Tags dp
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$N$$$ is up to $$$10^9$$$, it's obvious such memoization won't work here, since the code's time complexity is $$$\mathcal{O}(n)$$$

→ Reply
»
12 days ago, # |
  Vote: I like it -9 Vote: I do not like it

you're so amateur, im dying of laughter.

since 1,5,10,20 are nott coprimes, it always optimal to select the largest denomination first lol

pathetic.

→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You definitely could've stated that in a nicer way :)

    → Reply
»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Before learning dp, you should've learned about time complexity.

→ Reply
»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

DP is only necessary when at least one pair exists, such as 2*a>b, for any a,b belonging to the denomination array.

Since that's not the case, a greedy approach will work fine because taking a smaller value will never be beneficial if you can choose a larger one.

This text I took from the CP Handbook by Antti Laaksonen Book

Coin problem

As a first example, we consider a problem where we are given a set of coins and our task is to form a sum of money n using the coins. The values of the coins are coins = {c1, c2,..., ck}, and each coin can be used as many times we want. What is the minimum number of coins needed? For example, if the coins are the euro coins (in cents) {1,2,5,10,20,50,100,200} and n = 520, we need at least four coins. The optimal solution is to select coins 200+200+100+20 whose sum is 520.

Greedy algorithm

A simple greedy algorithm to the problem always selects the largest possible coin, until the required sum of money has been constructed. This algorithm works in the example case, because we first select two 200 cent coins, then one 100 cent coin and finally one 20 cent coin. But does this algorithm always work? It turns out that if the coins are the euro coins, the greedy algorithm always works, i.e., it always produces a solution with the fewest possible number of coins. The correctness of the algorithm can be shown as follows:

First, each coin 1, 5, 10, 50 and 100 appears at most once in an optimal solution, because if the solution would contain two such coins, we could replace them by one coin and obtain a better solution. For example, if the solution would contain coins 5+5, we could replace them by coin 10. In the same way, coins 2 and 20 appear at most twice in an optimal solution, because we could replace coins 2+2+2 by coins 5+1 and coins 20+20+20 by coins 50 + 10. Moreover, an optimal solution cannot contain coins 2 + 2 + 1 or 20+20+10, because we could replace them by coins 5 and 50. Using these observations, we can show for each coin x that it is not possible to optimally construct a sum x or any larger sum by only using coins that are smaller than x. For example, if x = 100, the largest optimal sum using the smaller coins is 50+20+20+5+2+2 = 99. Thus, the greedy algorithm that always selects the largest coin produces the optimal solution.

This example shows that it can be difficult to argue that a greedy algorithm works, even if the algorithm itself is simple.

→ Reply
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for helping me out. I'm a complete beginner and your comment was really insightful.

    → Reply
  • »
    »
    12 days ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    At times using only the necessary conditions (like number of 5's should be < 2 ..) we can bound the number of coins of each type in the optimal solution: For above question:

    (Let n(1) denote number of coins that can be present in any optimal solution)

    n(1) < 5

    n(5) < 2

    n(10) < 2

    n(20) < 5 (can be made tighter to n(20) < 3 as mentioned above)

    So here after fixing a choice of number of coins of 1,5,10,20 the number of 100 coins we take is fixed. So if we iterate all 5*2*2*5 combinations of number of coins of 1,5,10,20 we will end up covering the optimal answer as well.

    → Reply