Hello, I have an issue with validator 6 (the one that avoid hard code) but don’t have any hard code 
Only have a static array to memoize solutions m[2001][10]
Last testcase has N=1000 while validator 6 has N=2000 so maybe your solution is fast enough for 1000 but not for 2000.
Don’t pay much attention to the message about hardcoding, it displays it all the time, regardless of if you hardcode or not.
Another possible explanation, if you use Python for example and a recursive solution, you must set a higher recursion limit, so maybe you set it high enough for N=1000 but not for N=2000.
1 Like
All test pass now. Mistake was elsewhere… but yes, when I test custom with N=2000 and v[10] 1 to 10, it works but only when i set way amount in a long int type. (C code)
Hi all,
What can cause my solution to break on Validator 3 and Validator 6 while it works perfectly fine and stable for 100% of test cases?
I’ve got some optimizations and reuse previous calculations from the current run (it was not passing the last test without reusing).
I’ve also tried custom test cases with 2000 amount as it was mentioned by @Gbrfix above. Works just well in IDE.
My code is in JS.
Thanks.
here’s validator 3. Might help you to pass validator 6 as well:
Input:
17
4
5 8 10 11
Output
0
1 Like
Thanks, man!
This helped to spot a bug in my coin values handling.
I can validate 100% now.
Still my solution is suboptimal but it’s just good 'nuf.
According to the solution given in the book, 311, 131 and 113 are considered 3 different ways to solve it, while in the given task they should be considered as one (two 1’s and one 3). The given algorithm calculates the number of ways just fine if duplicates were allowed. To solve the given puzzle one would need to think of a very different solution.
I’ve been stuck on this for a while, because all the multiple solutions I came up with so far either do not consider duplicates or time out because of recursion depth.
another good textbook:
page 51
[Example: Counting change]
easier to understand
but this method will cause StackOverFlow error, need some technique to overpass
If that helps you:
I had the same issue, because I was thinking the problem as:
If we know the number of ways to make 1…n, you can compute n+1 by looking at n+1-C1 … n+1+CN (C1…CN being the coin values).
This is not how you should approach the problem, as it will obviously count duplicates.
Have the opposite approach instead:
If we know the number of ways to make 1…n for C1…CN, you can deduce the number of ways to make 1…N for C1…CN+1.
Also, the first answer of Pardouin is very accurate. I believe what I explained is what he called ‘with a maximal coin’ of M. His last point about only needing a 1D array is also correct, and the best way to implement it.
Hello everyone,
Using C code.
Kinda frustrated here, I don’t get why my code pass all tests, and does not pass only the 6th validator.
I fixed an error that may be caused by the use of “int” type, by using the “long int” type
On local, I tried to solve:
2000
10
1 2 3 4 5 6 7 8 9 10
And it solves immediatly : 439541281384464800
So I don’t think it is a speed problem.
I can’t get what my error may be sadly, so if anyone got an idea.
Anyway it was nice working on making it work. Thanks for it.