Connection Status:
Competition Arena > OddEvenTreeHard

OddEvenTreeHard

SRM 658 · 2015-05-01 · by cgy4ever

SRM 658 · 2015-05-01 · by cgy4ever · Brute Force
Class Name: OddEvenTreeHard
Return Type: int[]
Method Name: getTree
Arg Types: (vector<string>)
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 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.

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
0)
{"EOE",
 "OEO",
 "EOE"}
Returns: {0, 1, 2, 1 }

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

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

Any tree with 4 nodes is a valid solution.

2)
{"????",
 "????",
 "??O?",
 "????"}
Returns: {-1 }

dist[2][2] should be zero, can't be an odd number.

3)
{"??O?",
 "????",
 "E???",
 "????"}
Returns: {-1 }

dist[0][2] = dist[2][0], they should be both even or both odd.

4)
{"?O??",
 "??O?",
 "???O",
 "????"}
Returns: {0, 1, 0, 3, 2, 1 }

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

Coding Area

Language: C++17 · define a public class OddEvenTreeHard with a public method vector<int> getTree(vector<string> x) · 78 test cases · 2 s / 256 MB per case

Submitting as anonymous