TreeAndPathLength3 | Topcoder Archive

Problem Statement

You are given an int s. Your task is to construct an undirected tree such that:

The number of nodes is between 1 and 500, inclusive.
The number of simple paths of length 3 in the tree is exactly s.

Note that the direction of the simple path does not matter: A-B-C-D is the same simple path as D-C-B-A.

It is guaranteed that for the constraints used in this task a tree with the required properties always exists. Find one such tree.

If your tree has n nodes, they must be labeled 0 through n-1. Return a int[] with (n-1)*2 elements. For each valid i, elements 2i and 2i+1 of the return value should be the endpoints of one of the edges in your tree.
If there are multiple correct solutions, you may return any of them.

Definition

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

Constraints

s will be between 1 and 10,000, inclusive.

Examples

```
1
```
```
Returns: {0, 1, 1, 2, 2, 3 }
```
The return value has 6 elements, so it has to describe a tree on 4 vertices. This tree contains the edges 0-1, 1-2, and 2-3. We can easily verify that this tree does indeed contain exactly one simple path of length 3: the path 0-1-2-3.
```
2
```
```
Returns: {0, 1, 1, 2, 2, 3, 3, 4 }
```
The returned tree has 5 vertices. The two simple paths of length 3 in this tree are the paths 0-1-2-3 and 1-2-3-4.
```
6
```
```
Returns: {0, 1, 1, 2, 0, 3, 3, 4, 0, 5, 5, 6 }
```
The six simple paths of length 3 in this tree are the following paths: 2-1-0-3, 2-1-0-5, 4-3-0-1, 4-3-0-5, 6-5-0-1, and 6-5-0-3.

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

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.