HeroVacation | Topcoder Archive

Problem Statement

Hero is going on a vacation to the land called Albion. Albion is a tree with n vertices, labeled 0 through n-1. You are given a description of this tree: a int[] p with n-1 elements. For each valid i, the tree contains an edge that connects the vertices (i+1) and p[i]. Before traveling to Albion, Hero is going to choose a permutation q of its vertices. Hero's visit to Albion will then look as follows:

He will fly from his home (a place outside Albion that does not matter in terms of the problem) to the vertex q[0] where his vacation will begin.
For each valid i, he will travel from the vertex q[i] to the vertex q[i+1] along the only direct path. During these travels Hero will visit each of the vertices he passes through.
Finally, he will fly from the vertex q[n-1] back home.

Hero loves sightseeing, so he would like to choose the permutation q accordingly. More precisely, we will define quality(q) as follows: For each vertex v, let cnt[v] be the number of times v is visited when Hero travels according to the permutation q. (This includes both the time when q[i]=v and all times when Hero will travel through v. See Example 1 for clarification.) Then, quality(q) is the sequence cnt[] sorted into non-increasing order. Find and return the permutation q for which quality(q) is the lexicographically largest out of all possible qualities. If there are multiple optimal solutions, you may return any one of them.

Definition

Class:: HeroVacation
Method:: getPermutation
Parameters:: int[]
Returns:: int[]
Method signature:: int[] getPermutation(int[] p)
(be sure your method is public)

Notes

Given two different sequences with the same number of elements, the lexicographically larger one is the one that has a larger value at the first index at which they differ.

Constraints

p will contain between 1 and 49 elements, inclusive.
For each i, p[i] will be between 0 and i, inclusive.

Examples

```
{0,1,2}
```
```
Returns: {1, 3, 0, 2 }
```
```
{0,1,2,3}
```
```
Returns: {2, 0, 4, 1, 3 }
```
Here, Albion is the path 0-1-2-3-4. If q is the permutation {2, 0, 4, 1, 3}, Hero will travel as follows: (2)-1-(0)-1-2-3-(4)-3-2-(1)-2-(3). (The vertices in parentheses are the ones specified by q, the other vertices are the ones visited along the way.) Thus, cnt[] = {1, 3, 4, 3, 1} and therefore quality(q) = {4, 3, 3, 1, 1}.
```
{0,0,0,0}
```
```
Returns: {0, 1, 2, 3, 4 }
```

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

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

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

Returns: {0, 6, 9, 12, 5, 8, 11, 4, 7, 10, 1, 2, 3 }

{0,1,2,0,0,5,6,6,8,9,10,11,11,13,10,9}

Returns: {8, 7, 16, 5, 15, 4, 14, 3, 13, 2, 12, 1, 11, 0, 10, 6, 9 }

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.