Internet Problem Solving Contest

IPSC 2004

Solution to Problem C – Calls

The problem can be represented as a graph in which vertices correspond to cities and edges correspond to phone lines. In this representation, the problem can be formulated as follows:

We are given an N×N matrix A of positive numbers and a positive integer E (in fact, we are given just half of A, but the matrix is symmetric and all elements on the diagonal are unimportant). We have to determine, whether it is possible to find a graph with N vertices and E edges (each edge must have a positive length) that satisfies the condition C: "matrix element A[I,J] is the length of shortest path beween vertices I and J".

We will try to find a graph G satisfying C with the least number L of edges. It is clear that once this is done it is possible to add more edges with really large weights without changing the lengths of shortest paths. Thus the answer is "YES" for all values of E between L and N*(N-1)/2.

Our algorithm works like this:

  1. If E>N*(N-1)/2, answer "NO" (trivial condition)
  2. Start with an empty graph G on N vertices.
  3. Process elements of A[I,J] in increasing order:
    • Find the length D of the shortest path between I and J in G (our implementation uses Dijkstra's shortest-path algorithm)
    • If D<A[I,J], output "NO" and stop
      If D>A[I,J], add an edge between I and J of length A[I,J] to G
      If D=A[I,J], do nothing
  4. If the resulting graph G has more than E edges, answer "NO", otherwise answer "YES"

Clearly, this algorithm runs in O(N4) time and O(N2) space.

Correctness of the algorithm

Denote GS a graph that is obtained by our algorithm just after processing all entries of A[i,j]≤S. We will show that each graph GS has the following two properties:

Clearly, if Q is the largest element in matrix A, then P(Q) is exactly the property C, and L(Q) implies that GQ has the least possible number of edges. In other words, graph GQ, obtained when our algorithm is finished, indeed satisfies the requirements of the problem.

We will prove our claim by induction on S (where S is a value taken from the matrix A or 0). Base case: Graph G0 has no edges. Clearly, this graph satisfies property P(0) and L(0).

Inductive step: Assume that graph GS' satisfies P(S') and L(S') and let S be the smallest entry from A larger than S'. We will show that GS also satisfies properties P(S) and L(S).

We obtained graph GS by adding several edges of weight S to graph GS'. An edge was added between pair of vertices I,J if and only if A[I,J]=S, and the length of the shortest path between I and J in GS' was longer than S. Since GS' satisfies P(S'), it is easy to see that GS must satisfy P(S).

It remains to show that GS also satisfies L(S). Let us assume that there is an edge (I,J) in GS such that there exists a graph H satisfying P(S) where I and J are not connected.

Thus, GS satisfies L(S).

We have proved that if the algorithm produces graph GQ, the graph satisfies properties P(Q) and L(Q). It is also possible that the algorithm will fail while producing graph GS from GS'. This is because the for some edge (I,J), the graph GS' already contained a path shorter than A[I,J]. Property L(S') implies that the correct answer is indeed "NO" in this case.