LuckyTree | Topcoder Archive

Problem Statement

Cat loves making trees. Cat's friend Dog will have a birthday soon, so Cat has decided to make a special tree for Dog.

Cat likes the numbers 4 and 7. Therefore, the weight of each edge in the tree will be either 4 or 7.

Dog likes balance. A simple non-empty path in the tree is balanced if it contains the same number of weight-4 and weight-7 edges. (Note that an empty path is not balanced.) Direction does not matter: a path from X to Y is the same as a path from Y to X.

Dog's favorite number is favorite. Cat would like to encode this number into the tree as the number of balanced paths it contains.

You are given the int favorite. Find a tree that contains at most 51 vertices and has all the above properties. Return a int[] containing a description of the tree in the format specified below. If there are many such trees, you may return any of them. If there are no such trees, return an empty int[] instead.

Suppose that you want to return a tree with V vertices. (Note that V must be between 1 and 51, inclusive.) First, label those vertices 0 through V-1. Then, return a int[] X with exactly 3V-2 elements. X[0] should be the number of vertices. The rest of X should be the list of edges. More precisely: For each edge in your tree there must be an i between 0 and V-2, inclusive, such that X[3*i+1] and X[3*i+2] are the vertices connected by that edge and X[3*i+3] is the weight of the edge: either 4 or 7.

Definition

Class:: LuckyTree
Method:: construct
Parameters:: int
Returns:: int[]
Method signature:: int[] construct(int favorite)
(be sure your method is public)

Constraints

favorite will be between 1 and 1275, inclusive.

Examples

```
1
```
```
Returns: {3, 0, 1, 4, 1, 2, 7 }
```
We are looking for any tree with exactly 1 balanced path. The return value describes a tree with three vertices. There are two edges: 0-1 (weight 4) and 1-2 (weight 7). The single balanced path is the path between vertices 0 and 2.

Returns: {17, 0, 1, 4, 0, 2, 4, 0, 3, 4, 0, 4, 4, 0, 5, 4, 0, 6, 4, 0, 7, 4, 0, 8, 4, 0, 9, 7, 0, 10, 7, 0, 11, 7, 0, 12, 7, 0, 13, 7, 0, 14, 7, 0, 15, 7, 0, 16, 7 }

Returns: {15, 1, 12, 4, 1, 11, 4, 0, 1, 7, 0, 2, 7, 2, 10, 4, 2, 9, 4, 0, 4, 4, 0, 3, 4, 3, 7, 7, 3, 8, 7, 4, 5, 7, 4, 6, 7, 12, 13, 7, 13, 14, 4 }

```
1275
```
```
Returns: { }
```
It is not possible to create a tree with 1275 balanced paths using only 51 nodes.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.