DistanceZeroAndOne | Topcoder Archive

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.

Definition

Class:: DistanceZeroAndOne
Method:: construct
Parameters:: int[], int[]
Returns:: String[]
Method signature:: String[] construct(int[] dist0, int[] dist1)
(be sure your method is public)

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,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.
```
{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.
```
{3,1,1,1}
```
```
{1,0,1,1}
```
```
Returns: { }
```
The value dist0[0] cannot be 3.

{0,1,1,1}

{1,0,1,1}

Returns: {"NYYY", "YNYY", "YYNN", "YYNN" }

{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" }

```
{0,1}
```
```
{1,0}
```
```
Returns: {"NY", "YN" }
```

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.