CaterpillarTree
TCO05 Wildcard · 2005-08-16 · by Yarin
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
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.
{"11101011111010010001000100"}
Returns: 0
This is the leftmost picture above. Since it already is a caterpillar tree, no nodes have to be removed.
{"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.
{"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.
{"1","0"}
Returns: 0
{"11111111000110100101111100000011100101001101110001","10011000110110100111010011010001101000011101111100","01100011011001010011010101001101010100011110100101","10011000011010100011000110100111001011100110110001","10100000111110011101010011001000110101011000110011","10110100011010101000011111101010010110100010111010","10100111001101000001111110001101011110100011100110","01001001110101001100000111010011000111110001101011","10001000000110011110101000000111110101011000100110","10110111000010011101011010010011100011111001110010","10110000101110110100000111110101001110010010000110","00110101011010000011111101000110011101000100111100","11001001110011010010000001111110111100001101001001","10000110110101011100101000011101110101100011001100","11101010010001100000001111100110101000110110100100","110100001111010011000000"}
Returns: 337
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CaterpillarTree with a public method int fewestRemovals(vector<string> tree) · 92 test cases · 2 s / 256 MB per case