Help on BOI Questions

doraemon2112 · Post by **doraemon2112** » Sat Jul 31, 2004 7:30 pm

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!

gawry · Post by **gawry** » Mon Aug 02, 2004 4:01 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 · Post by **doraemon2112** » Tue Aug 03, 2004 2:43 pm

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 · Post by **gawry** » Tue Aug 03, 2004 3:43 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).