Connection Status:
Competition Arena > DistanceZeroAndOne

DistanceZeroAndOne

TCO17 Round 2A · 2017-03-31 · by cgy4ever

TCO17 Round 2A · 2017-03-31 · by cgy4ever · Graph Theory
Class Name: DistanceZeroAndOne
Return Type: String[]
Method Name: construct
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel used to have a graph G but she lost it somewhere. She now wants to reconstruct it and she needs your help to do so.

Here is what she remembers about the graph:
  • G was a simple undirected graph on n nodes, numbered 0 through n-1.
  • G was connected.
  • All edges had unit lengths. (Thus, the distance between two nodes is simply the smallest number of edges one needs to traverse to get from one to the other.)
  • For each node i, the distance between nodes 0 and i was dist0[i].
  • For each node i, the distance between nodes 1 and i was dist1[i].

You are given the int[]s dist0 and dist1, each containing n elements. If there is at least one graph G that corresponds to these distances (and all the other constraints given above), return any such graph. More precisely, return a String[] R containing the adjacency matrix of the chosen graph G. For each i and j, R[i][j] should be 'Y' if nodes i and j are connected by an edge, or 'N' if they are not.

If there is no solution, return an empty String[] instead.

Constraints

  • n will be between 2 and 50, inclusive.
  • dist0 will contain exactly n elemnets.
  • dist1 will contain exactly n elemnets.
  • Each element in dist0 will be between 0 and n-1, inclusive.
  • Each element in dist1 will be between 0 and n-1, inclusive.
Examples
0)
{0,2,1}
{2,0,1}
Returns: {"NNY", "NNY", "YYN" }

We have a graph with three nodes. From the given distances we see that dist(0,1) = 2 and that dist(0,2) = dist(1,2) = 1. Thus, the graph G must look like this: 0 - 2 - 1.

1)
{0,2,1}
{1,0,2}
Returns: { }

The value dist0[1] claims that the distance between nodes 0 and 1 is 2. On the other hand, the value dist1[0] claims that this distance is 1. As the graph is undirected, this is impossible.

2)
{3,1,1,1}
{1,0,1,1}
Returns: { }

The value dist0[0] cannot be 3.

3)
{0,1,1,1}
{1,0,1,1}
Returns: {"NYYY", "YNYY", "YYNN", "YYNN" }
4)
{0,3,1,2,2,3,4,4}
{3,0,2,1,2,3,4,4}
Returns: {"NNYNNNNN", "NNNYNNNN", "YNNYYNNN", "NYYNYNNN", "NNYYNYNN", "NNNNYNYY", "NNNNNYNN", "NNNNNYNN" }

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

Coding Area

Language: C++17 · define a public class DistanceZeroAndOne with a public method vector<string> construct(vector<int> dist0, vector<int> dist1) · 150 test cases · 2 s / 256 MB per case

Submitting as anonymous