Connection Status:
Competition Arena > NormalizingTrees

NormalizingTrees

SRM 348 · 2007-05-09 · by soul-net

SRM 348 · 2007-05-09 · by soul-net · Graph Theory, Greedy, Recursion
Class Name: NormalizingTrees
Return Type: int[]
Method Name: normalize
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Trees are important data structures in programming. In this problem, you will be given a tree that was constructed from a fully connected undirected acyclic graph with exactly N nodes. First, a distinct number between 0 and N-1, inclusive, was assigned to each node. Then, one of the nodes was selected to be the root of the tree. Finally, each non-root node was assigned its neighbor closest to the root as its parent.

You will be given the tree as a int[], where the i-th element is the parent of the i-th node, or -1 if the i-th node is the root (indices are 0-based). A tree is considered equivalent to this tree if it can be constructed from the same original graph using the method described above. This means you can renumber the nodes and select a different node as the root (see examples for clarification). Return a int[] containing the equivalent tree that comes first lexicographically. A int[] a1 comes before int[] a2 lexicographically if a1 has a smaller value at the first element where they differ.

Constraints

  • tree will contain between 1 and 50 elements, inclusive.
  • Each element of tree will be between -1 and N-1, inclusive, where N is the number of elements in tree.
  • Exactly one element of tree will be -1.
  • tree will represent a connected acyclic graph.
Examples
0)
{2,0,-1,4,2,4}
Returns: {-1, 0, 0, 0, 1, 4 }

This is the original drawing (with 2 as the root): 2 / \ 0 4 / / \ 1 3 5 The renumbering gives this: 1 / \ 4 0 / / \ 5 2 3 and taking the new 0 as the root gives the answer: 0 / | \ 1 2 3 | 4 | 5

1)
{-1,0,1,2,3}
Returns: {-1, 0, 0, 1, 2 }

This is a simple path of length 5. Selecting the middle node as root and renumbering gives the lexicographically first representation.

2)
{3,3,3,4,-1,3}
Returns: {-1, 0, 0, 0, 0, 0 }

This tree has the shape of a star (one center node with 5 nodes connected to it).

3)
{10,9,6,10,6,9,7,-1,9,7,7,10,6}
Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6 }
4)
{-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6}
Returns: {-1, 0, 0, 0, 0, 1, 1, 5, 5, 5, 6, 6, 6 }

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

Coding Area

Language: C++17 · define a public class NormalizingTrees with a public method vector<int> normalize(vector<int> tree) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous