POI Farmcraft

Revision en1, by themaskedhero, 2016-11-21 18:42:33

Hi CF Community:

Today I was solving the problem Farmcraft (http://main.edu.pl/en/archive/oi/21/far). Basically in this problem, you start at the root of a tree, and when you reach a node, you start a timer in that node(except for the root, which only starts when you visit it last). Each node has a time value ti, and a timer in that node ends when it reaches ti. What is the minimum amount of time for all timers to end, if you walk the tree in the optimal way.

My idea was to binary search the minimum time, and then subtract this from each node's ti. Then, this gives the maximum time that you can reach each node. But how should I check if its possible to satisfy all maximum times. Or is there another solution?


  Rev. Lang. By When Δ Comment
en1 English themaskedhero 2016-11-21 18:42:33 749 Initial revision (published)