Connection Status:
Competition Arena > PreInPostOrder

PreInPostOrder

TCO22 Parallel 4 · 2022-04-14 · by misof

TCO22 Parallel 4 · 2022-04-14 · by misof · Dynamic Programming
Class Name: PreInPostOrder
Return Type: int
Method Name: reconstruct
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

A binary tree is a rooted tree in which each node has at most one left child and at most one right child.

Each N-node tree in this problem will have its nodes labeled 0 to N-1. For a fixed tree left(v) and right(v) will denote the numbers of the left and right child of node v. The special value None is used if node v does not have that child.


Consider the following three mutually recursive functions: 


function PreInPost(v):
    print(v)
    if left(v) is not None: InPostPre(left(v))
    if right(v) is not None: InPostPre(right(v))

function InPostPre(v):
    if left(v) is not None: PostPreIn(left(v))
    print(v)
    if right(v) is not None: PostPreIn(right(v))

function PostPreIn(v):
    if left(v) is not None: PreInPost(left(v))
    if right(v) is not None: PreInPost(right(v))
    print(v)

Each of these three functions has the property that if you call it with the argument equal to the root of the tree, it will output each of the tree's nodes exactly once. (As the three functions call each other in a cycle, we are cycling through printing the tree in pre-order, in-order, and post-order. Hence the function names.)


You are given the int[]s PIP and IPP. PIP contains the order in which the call PreInPost(root) printed the nodes of a tree. IPP contains the order in which the call InPostPre(root) printed the nodes of the same tree.

Count all distinct trees that match the given information. Return that count modulo (10^9 + 7).

Notes

  • Remember that you are counting binary trees with N nodes, where N is the number of elements in PIP. The nodes are labelled 0 to N-1.
  • Two trees count as identical if and only if the functions left() and right() that describe them are identical.

Constraints

  • PIP will have between 1 and 70 elements, inclusive.
  • PIP will be a permutation of 0 to N-1, where N is the number of elements in PIP.
  • IPP will have the same number of elements as PIP.
  • IPP will be a permutation of 0 to N-1, where N is the number of elements in IPP.
Examples
0)
{0, 1, 2}
{0, 2, 1}
Returns: 1

The only tree that matches these looks as follows: 0 \ 1 \ 2

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

The only matching tree has the same shape as in the previous example, only the order of node labels is different.

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

No such tree.

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

In both matching trees we have left(2)=1 and right(1)=0. One of the two matching trees has left(0)=3, the other has right(0)=3.

4)
{0, 3, 4, 2, 1, 7, 8, 6, 5, 10, 9}
{2, 3, 4, 1, 0, 6, 7, 8, 9, 10, 5}
Returns: 18
78)
{0,1,3,5,4,2}
{0,2,3,5,4,1}
Returns: 4

0 0 0 0 \ \ \ \ 1 1 1 1 \ \ \ \ 2 2 2 2 \ / \ / \ / 3 3 5 3 4 3 \ \ \ \ 4 4 5 4 / / 5 5

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

Coding Area

Language: C++17 · define a public class PreInPostOrder with a public method int reconstruct(vector<int> PIP, vector<int> IPP) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous