https://www.codingame.com/training/medium/ways-to-make-change

Send your feedback or ask for help here!

Created by @lhm,validated by @java_coffee_cup,@SinOfWrath and @codybumba.

If you have any issues, feel free to ping them.

https://www.codingame.com/training/medium/ways-to-make-change

Send your feedback or ask for help here!

Created by @lhm,validated by @java_coffee_cup,@SinOfWrath and @codybumba.

If you have any issues, feel free to ping them.

Nice puzzle but thereâ€™s still an issue with validator 5.

The problem was raised 2 days ago by SinOfWrath but not fixed and the contribution got validated in the meanwhile.

Basically the problem is that validator 5 features an edgecase that does not appear in the testcases and even if it matches the constraints, it makes so little sense that people could spend a long time before thinking about it.

So what do you think ? Should we edit validator 5 to make it more similar to testcase 5 ?

Or add a testcase similar to validator 5 ?

Edit: the more I think about it, the more I want to just remove it cause really Vi = 0 does not make sense, it could lead to infinite number of combinations, for example if the set is {0, 1} you have 1 = 1 + 0 = 1 + 0 + 0 etc.

3 Likes

agree :}

Yeah, Vi = 0 does not make any sense, I think I avoided this validator issue only by chance.

Problem solved, Stilgart edited it.

Itâ€™s the other way around, you sum 1 coin 10 times.

Interesting challenge, but Iâ€™m stuck on last test case: solution not optimized.

Message to moderator : Iâ€™m not sure what I can write in this thread, so remove if innapropriate.

Iâ€™m using a tree to build the solutions, represented by the leaves.

Of course, with sum = 1000 and the smallest possible coins, the tree is quite huge.

There may be a more mathematical solution to optimize my algorithm. I already did it when the sum within the tree is higher than the requested amount. But so far, Iâ€™m clueless for this last test caseâ€¦

Any clue ?

[edit] I tried using list instead of vector, which may be more optimized in this case, but I was unable to : error in algorithm when including listâ€¦

Say you want to find the number of combinations for an amount N.

If you already computed the number of combinations that gives all amounts from 0 to an number N - 1 and stored them in an array C, couldnâ€™t you determine C[N] from C[0], C[1], â€¦, C[N-1] ?

2 Likes

Thanks for the hintâ€¦ Need to think more about it was definitely not the path I went firstâ€¦

My dad and I have struggled with Test Case 6 for hours and hours, but we just canâ€™t figure it out. We used recursion, and we donâ€™t know how to make it efficient enough to solve Test Case 6. Could someone please give us a hint?

1 Like

We also couldnâ€™t understand pardouinâ€™s earlier commentâ€¦

1 Like

When the problem can be broken down into smaller and similar sub-problems, we can store the previous processed values into memory and take them out to reuse, to avoid duplicated calculation.

*Do not open the hint if you do not wish to see it.*

```
When the world has only 1-dollar coin circulating,
ways to make changes for $1 to $10:
$=10 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
When a 2-dollar coin is introduced, you have extra ways to make changes.
They are "EXTRA" ways. The original 1-dollar ways do not change.
Reuse previous calculated results.
$=2 [1, 2, 1, 1, 1, 1, 1, 1, 1, 1]
$=3 [1, 2, 2, 1, 1, 1, 1, 1, 1, 1]
$=4 [1, 2, 2, 3, 1, 1, 1, 1, 1, 1]
$=5 [1, 2, 2, 3, 3, 1, 1, 1, 1, 1]
$=6 [1, 2, 2, 3, 3, 4, 1, 1, 1, 1]
$=7 [1, 2, 2, 3, 3, 4, 4, 1, 1, 1]
$=8 [1, 2, 2, 3, 3, 4, 4, 5, 1, 1]
$=9 [1, 2, 2, 3, 3, 4, 4, 5, 5, 1]
$=10 [1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
```

Focus on two lines from above. Try to understand the reasoning.

3 Likes

Thank you so much. We couldnâ€™t have done it without you!

1 Like

hey, could not understand your hint.

Letâ€™s take

$=2 [1, 2, 1, 1, 1, 1, 1, 1, 1, 1]

If we have a 2$ coin, it does not change the number of ways to do 1, hence there should be no extra way, for 2$ it is just one more way, so shouldnâ€™t it be

$=2 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

?

The array is the cumulative number of ways to do changes.

When you have both 1 and 2-dollar coins, the way to do change for $1 does not change, keeps at 1.

The way to do changes for $2 will be the original way + extra way for using the 2-dollar coin, so it is 2.

in that case, why the rest of the array is not all 2s then?

to make change for 3 we can do 3*1 or 2*2+1

The way to change with 2 kinds of coins and with amount of $3 is calculated in the $=3 line.

The $=2 line is valid for amount not exceeding $2.

A first idea would be, if you call C[N] the number of ways to make N and your set of coins is {c1, c2, â€¦ } :

C[N] = C[N - c1] + C[N - c2] + â€¦

but if you do that, some combinations will be counted several times, for example a combination â€śN = 1 + 2 + somethingâ€ť will be counted in C[N - 1] AND in C[N - 2].

Two ways to deal with it:

first option: let C[N][M] denote the number of ways to make N with a *maximal coin* of M, then you can go like this:

C[N][N] = C[N - c1][c1] + C[N - c2][c2] + â€¦

second option: let C[N][M] denote the number of ways to make N with a *minimal* coin of M, then you can go like this:

C[N][0] = C[N - c1][c1] + C[N - c2][c2] + â€¦

Both options work, and hint for a solution based on a recursive function. Youâ€™ll want to memoize the results to not recalculate the same things many times. It implies storing all values in a big cache, a 2dim array here (or let a builtin memoization feature do it for you).

You might have to set a higher recursion limit but it will work.

Now if you want to go further, if youâ€™re familiar with those problems with recursive functions + memoization, you know that there is usually a way to get rid of the recursive function and build the cache yourself in an ascending way.

Here itâ€™s particularly interesting cause when you fill the cache you realize that you donâ€™t even need a 2dim array, you can only use a 1dim array and with the good chronology, modify the values in place and end up with the final state (the only one you actually need).

Itâ€™s a good way to save memory.

Thatâ€™s how java_coffee_cup does it, he uses this chronology (step 1: maximal coin is c1, step 2: maximal coin is c2, etc).

Is it possible to get the solution for C++ ? I am stuck on this exercices for a long time and I canâ€™t figure out how to solve it

I you still canâ€™t solve it after all thatâ€™s been said, it might mean youâ€™re not ready for this kind of puzzle yet.

Maybe try to solve easy puzzles first, thereâ€™s more than hundred of them:

Also, for this specific puzzle, this kind of problem is described here: https://cses.fi/book/book.pdf (from page 65), thereâ€™s the traditionnal change making problem and several other classics.

The codes are given in C++ so itâ€™s perfect for you.

1 Like