hello, i can pass 66% of the ide test, so i think i understand the basic implementation (brute force check for all cases possibles, compare the working solutions and find the best solution, finding the best score attainable if the total length is not possible) for this puzzle,
but i don’t know if it is compatible (compliant ?) with the last two tests with too much cases generation…
any help would be very nice.
1 Like
You can check the infamous Change-Making problem (you can find many sources easily), it’s a bit easier than this one and a good introduction to recursive search for an optimal solution.
Once you understand the basic recursive method, you can add memoization to avoid computing the same states over and over.
And then you realize that if you’re going to fill a cache anyway, why not get rid of the recursion and just fill the cache yourself in an ascending way (that’s called dynamic programming).
2 Likes
@pardouin thanks for your answer, actually i have erased all i did and trying a totally different approach beginning from the top length cut and go down recursively with some checks to avoid unconsistent cases, i ll tell you if it’s better
i know it is not very fair, but i mix my 2 algorithms and it passes the 100%…
O(n^2) does not pass last test case in C++ with/without recursion. This problem is biased towards Python. Author should consider all the languages not just Python. I used unordered_map to store all length and value pairs but still last test cases giving timeout error.
All you need is a simple array of length L+1 (L being the length of the rod).
The expected DP algorithm has a O(L x N) time complexity.
It’s not biased toward Python, Python is usually much slower than C++ (I’d say 5x to 100x slower).
@pardouin I used DP to solve this problem in Python. C++ version is failing in last test case with same logic. I had to use unordered_map to store length and value pair since you cannot store in plain array with index as length since 0 < length ≤ 10 000 000 000. Did you try last test case in C++ using DP?
This might be the reason nobody solved it in C++ yet. At least I don’t see any C++ solution.
There are plenty of c++ solutions, but they are only visible once you’ve solved it in c++.
Looking at your python submission the complexity is O(L^2) which is much worse than the intended DP solution. The means your python solution takes almost 5 seconds (which is right on the limit) for the last case to run but it’s possible to get around 100ms in python.
You only need an array of size 100 000 actually.
Lengths bigger than L can be ignored.
Hi, can someone confirm that the expected answer for the “Many pieces” example is indeed supposed to be 1152. I am getting 1149 and I only get 1152 if I override the value for length 1 to be 1 instead of 0 which is given from input. I made a recursion example that works for the first 4 tests, and it doesn’t error out like some have mentioned, it just gets a slightly wrong answer. I have the same issue with the “Huge Rod” example where if I override the value for 1 to be 1 instead of 0 I get the correct answer.
The simpler approach of dividing the values list by length for “Many pieces”, it’s clear that 13 has the most value which would give the start of the answer as 76 pieces of length 13 which has value of 76 x 15 =1140
Then the remaining 12 (1000-13*76) needs to be apportioned from the below length values:
length_values = {1: 0, 2: 1, 3: 1, 5: 4, 8: 7}
If the value of 1 was 1 then the answer would be 12 x 1 + 1140 = 1152 (as expected by the problem), but the length value for 1 is zero, so my answer becomes 1 piece of length 8 and 2 pieces of length 2, with the value then being 7x 1 + 1x2 + 1140 = 1149.
Very likely I’m screwing this up somehow as it’s obvious many others are getting the answer but I can’t see where my sums above are wrong? Can anyone please confirm that they are matching the 1152 value.
Much appreciated.
Mark
I did a first version recursively using remainders in integers division and I got similar slightly wrong results.
Cause even if a piece has the best ratio price/length, it’s not always the best choice to take as many of it has you can.
So I stuck with substraction, which was always giving good results but the stack was going pretty big and out of hand in Python (even with sys.setrecursionlimit), so I transformed my descending recursion into an ascending DP and it worked fine.
In Javascript, The last 2 test cases are basically impossible. I am not using recursion, a simple for loop. I have done it in the exact same way, in c++. I think the last two test cases should be reworked.
There are seven published solutions in Javascript.
Great, I get it now, thanks for the explanation. Incidentally, my recursive solution still scored 100%, but I can see that it’s suboptimal.
hi! can’t make an optimal solution 
. i did a “standard” solution fast enough to pass the last test but when submit , it does not pass the last verification level…
I’m looking for DP tutorials, do you have links?
i cant’ see what i should do recursive. thansk for your help !
From page 65 to middle of page 68. It’ll give you a good understanding of what DP is.
I tried but still I am getting time out at last test case. Did you try in C++?
I just did it in C++ to see if there was anything special, but there was nothing special.
Here’s all I use:
#include <iostream>
#include <algorithm>
using namespace std;
const int L = 100000;
int best[L];
int n, goal, length, value;
Nothing fancy, as you can see. algorithm is only used for max, you could easily get rid of it and use an if statement instead.
I published my complete solution if you want to give a look at it when you’re done.
Thanks. I successfully submitted after ignoring large length > L in C++. Thanks for the suggestion. I think the problem test cases could be improved by providing only list of lengths <= L in the input.
However I do observe that randomly I got timeout error on last test case. Running the test cases again few times gave me green. Earlier I did not notice this behaviour and assumed it was not working for last test case. Is it CG bug?
1 Like