LittleTree

SRM 386 · 2008-01-05 · by eleusive

SRM 386 · 2008-01-05 · by eleusive · Dynamic Programming, Greedy, Recursion

Show categories

Class Name: LittleTree

Return Type: int

Method Name: minCost

Arg Types: (int, vector<string>, int)

Problem Statement

In a rooted tree, a vertex V is at level L if the length of the shortest path between the root and V is L. Vertex U is said to be the parent of vertex V if U and V are connected by an edge, V is at level L, and U is at level L-1. A vertex U is an ancestor of vertex V if U lies along the shortest path from the root vertex to V. More formally, U is an ancestor of V if there exists a sequence of vertices U = W₁, W₂ ,..., W_k = V, such that W_i is the parent of W_i+1 for every 1 &lt= i &lt k.

You're given a rooted tree and you wish to perform several augmentation operations on it. An augmentation operation consists of the following steps:

Choose a non-root vertex V.
Choose a vertex U, which is an ancestor of V.
Erase the edge from V to its parent.
Draw an edge from U to V so that U becomes the parent of V.

If V and U are at levels L1 and L2, respectively, then the cost of the augmentation operation described above is L1 - L2 - 1.

A tree has height K if there exists some vertex at level K and no vertex is at level K+1. Given a tree and an int height, return the smallest total cost required to perform a sequence of augmentations on the tree such that the height of the resulting tree is less than or equal to height. For example, the following diagram illustrates augmenting the subtree rooted at vertex 2, which is augmented such that vertex 2 becomes a child of vertex 0 (which is the root vertex). This is also the cheapest way of transforming this tree of height 3 into a resulting tree of height 2.


0					0
 \				       / \
  1				      2   1
   \			=>	     / \
    2				    3   4
   / \					
  3   4

The tree contains exactly N vertices, and is described by a String[] edges. Concatenate the elements of edges to form a single-space separated list of strings of the form "parent,child" (quotes for clarity). Here, parent and child are integers with no leading zeros and are between 0 and N-1, inclusive, which represents that vertex child is a child of vertex parent. Each vertex will have exactly one parent except for the root vertex. Node 0 is the root vertex.

Constraints

N will be between 2 and 100, inclusive.
height will be between 1 and N-1, inclusive.
edges will be formatted as described in the problem statement.
edges will contain between 1 and 50 elements, inclusive.
Each element of edges will contain between 1 and 50 characters, inclusive.
There will be exactly N-1 tree edges contained in edges.
edges will represent a tree.

Examples

5
{"0,1 1,2 2,3 2,4"}
2
Returns: 1

This is the example from the problem statement.

5
{"0,1 1,2 2,3 2,4"}
1
Returns: 3

The tree is the same from above, but we must get a resulting tree of height 1. One way to achieve this is to augment vertices 3 and 4 to become children of vertex 0, then augment vertex 2 to become a child of vertex 0, for a total cost of 5. However, we can do better by first augmenting the subtree rooted at vertex 2 to become a child of vertex 0, then augmenting vertices 3 and 4 to become children of vertex 0, for a total cost of 3.

3
{"0,1 1,2"}
2
Returns: 0

This tree already has a height of 2, so we don't need to perform any augmentations.

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

2
{"0,1"}
1
Returns: 0

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

Coding Area

Language: C++17 · define a public class LittleTree with a public method int minCost(int N, vector<string> edges, int height) · 91 test cases · 2 s / 256 MB per case