ThreeColorTrees | Topcoder Archive

Problem Statement

Consider the following problem: Given a tree with N vertices, color each of them red, green or blue in such a way that:

No two red vertices are adjacent.
No two red vertices share a common neighbor.

(Note that green and blue vertices may be placed arbitrarily.)

Given N, construct any tree with at least 2.62^N valid colorings.

In order to compute the return value, root your tree in any of its vertices and label the vertices 0 through N-1 in such a way that for each vertex x, parent[x] < x. Then, return { parent[1], parent[2], ..., parent[N-1] }.

Definition

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

Notes

For N = 1, 2, 3, ..., 10 your tree should have at least 3, 7, 18, 48, 124, 324, 848, 2221, 5818, and 15241 valid colorings.

Constraints

N will be between 1 and 1000, inclusive.

Examples

```
2
```
```
Returns: {0 }
```
The only two-vertex tree has 8 valid colorings. (The only invalid coloring is the one with both vertices red.)
```
4
```
```
Returns: {0, 0, 0 }
```
A star with four vertices has exactly 48 valid colorings: 2^4 = 16 such that no vertex is red, and 4 * 2^3 = 32 such that one vertex is red.
```
6
```
```
Returns: {0, 1, 2, 3, 4 }
```
A path of length 6 has 352 valid colorings.
```
10
```
```
Returns: {0, 1, 0, 3, 4, 0, 0, 7, 8 }
```

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.