HiddenRabbits | Topcoder Archive

Problem Statement

You are given an undirected tree with n nodes, labeled 0 through n-1. For each valid i, there is an edge between nodes (i+1) and p[i]. There are m rabbits, numbered 0 through m-1. Each of the rabbits wants to live in one of the nodes of the tree. That node will be called its home. Multiple rabbits may share the same home. Your task is to choose the homes for all the rabbits according to some constraints.

You are given the int[] p and the int m. You are also given four equally-long int[]s: r, a, b, and x. These describe a set of constraints the homes of the rabbits have to satisfy.

Let h[j] denote the home of rabbit j. For each valid i, we have the following constraint:

If we select r[i] to be the root of the tree, the least common ancestor of the nodes h[ a[i] ] and h[ b[i] ] must be the node x[i].

Please find and return a int[] h of length m that satisfies these constraints. If there are multiple solutions, you may return any of them. If there are no solutions, return an empty int[] instead.

Definition

Class:: HiddenRabbits
Method:: whereAreTheRabbits
Parameters:: int[], int, int[], int[], int[], int[]
Returns:: int[]
Method signature:: int[] whereAreTheRabbits(int[] p, int m, int[] r, int[] a, int[] b, int[] x)
(be sure your method is public)

Constraints

p will contain between 1 and 250 elements, inclusive. (It means that the number of nodes in the tree will be between 2 and 251, inclusive.)
For each i, 0 <= p[i] <= i.
m will be between 2 and 250, inclusive.
r will contain between 1 and 250 elements, inclusive.
r, a, b, x will contain the same number of elements.
Each element in r, x will be between 0 and |p|, inclusive.
Each element in a, b will be between 0 and m-1, inclusive.
For each i, a[i] != b[i].

Examples

```
{0,1,2}
```
```
2
```
```
{2}
```
```
{0}
```
```
{1}
```
```
{1}
```
```
Returns: {1, 1 }
```
The tree looks like: 0 - 1 - 2 - 3. And we know that if we root the tree at node 2, then LCA(h[0], h[1]) = 1. That means one of them must be at node 1, and another one is at node 0 or node 1. We have 3 solutions: {0, 1}, {1, 0} and {1, 1}.
```
{0,1}
```
```
2
```
```
{0,1}
```
```
{0,1}
```
```
{1,0}
```
```
{0,1}
```
```
Returns: {0, 1 }
```
We have: If we root the tree at node 0, then LCA is 0, that means one of them is at 0. If we root the tree at node 1, then LCA is 1, that means one of them is at 1. So there are 2 answers: {0, 1}, {1, 0}.
```
{0,1,1}
```
```
3
```
```
{0,0,0,2,3,2,3,2,3}
```
```
{0,1,2,0,0,1,1,2,2}
```
```
{1,2,0,1,1,2,2,0,0}
```
```
{1,1,1,2,3,2,3,2,3}
```
```
Returns: { }
```
From first 3 constraints we know: h[0], h[1], h[2] must be in node 2 or node 3. From next 2 constraints we know: Among {h[0], h[1]}, one of them is in node 2 and another is in node 3, that means h[0] != h[1]. Next 2 constraints are similar, we have h[1] != h[2]. And last 2 gives us h[2] != h[0]. Then we have a contradiction: h[0], h[1], h[2] must be pairwise different but there are only 2 nodes to choose. So it is impossible

{0,1,2}

{2,1,0,2,1,3}

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

{2,3,1,1,3,3}

{1,2,0,2,1,3}

Returns: {0, 2, 1, 3 }

```
{0,0,0,1,0,2,3,1}
```
```
10
```
```
{3,3}
```
```
{2,6}
```
```
{6,2}
```
```
{5,0}
```
```
Returns: { }
```
LCA(h[2], h[6]) and LCA(h[6], h[2]) must be the same. So it is impossible.

{0,0,0,0,2,2,3,0,7,6,9,11,4,13,7,10,12,1,18}

{13,15,1,11,17,15,13,6,15,14,10,15,3,5,0,1,17,7,9,13,18,4,4,14,16}

{2,0,13,12,5,11,14,10,12,7,7,2,14,9,14,0,0,3,0,6,13,3,1,6,14}

{3,7,6,0,1,12,1,1,4,2,8,10,3,3,3,10,3,0,4,4,11,2,5,14,0}

{0,7,0,7,18,0,1,0,0,7,10,7,0,2,0,0,7,7,7,0,0,0,18,0,0}

Returns: {7, 18, 7, 0, 0, 18, 0, 7, 10, 2, 0, 0, 0, 0, 1 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.