Connection Status:
Competition Arena > BinaryTreeAndPermutation

BinaryTreeAndPermutation

SRM 712 · 2017-02-20 · by cgy4ever

SRM 712 · 2017-02-20 · by cgy4ever · Graph Theory
Class Name: BinaryTreeAndPermutation
Return Type: int[]
Method Name: findPermutation
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

A full binary tree is a rooted tree with the following property: each vertex that is not a leaf has exactly two children - a left child and a right child.

You have a full binary tree. The tree has n vertices, numbered 0 through n-1. You are given the int[]s lef and rig that describe the shape of the tree. If vertex i is a leaf we have lef[i] = rig[i] = -1. Otherwise, lef[i] is the left child and rig[i] is the right child of vertex i.

The ancestors of vertex x are the vertices on the unique path from x to the root of the tree, including x and the root. The least common ancestor of x and y, denoted LCA(x,y), is the first vertex on the path from x to the root that is also the ancestor of y. Equivalently, among all vertices that are ancestors of both x and y, LCA(x,y) is the one that is farthest away from the root.

We are looking for a permutation p of {0, 1, ..., n-1}. You are given a set of m constraints this permutation has to satisfy. More precisely, you are given the int[]s a, b, and c, each with m elements. For each valid i we get one constraint: LCA( p[a[i]], p[b[i]] ) must be c[i].

If there is at least one permutation with the above properties, find and return one such permutation. Otherwise, return an empty int[].

Constraints

  • n, m will be between 1 and 50, inclusive.
  • lef and rig will contain exactly n elements.
  • For each i, lef[i]=rig[i]=-1 or (i<lef[i],rig[i]<n and lef[i] != rig[i]).
  • lef and rig will describe a binary tree.
  • a, b, c will contain exactly m elements.
  • Each element in a, b, c will be between 0 and n-1, inclusive.
Examples
0)
{1,-1,-1}
{2,-1,-1}
{2,1}
{2,0}
{0,0}
Returns: {2, 1, 0 }

The tree looks as follows: 0 / \ 1 2 We are given two constraints: LCA( p[2], p[2] ) should be 0, and LCA( p[1], p[0] ) should also be 0. The first constraint implies that p[2] must be 0. This leaves us with two possible permutations: {2,1,0} and {1,2,0}. We can easily verify that they both satisfy the second constraint as well, so each of them is a valid answer.

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

We have the same tree and the same first constraint. The second constraint now requires that LCA( p[1], p[0] ) should be 1. As we saw in Example 0, there is no permutation p with this property.

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

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

Coding Area

Language: C++17 · define a public class BinaryTreeAndPermutation with a public method vector<int> findPermutation(vector<int> lef, vector<int> rig, vector<int> a, vector<int> b, vector<int> c) · 237 test cases · 2 s / 256 MB per case

Submitting as anonymous