SRM 712 Editorials Contest - Div I - Hard - BinaryTreeAndPermutation

DETAILED REQUIREMENTS

 

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[].

Definition

    
Class:BinaryTreeAndPermutation
Method:findPermutation
Parameters:int[], int[], int[], int[], int[]
Returns:int[]
Method signature:int[] findPermutation(int[] lef, int[] rig, int[] a, int[] b, int[] c)
(be sure your method is public)

Limits

    
Time limit (s):2.000
Memory limit (MB):256
Stack limit (MB):256

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: { }

5)    

{1,3,5,-1,-1,7,-1,-1,-1}

 

{2,4,6,-1,-1,8,-1,-1,-1}

 

{6,6,7,7,3,8,5,3}

 

{4,3,7,1,0,0,0,5}

 

{1,0,1,0,2,2,2,5}

 

Returns: {2, 0, 7, 5, 4, 8, 3, 1, 6 }

PRIZES
---Topcoder Editor T-shirt. If your editorial is published
---Additional cash prizes, once your count of published editorials reaches 10. Please refer below.
---First 10 editorials published, a crash prize of $50.
---Next 15 editorials published, a crash prize of $100.

Once your count of published editorials reaches 25 we will reset the count to 0.