Help on BOI Questions

Let's talk about algorithms!

Moderator: Board moderators

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

Help on BOI Questions

Post by doraemon2112 »

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
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm

Post by gawry »

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

Post by doraemon2112 »

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

Post by gawry »

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).
Post Reply

Return to “Algorithms”