Connection Status:
Competition Arena > HiddenRabbits

HiddenRabbits

TCO17 Round 3A · 2017-03-31 · by cgy4ever

TCO17 Round 3A · 2017-03-31 · by cgy4ever · Graph Theory
Class Name: HiddenRabbits
Return Type: int[]
Method Name: whereAreTheRabbits
Arg Types: (vector<int>, int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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)
{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}.

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}.

2)
{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

3)
{0,1,2}
4
{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 }
4)
{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.

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

Coding Area

Language: C++17 · define a public class HiddenRabbits with a public method vector<int> whereAreTheRabbits(vector<int> p, int m, vector<int> r, vector<int> a, vector<int> b, vector<int> x) · 176 test cases · 2 s / 256 MB per case

Submitting as anonymous