Connection Status:
Competition Arena > PreInPost

PreInPost

SRM 715 · 2017-02-20 · by lg5293

SRM 715 · 2017-02-20 · by lg5293 · Advanced Math, Brute Force
Class Name: PreInPost
Return Type: int[]
Method Name: findMissing
Arg Types: (vector<string>, vector<int>, vector<int>, string, string)
Problem Statement

Problem Statement

An ordered binary tree is a rooted binary tree in which each node X contains two pointers: X.left and X.right. Each of these pointers either points to the corresponding child node, or it has a special value "None" meaning that node X doesn't have the corresponding child.

I just taught Antonio some tree traversal techniques on ordered binary trees. I asked him to implement these tree traversals but I don't think he was paying attention, since he mixed them up and wrote the following pseudocode: 

def order(v, mode):
    if v == None:
        return []
    if mode == "pre":
       return [v.label] + order(v.left, s[0]) + order(v.right, s[1])
    if mode == "in":
       return order(v.left, s[2]) + [v.label] + order(v.right, s[3])
    if mode == "post":
       return order(v.left, s[4]) + order(v.right, s[5]) + [v.label]

You are given the String[] s used in the pseudocode above. You are guaranteed that among {s[0], s[2], s[4]} and also among {s[1], s[3], s[5]} each of the strings "pre", "in", and "post" appears exactly once.

I have a rooted binary tree with n nodes. The nodes of the tree are labeled 1 through n, in no particular order. The root of the tree is stored in a variable called root.

You are given Strings e1 and e2. It is guaranteed that these are two of the three strings "pre", "in", and "post". Let e3 be the third, unused string.

You are also given int[]s a1 and a2, each of length n, and each containing a permutation of numbers 1 through n.

Consider the scenario in which we executed Antonio's code twice, as follows: 

a1 = order(root, e1)
a2 = order(root, e2)

Is there a tree for which this scenario is possible? If there is no tree that corresponds to the given a1, a2, e1, and e2, return an empty int[]. Otherwise, suppose that we also executed the third matching command: 

a3 = order(root, e3)

Find and return a3. If there are multiple solutions, you may return any of them.

Constraints

  • s will contain exactly 6 elements.
  • Each element of s will be one of "pre", "in", "post".
  • Among {s[0], s[2], s[4]} and {s[1], s[3], s[5]}, each of "pre", "in", "post" appears exactly once.
  • a1 will have between 1 and 200 elements, inclusive.
  • a2 will have the same length as a1.
  • Both a1,a2 will be a permutation of 1 to len(a1).
  • e1,e2 will each be one of "pre", "in", "post".
  • e1 will be different from e2.
Examples
0)
{"post", "in", "pre", "post", "in", "pre"}
{1,2,3,4,5}
{2,4,3,5,1}
"pre"
"post"
Returns: {2, 1, 3, 5, 4 }

Here you are supposed to return the result of order(root, "in") The returned result corresponds to the following rooted tree: Another possible answer is {4,2,3,1,5}, which corresponds to the following tree:

1)
{"post", "in", "pre", "post", "in", "pre"}
{2,1,3,5,4}
{1,2,3,4,5}
"in"
"pre"
Returns: {2, 4, 3, 5, 1 }
2)
{"pre", "pre", "in", "in", "post", "post"}
{1,2,3,4,5,6,7,8,9,10}
{10,9,8,7,6,5,4,3,2,1}
"post"
"pre"
Returns: {10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

It is allowed for nodes to have only one child.

3)
{"pre", "pre", "in", "in", "post", "post"}
{1}
{1}
"post"
"in"
Returns: {1 }
4)
{"pre", "in", "post", "pre", "in", "post"}
{9,3,4,1,6,5,2,7,8}
{3,9,1,4,2,7,8,5,6}
"in"
"post"
Returns: {6, 1, 9, 3, 4, 5, 8, 7, 2 }
5)
{"pre", "in", "in", "post", "post", "pre"}
{1,2,3}
{2,3,1}
"post"
"pre"
Returns: { }

In this case there is no solution.

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

Coding Area

Language: C++17 · define a public class PreInPost with a public method vector<int> findMissing(vector<string> s, vector<int> a1, vector<int> a2, string e1, string e2) · 157 test cases · 2 s / 256 MB per case

Submitting as anonymous