OddEvenTreeHard | Topcoder Archive

Problem Statement

In a tree, the distance between two nodes is the number of edges on the (only) simple path that connects them.

You are given a String[] x with N elements, each containing N characters. Draw a tree with N nodes, numbered 0 through N-1.
The tree must have the following properties:

For each i and j, if x[i][j] is one of 'E', 'O' (uppercase o), and '?'.

If x[i][j]='E', the distance between i and j must be even.
If x[i][j]='O', the distance between i and j must be odd.
If x[i][j]='?', the distance between i and j may be arbitrary.

If there is no tree with these properties, return {-1}. Otherwise, return a int[] with 2N-2 elements: the list of edges in one such tree. For example, if N=3 and your tree contains the edges 0-2 and 1-2, return {0,2,1,2}. If there are multiple correct outputs you may output any of them.

Definition

Class:: OddEvenTreeHard
Method:: getTree
Parameters:: String[]
Returns:: int[]
Method signature:: int[] getTree(String[] x)
(be sure your method is public)

Notes

If you use plugins to test your solution, be careful. Plugins cannot tell you whether your solution is correct -- they'll just tell you whether it matches the example output exactly.

Constraints

n will be between 2 and 50, inclusive.
x will contain exactly n elements.
Each element in x will have exactly n characters.
Each character in x will be 'O', 'E' or '?'.

Examples

{"EOE",
 "OEO",
 "EOE"}

Returns: {0, 1, 2, 1 }

The tree 0-1-2 is a valid solution.

{"????",
 "????",
 "????",
 "????"}

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

Any tree with 4 nodes is a valid solution.

```
{"????",
 "????",
 "??O?",
 "????"}
```
```
Returns: {-1 }
```
dist[2][2] should be zero, can't be an odd number.
```
{"??O?",
 "????",
 "E???",
 "????"}
```
```
Returns: {-1 }
```
dist[0][2] = dist[2][0], they should be both even or both odd.

{"?O??",
 "??O?",
 "???O",
 "????"}

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

{"?E??",
 "??E?",
 "???E",
 "????"}

Returns: {-1 }

{"?????????????","??????????OE?","?????????????","?????????????","?????????????","?????????????","?????????????","???????E?????","???????E?????",
"?????????????","???????????O?","???????????E?","????????????E"}

Returns: {0, 1, 0, 3, 0, 5, 0, 7, 0, 8, 0, 11, 0, 12, 2, 1, 4, 1, 6, 1, 9, 1, 10, 1 }

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.