PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
The problem is of finding a path such that the weight of the edge with minimal weight, on the path, is maximized for all pairs of distinct vertices (u, v). Let us call such a path, a maximal path for (u, v). Let’s first try to understand a simple and slower dynamic programming solution similar to that of Floyd-Warshall’s All Pairs Shortest Paths. Let minimal[u][v][k] denote the minimal weight of an edge for a path that starts at node u, ends at node v, and the only intermediates are vertices 1, 2, …, k where the nodes are numbered from 1. We set minimal[u][v][0] to the weight of the edge (u, v), if it exists, or otherwise we set it to 0. We can compute minimal[u][v][k + 1] given minimal[x][y][k], for all x, y in V, as follows:
Clearly, the maximal path either passes through vertex k + 1, or it does not. This allows us to write:
minimal[x][y][k + 1] = MAX(MIN(minimal[x][k + 1][k], minimal[k + 1][y][k]), minimal[x][y][k])
So we can use O(V ^ 3) time and O(V ^ 3) space to solve the problem, but clearly the constraints are much higher.
Let us look at a next approach: Let us maintain a disjoint set data structure to keep track of vertices which are in same/different components. We start with the heaviest weight edge, and process edges in order of decreasing weight. Each time we find an edge that connects two vertices u and v, with different components, we merge the two components and for each vertex x that is in the first component, and for each vertex y in the second component, we set the value of minimal[x][y] to the weight of the edge (u -> v). We do this since there will be always be an edge on a path connecting x and y such that the weight of this edge will be lesser than or equal to the weight of the edge (u -> v), and so we know that this strategy will result in an optimal solution. We can reduce this problem further by seeing that we are computing nothing but the maximum spanning tree of the graph. We can compute the maximum spanning tree of the graph using Kruskal’s Algorithm in O(E * log(V)) time by sorting the edges, but this is likely to timeout because sorting the edges will take O(V ^ 2 * log(V)) time. We can use Radix Sort in base 2 ^ 15 (to speed up modulus calculations) and sort the edges in linear time, O(E) (2 ^ 15 is much less than the maximal number of edges). If we use path compression, and the union by rank heuristic, we’ll get a running time of O(V ^ 2 * alpha(V)), where alpha(n) is the inverse of the ackermann function. Once the maximum spanning tree has been computed, we can run a dfs/bfs from each vertex of the graph and fill the entries of the minimal array in O(V ^ 2) time. The time limits of this problem were kept strict so that solutions using weaker methods could not pass the system tests.
SETTER’S SOLUTION
TESTER’S SOLUTION
Can be found here