Connection Status:
Competition Arena > ChangeDistances

ChangeDistances

TCO19 SRM 746 · 2019-01-09 · by majk

TCO19 SRM 746 · 2019-01-09 · by majk · Graph Theory
Class Name: ChangeDistances
Return Type: String[]
Method Name: findGraph
Arg Types: (vector<string>)
Problem Statement

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.

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
0)
{"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.

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.

2)
{"0100","1000","0001","0010"}
Returns: {"0011", "0010", "1100", "1000" }
3)
{"0100","1010","0101","0010"}
Returns: {"0011", "0001", "1000", "1100" }
4)
{"0"}
Returns: {"0" }

Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ChangeDistances with a public method vector<string> findGraph(vector<string> g) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous