Indian Computing Olympiad

Dynamic programming on trees→Coffee Shop (APIO Shortlist 2007)

Given some stations arranged in a tree-like network, we want to place coffee shops at some stations so that no station is more than K hops away from a coffee shop.

Since the network is a tree, we identify any one node as the root and walk up from the leaves.

When we come to a node v, we assume we have processed its subtrees and placed coffee shops. We need to decide whether to place a coffee shop at v.

The only reason to place a coffee shop at v is if there is some node below v that cannot be serviced below v and would become more than K hops away from a coffee shop if there is no shop at v.

To compute this, we maintain two quantities:

• C(v) : minimum depth of coffee shop below v
• U(v) : maximum depth of unserved node below v

We first compute

	C'(v) = 1 +	min	C(w)
		w in child(v)

to find the minimum depth of a coffee shop from v without placing a coffee shop at v.

Let {w1,w2,...,wn} be the children of v. Even if we don't place a coffee shop at v, an unserved node below one child wi of v may get served (via v) by a coffee shop below some other child wj of v. Recall that we have already computed C'(v), the shortest distance from v to a coffee shop below it. For each child w of v, compute

• U'(w) = 0, if U(w) + 1 + C'(v) ≤ k (node below w can reach a coffee shop via v)
• U'(w) = U(w), otherwise (cannot reach a coffee shop via v)

Now, we must place a coffee shop at v if U'(w) = k-1 (otherwise, after adding v without a coffee shop, the unserviced node below w will be k hops away from v without seeing a coffee shop and nearest coffee).

If we add a coffee shop at v, every node below v is served, including v. So the 'maximum depth of unserved node below v' is not defined. Defining it as 0 would imply that v was not served. And, to ensure that the +1s from executing "U(v) = 1+ max[w child of v] U'(w)" in the other case does not interfere with our values, we define U(v) to be -infinity. So, U(v) = -infinity, where 'infinity' can be any number greater than the total number of nodes in the tree.

• C(v) = 0
• U(v) = -infinity

Otherwise,

• C(v) = C'(v)
• U(v) = 1 + max_{w child of v} U'(w)

Finally, when we reach the root, we must put a coffee shop if there is any unserviced node below it, or if it is itself unserviced by anything below it.

To show that this solution is optimal, consider any other solution. Inductively, in every subtree, if our solution puts a coffee shop, the other solution must have a matching coffee shop (because we put coffee shops only when absolutely necessary). Our coffee shops are pushed up as far as possible, which can only improve the total number.

---