OddEvenTree
SRM 658 · 2015-05-01 · by cgy4ever
SRM 658 · 2015-05-01 · by cgy4ever · Graph Theory
Problem Statement
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 aString[] 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 'E' the distance between i and j must be even, and if it is 'O' (uppercase o) this distance must be odd.
If there is no tree with these properties, return {-1}. Otherwise, return aint[] 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.
You are given a
If there is no tree with these properties, return {-1}. Otherwise, return a
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' or 'E'.
Examples
0)
{"EOE",
"OEO",
"EOE"}
Returns: {0, 1, 2, 1 }
The tree: 0-1-2 is a valid answer.
1)
{"EO",
"OE"}
Returns: {0, 1 }
2)
{"OO",
"OE"}
Returns: {-1 }
dist[0][0] must be 0, and it should be an even number, so it is impossible.
3)
{"EO",
"EE"}
Returns: {-1 }
dist[0][1] should be same with dist[1][0].
4)
{"EOEO",
"OEOE",
"EOEO",
"OEOE"}
Returns: {0, 1, 0, 3, 2, 1 }
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class OddEvenTree with a public method vector<int> getTree(vector<string> x) · 103 test cases · 2 s / 256 MB per case