ChangeDistances | Topcoder Archive

Problem Statement

You are given an undirected graph G on n vertices, labeled 0 through n-1. Find any undirected graph H on those n vertices such that such that for all pairs of vertices u != v, the distance between u and v in G is different from the distance between u and v in H.

More precisely, you are given the adjacency matrix of G in the String[] g: g[i][j] is '1' if there is an edge between vertices i and j, and it is '0' otherwise. Return the adjacency matrix of your H in the same format. It can be shown that there is always a solution. If there are multiple answers, you may return any of them.

Definition

Class:: ChangeDistances
Method:: findGraph
Parameters:: String[]
Returns:: String[]
Method signature:: String[] findGraph(String[] g)
(be sure your method is public)

Notes

The distance between two vertices in a graph is the smallest number of edges one needs to traverse in order to get from one of them to the other. If there is no path between the two vertices, the distance is considered to be infinity.
The returned String[] must be symmetric according to the main diagonal, and it must have '0's on the main diagonal.

Constraints

n will be between 1 and 50 elements, inclusive.
g will have exactly n elements.
Each element of g will have exactly n characters.
Each character of each element of g will be either '0' or '1'.
For all u and v, g[u][v] = g[v][u].
For all u, g[u][u] = 0.

Examples

```
{"011","100","100"}
```
```
Returns: {"000", "001", "010" }
```
The graph G contains the edges 0-1 and 0-2. Thus, distG(0,1) = distG(0,2) = 1, and distG(1,2) = 2. The graph H that corresponds to the return value shown above contains only the edge 1-2. Thus, distH(0,1) = distH(0,2) = infinity and distH(1,2) = 1.
```
{"000","000","000"}
```
```
Returns: {"011", "100", "100" }
```
The given graph G consists of three isolated vertices. All distances are infinite. The return value describes the graph H that contains edges 0-1 and 0-2. In this graph all distances are finite, and therefore different from the corresponding distances in G.

{"0100","1000","0001","0010"}

Returns: {"0011", "0010", "1100", "1000" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.