https://www.codingame.com/training/easy/gold-packing
Send your feedback or ask for help here!
Created by @tobakudan,validated by @JLukeSkywalker,@Nikai and @i_am_noob_abc.
If you have any issues, feel free to ping them.
There are multiple solutions with the same number of bars. For example, this also should work for the last test case: 3 10 15 21 28 36 55 66 78 91 105 120 136 153 171 190 210
3 Likes
I added this to fix the problem:
“If there still are multiple such sets, choose the first one in lexicographic order.”
1 Like
The last test/validator feels a bit iffy.
For one it requires code to be optimised which is not really stuff for an “easy” puzzle.
Secondarily I could get away with randomness + brute force with a pretty decent success rate. If one submit gave <100% I could just try again.
I would just do away with it to be honest.
I do agree that it’s not trivial but really generating all possible subsets is an ability you want to learn as soon as possible cause it’s pretty useful.
There are numerous ways to do it, you can use dedicated combinatorics modules like Python’s itertool, you can use bitsets and bitwise operators, you can run a DFS to generate the subsets recursively.
The complexity is always O(2^N), so it should not be a problem with N = 20, even without any optimisation. Maybe you were performing useless operations in the process.
Can’t pass validator 4… Can’t figure out why… Any hint ?
1 Like
Maybe your complexity is O(N * 2^N) instead of O(2^N).
It could be enough to make N=20 a borderline case.
How do you generate subsets ?
1 Like
Ok, thanks! I was using a recursive method with maybe to much operations to generate the subsets.
I’ve found a better one that pass all validators.
I think this puzzl is not easy, but rather medium. Optimization should not be in the easy category I think. It took me a lot more time than the other easy puzzles
For test case #3, Prime Gold,
Given answer is “5 7 13 17 19 23 29”
My answer is “2 3 7 13 17 19 23 29”
Another possible answer is “2 5 7 11 17 19 23 29”
All sums up to 113 exactly.
Lexicographically compare them as strings, my two answers should be listed before the given answer. So either the lexicographic order constraint is not good enough or the given answer is simply incorrect.
1 Like
Your solutions have more bars than the answer. The problem asks for fewest number of bars.
1 Like
Ouch! “fewest number of bars”…
Then for the last test case,
the given answer is “3 6 10 21 28 45 55 66 78 91 105 120 136 153 171 190 210”
my answer is “3 10 15 21 28 36 55 66 78 91 105 120 136 153 171 190 210”
Lexicographically compare them as strings, “3 10” should come before "3 6 ", (ascii ‘1’ is smaller than ‘6’).
Do you think so?
It depends if you compare lexicographically the strings or the numbers list.
I was thinking about lexicographic order of the list when I edited that, but it’s indeed ambiguous. I’ll try to rephrase that.
1 Like
The tests are all okay, but the last validatortest is wrong. Is there a way to test it?
I try with:
ergList = []
ergList.append([1,3,4,7])
ergList.append([1,3,4,8])
ergList.append([1,2,5,8])
ergList.append([1,1,5,9]) => the result
ergList.append([1,1,5,8])
hello @mw197, what did you get with:
1565
22
2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137 154 172 220 221 250 300
i pass this puzzle and get this result.
56 106 121 137 154 220 221 250 300
gl.
Can you explain that please ? I sort the lists of numbers in numeric order and it s good for the tests but i can’t pass 4th validator …
Same issue, test4 ok but validator 4 not. I hate that.
1 Like