TopCoder Statistics - Problem Statement

Problem Statement

A 2-tree is a tree in which each vertex either has exactly 2 non-empty children (its left and right child), or is a leaf (has no children). Each leaf is named with an uppercase letter, and each other vertex is named with a lowercase letter.

We want to mutate a given 2-tree by swapping the locations of two of its subtrees. For example, below is shown a 2-tree and then its mutation when its subtrees rooted at C and x are swapped.

      q                      q
  x       z        ==>    C       z
 A B    C   g                   x    g
           R Q                 A B  R Q

Each 2-tree can be represented by a string consisting of the names of its vertices in the order given by a post-order traversal of the tree (see notes). Given tree, the representation of a 2-tree, and the 0-based indices of two of its vertices, return the representation of the mutated tree. If the two subtrees have any vertices in common return the 7-character string "OVERLAP". If tree is not the representation of any 2-tree, return "BADTREE".

Definition

Class:: MutateTree
Method:: newTree
Parameters:: String, int, int
Returns:: String
Method signature:: String newTree(String tree, int root1, int root2)
(be sure your method is public)

Notes

A post-order print of a 2-tree rooted at root is defined recursively as follows:if root is not a leaf post-order print the left subtree post-order print the right subtreeprint the root's letter.

Constraints

tree will contain between 1 and 50 characters, inclusive.
Each character in tree will be a letter ('A'-'Z','a'-'z').
The characters in tree will be distinct.
root1 and root2 will each be between 0 and n-1, inclusive, where n is the number of characters in tree.

Examples

"ABxCRQgzq"

3

2

Returns: "CABxRQgzq"

This is the example above, in which the subtrees rooted at C and x are swapped.
"rAB"

1

2

Returns: "BADTREE"

The post-order print of every (non-empty) 2-tree starts with a leaf.
"ABxCRQgzq"

3

7

Returns: "OVERLAP"

This is the tree shown in the problem. The two indicated subtrees are the ones rooted at C and at z. They overlap since vertex C is in both of them.
"CEGHfdbIa"

7

0

Returns: "IEGHfdbCa"
"CEGHfdbIa"

2

2

Returns: "OVERLAP"
"CEGHfdbIa"

3

2

Returns: "CEHGfdbIa"
"X"

0

0

Returns: "OVERLAP"

This tree is a legal 2-tree containing only one leaf. The subtrees are the entire tree -- they overlap.
"IPDqWmSbEa"

9

1

Returns: "BADTREE"
"e"

0

0

Returns: "BADTREE"
"FGeABCdm"

3

2

Returns: "BADTREE"
"ABaCDe"

0

5

Returns: "BADTREE"
"AaB"

1

1

Returns: "BADTREE"
"ABcDEfGHiJKlMNoQRsTUvWXyabwdekz"

3

12

Returns: "ABcMEfGHiJKlDNoQRsTUvWXyabwdekz"
"ABcDEfGHiJKlMNoQRsTUvWXyabwdekz"

24

25

Returns: "OVERLAP"
"ABcDEfGHiJKlMNoQRsTUvWXyabwdekz"

23

12

Returns: "ABcDEfGHiJKlWXyNoQRsTUvMabwdekz"
"ABcDEfGHizJKlMNoQRsTUvWXyabwdek"

12

23

Returns: "ABcDEfGHizXMNoQRsTUvWJKlyabwdek"
"ABcDEfGHizJKlMNoQRsTUvWXyabwdek"

0

1

Returns: "BAcDEfGHizJKlMNoQRsTUvWXyabwdek"
"ABcDEfGHizJKlMNoQRsTUvWXyabwdek"

9

3

Returns: "OVERLAP"
"ABcDEfg"

0

6

Returns: "OVERLAP"
"ABc"

0

1

Returns: "BAc"
"ABq"

0

1

Returns: "BAq"
"a"

0

0

Returns: "BADTREE"
"AabcBCD"

0

1

Returns: "BADTREE"
"BCa"

0

1

Returns: "CBa"
"x"

0

0

Returns: "BADTREE"
"AbC"

0

0

Returns: "BADTREE"
"ABxCRQgzq"

0

1

Returns: "BAxCRQgzq"
"c"

0

0

Returns: "BADTREE"
"AxB"

0

2

Returns: "BADTREE"
"FaBCDeg"

2

3

Returns: "BADTREE"
"ABc"

2

1

Returns: "OVERLAP"
"abcdefghijklmnopqrstuvwxyz"

5

7

Returns: "BADTREE"
"ABCDab"

0

0

Returns: "BADTREE"

Statistics

Problem Statement for "MutateTree"

Problem Statement

Definition

Notes

Constraints

Examples