Connection Status:
Competition Arena > InPrePost

InPrePost

SRM 715 · 2017-02-20 · by lg5293

SRM 715 · 2017-02-20 · by lg5293 · Greedy
Class Name: InPrePost
Return Type: String
Method Name: isPossible
Arg Types: (vector<string>, vector<int>, vector<int>, vector<int>)
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.

Let "root" be a variable that contains the root of an ordered binary tree with n nodes. The nodes are numbered 1 through n in no particular order.

Consider the scenario in which we executed Antonio's code on this tree three times by making the following function calls: 

a1 = order(root, "pre")
a2 = order(root, "in")
a3 = order(root, "post")

You are given the int[]s a1, a2, a3. Is there a tree for which the above scenario is possible? In other words, is it possible to construct an ordered binary tree with n nodes such that Antonio's code would output the three given sequences a1, a2, a3 when called as shown above?

Return "Possible" if the scenario could have happened, or "Impossible" if there is no such tree.

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 50 elements, inclusive.
  • a2,a3 will have the same length as a1.
  • Each of a1,a2,a3 will be a permutation of 1 to len(a1).
Examples
0)
{"post", "in", "pre", "post", "in", "pre"}
{1,2,3,4,5}
{2,1,3,5,4}
{2,4,3,5,1}
Returns: "Possible"

A possible tree that could have generated these inputs looks as follows:

1)
{"pre", "pre", "in", "in", "post", "post"}
{1,2,3,4}
{2,4,3,1}
{4,3,2,1}
Returns: "Possible"

It is allowed for nodes to have only one child.

2)
{"post", "in", "pre", "post", "in", "pre"}
{1,2,3,4,5}
{2,1,3,5,4}
{1,4,3,5,2}
Returns: "Impossible"

This is impossible. Here is one reason: From a1 we can deduce that the root of the tree must have the label 1. However, from a3 we can deduce that the root of the tree must have the label 2. This is a contradiction.

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

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

Coding Area

Language: C++17 · define a public class InPrePost with a public method string isPossible(vector<string> s, vector<int> a1, vector<int> a2, vector<int> a3) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous