I want to get some hints on this question:
http://www.ut.ee/boi/?item=boi.tasks.1.gems
I've no idea to solve this problem. Can you help me?
Thanks a lot!
Help on BOI Questions
Moderator: Board moderators
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.

 New poster
 Posts: 9
 Joined: Sun Jul 11, 2004 10:55 am
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).