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?
what's the time and memory limit?
Suppose you are at node x. Now you must choose an optimal order of visiting the children of x.
Consider if it has just two children a and b. We have the information of the time it takes traverse the edges of a child's subtree, and the best time of a computer being turned on for a child's subtree (i.e. the 'answer' for that subtree alone). What would be best?
It depends on which of size[a] + time[b] and size[b] + time[a] is smaller! Because then you minimise the max resulting time. Notice that this is also size[a] — time[a] < size[b] — time[b] which is good because then the order becomes independent of the variables you are comparing it to
Okay, now we know the best way to choose out of two nodes. How does this apply to more than two nodes?
Suppose we have a proposed solution. Notice that if two adjacent children in the solution order (say a and b) are better to be switched (i.e. the condition inside the spoiler), then we always switch them. Therefore it is optimal to sort by this condition for the entire list.
I'm sure you can work out the final solution with this idea of sorting :)