Connection Status:
Competition Arena > HeroVacation

HeroVacation

SRM 726 · 2017-12-18 · by subscriber

SRM 726 · 2017-12-18 · by subscriber · Graph Theory
Class Name: HeroVacation
Return Type: int[]
Method Name: getPermutation
Arg Types: (vector<int>)
Problem Statement

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:
  1. 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.
  2. 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.
  3. 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.

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

2)
{0,0,0,0}
Returns: {0, 1, 2, 3, 4 }
3)
{0,1,0,2,0,2,2,5}
Returns: {1, 8, 7, 5, 6, 3, 4, 0, 2 }
4)
{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 }

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

Coding Area

Language: C++17 · define a public class HeroVacation with a public method vector<int> getPermutation(vector<int> p) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous