Let's talk about algorithms!
Moderator: Board moderators
4 posts • Page 1 of 1
First prove that there are at most m=1+log_2 n different kinds of gems in the optimal solution. Then use dynamic programming: for each vertex try to made it of gem with price 1,2,...,m. It should give you O(nm^2) algorithm which you can speed up to O(nm) by observing that it's enough to remember two best solutions for each vertex. Hope it will help you.
No...when you try make some vertex of gem with price i you must make all its children of different kinds of gems. So for each child you must choose "best" gem - if you just remember all solution, you must look at each of them. But if you remember only two best ones, then in one of them this child is made of gem with different price than i. So in fact you dont need other than two best solutions (and if you dont remember those two best, then you will have to look at every solution - so it will be slower).