SPGraph | Topcoder Archive

Problem Statement

Series-parallel graphs are defined inductively as follows. The simplest kind is denoted (quotes for clarity) "~" and is depicted below.

Note how one node functions as the source and another as the sink. More complex series-parallel graphs are constructed in the following ways. Suppose x and y are strings denoting disjoint series-parallel graphs (they cannot share any vertices). The series-connection of these graphs is denoted Sxy, and is depicted below.

As seen above, the sink of the first graph and the source of the second have been merged. The new source is the source of the first graph. The new sink is the sink of the second graph. The parallel-connection is denoted Pxy, and is depicted below.

As seen above, the sources of the two graphs are merged to form the new source. Similarly, the sinks have been merged to form the new sink. A simple example on actual graphs is depicted below.

Character i of element j of graph denotes whether node i and node j share an edge ('Y' for yes, 'N' for no, and all indices are 0-based). All connections are undirected. Given the source and sink, return the lexicographically first String denoting the given series-parallel graph. Constraints will guarantee the given graph is series-parallel (constructable by the above rules using the simplest kind as "base cases").

Definition

Class:: SPGraph
Method:: getString
Parameters:: String[], int, int
Returns:: String
Method signature:: String getString(String[] graph, int source, int sink)
(be sure your method is public)

Notes

As with ASCII, 'P' comes before 'S' which comes before '~'.

Constraints

graph will contain between 2 and 50 elements inclusive.
Each element of graph will contain exactly N characters, where N is the number of elements in graph.
Each character in graph will be 'Y' or 'N'.
Character i in element i of graph will always be 'N'.
Character i in element j of graph will equal character j in element i.
source will be between 0 and N-1 inclusive, where N is the number of elements in graph.
sink will be between 0 and N-1 inclusive, where N is the number of elements in graph.
source will not equal sink.
The given graph will be series-parallel using the given source and sink.

Examples

```
{
"NY",
"YN"
}
```
```
0
```
```
1
```
```
Returns: "~"
```
Depicted above.
```
{
"NYN",
"YNY",
"NYN"
}
```
```
0
```
```
2
```
```
Returns: "S~~"
```
Depicted above.

{
"NYY",
"YNY",
"YYN"
}

Returns: "PS~~~"

Depicted above.

```
{
"NYNY",
"YNYN",
"NYNN",
"YNNN"
}
```
```
2
```
```
3
```
```
Returns: "SS~~~"
```
The graph is depicted below with the vertices numbered.

{
"NYYNNNNNNN",
"YNNYNNNNNN",
"YNNYNNNNNN",
"NYYNYYNNNN",
"NNNYNNYNNN",
"NNNYNNYNNN",
"NNNNYYNYYN",
"NNNNNNYNNY",
"NNNNNNYNNY",
"NNNNNNNYYN"
}

Returns: "SPS~~S~~SPS~~S~~PS~~S~~"

The graph is depicted below with the vertices numbered.

{
"NYNNNNNYY",
"YNYNNYYNN",
"NYNYYNNNN",
"NNYNYNNNN",
"NNYYNNYNN",
"NYNNNNYNN",
"NYNNYYNNY",
"YNNNNNNNY",
"YNNNNNYYN"
}

Returns: "PPSS~PPSS~PS~~~~S~~~~S~~~"

{
"NYNNYNN",
"YNNYNNN",
"NNNYNYY",
"NYYNNNN",
"YNNNNNY",
"NNYNNNY",
"NNYNYYN"
}

Returns: "PSSSS~PS~~~~~~~"

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.