## Help on BOI Questions

Moderator: Board moderators

doraemon2112
New poster
Posts: 9
Joined: Sun Jul 11, 2004 10:55 am

### Help on BOI Questions

I want to get some hints on this question:

I've no idea to solve this problem. Can you help me?

Thanks a lot!
gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm
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.
doraemon2112
New poster
Posts: 9
Joined: Sun Jul 11, 2004 10:55 am
Thanks a lot.

>>it's enough to remember two best solutions for each vertex
If I remember all the solutions of a vertex, can I speed it up to O(N)?
gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm
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).