UVa 295

From Algorithmist
Jump to navigation Jump to search

Solution[edit]

Fix a fatness d. First one may transform the fatness of the man to the fatness of the obstacles, since both are saying that the man and the obstacle cannot be as close as d/2. So the man is a single point, and each obstacle is a disk of diameter d. Then the question is simply whether there is a path from the left to the right while staying away from the forbidden region. There is no so path iff the top and bottom parts are connected by forbidden regions. (Convinced yourself it is an "iff".) So, for fixed d, we draw a graph on the disks (and top/bottom edges) such that A~B in the graph if these two disks are connected (centers are <= d away). Also it is obvious how to define the edges for top edge and bottom edge. Then run a DFS or so to see if the top edge is connected to the bottom. To find the biggest possible d, we may use a binary search. That all for the programming contests.

More Interesting Stuff[edit]

Now, for the Algorithmists: How to find a mathematical formula for this problem? We construct a complete graph with X = top edge, Y = bottom edge, and the disks, the edges in the graph have distance as weights. d is good iff any path from X to Y has an edge at least d. Define the length of a path to be its biggest edge, the best d is the shortest distance from X to Y in the new sense. (And one can easily prove that similar shortest path algorithms solves the new problem.) And yet this is not the end: Compute the minimum spanning tree of the complete graph, and the answer is the biggest edge on the path from X to Y in the tree. Once we see this, it is routing to prove it. So we have

Theorem: In a weighted graph G. Define (the metric) d(x, y) to be the length of shortest paths (in terms of max edge on the path). Define t(x, y, T) to be the weight of biggest edge on the path from x to y. Then d(x, y) = t(x, y, T) for any minimum tree T.

By this theorem, and dynamic programming on the tree, we can compute all the d(x, y) in O(n^2 log n) time.