TopCoder problem "CaterpillarTree" used in TCO05 Wildcard (Division I Level One)



Problem Statement

    

A caterpillar tree is a tree in which every node is on a central stalk or only one graph edge away from the stalk. The figure below illustrates to the left a caterpillar tree with 14 nodes (the stalk marked in blue), and on the right a non-caterpillar tree with 9 nodes.



Given the description of a tree, determine the least number of nodes that must be removed for the tree to become a caterpillar tree. The tree will be described as a string of 0's and 1's. Starting from some node in the tree, a '1' in the string traverses the tree to a previously unvisited node, while a '0' backtracks to the previous node. The trees in the figure above would be described as "11101011111010010001000100" and "1111100100110000", respectively, if the traversals starts at node 1 and the nodes are visited in the numbered orders.

Create a class CaterpillarTree containing the method fewestRemovals which takes a String[] tree containing the description of the tree (concatenate the elements to get the full description), and returns an int containing the fewest number of nodes that must be removed for the tree to become a caterpillar tree.

 

Definition

    
Class:CaterpillarTree
Method:fewestRemovals
Parameters:String[]
Returns:int
Method signature:int fewestRemovals(String[] tree)
(be sure your method is public)
    
 

Constraints

-tree will contain between 1 and 50 elements, inclusive.
-Each element in tree will only contain the characters '0' and '1'.
-Each element in tree will contain between 1 and 50 characters, inclusive.
-tree will describe a valid tree.
 

Examples

0)
    
{"11101011111010010001000100"}
Returns: 0
This is the leftmost picture above. Since it already is a caterpillar tree, no nodes have to be removed.
1)
    
{"1111100100110000"}
Returns: 1
This is the rightmost picture. One of the leaf nodes to the left must be removed for it to become a caterpillar tree.
2)
    
{"1111100000",
 "1111100000",
 "1111100000",
 "1111100000",
 "1111100000"}
Returns: 12
This is a star graph, with one node in the center and five arms containing five nodes each. If we delete four of the five nodes in three of the arms, we end up with a graph that is a caterpillar tree.
3)
    
{"1","0"}
Returns: 0
4)
    
{"11110100111100100111100110100110001110101001111000",
 "1101100000011100110000111001101100010000"}
Returns: 23

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4818

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8095&pm=4818

Writer:

Yarin

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Graph Theory, Recursion