TreeAndPathLength2 | Topcoder Archive

Problem Statement

You are given ints n and s.

We want to find an undirected tree with the following properties:

The number of nodes is exactly n.
The number of simple paths of length 2 is exactly s.

A simple path of length 2 consists of two distinct edges that share a vertex.
Note that the direction of the path does not matter: A-B-C is the same path as C-B-A.

Return "Possible" (quotes for clarity) if such a tree exists and "Impossible" otherwise.

Definition

Class:: TreeAndPathLength2
Method:: possible
Parameters:: int, int
Returns:: String
Method signature:: String possible(int n, int s)
(be sure your method is public)

Constraints

n will be between 2 and 50, inclusive.
s will be between 1 and 1,000, inclusive.

Examples

```
4
```
```
3
```
```
Returns: "Possible"
```
We want a tree on n=4 vertices that will have s=3 simple paths of length 2. Let the vertices be labeled A, B, C, and D. Consider the tree that contains the edges A-B, B-C, and B-D. This tree does indeed contain exactly three simple paths of length 2. These are the paths A-B-C, A-B-D, and C-B-D.
```
4
```
```
2
```
```
Returns: "Possible"
```
In this case, one valid tree contains the edges A-B, B-C, and C-D. The two simple paths of length 2 are A-B-C and B-C-D.
```
3
```
```
2
```
```
Returns: "Impossible"
```
There is only one possible tree on 3 nodes: a path of length 2. Obviously, this tree only contains a single path of length 2. Thus, we cannot have n=3 and s=2.
```
5
```
```
4
```
```
Returns: "Possible"
```
```
50
```
```
999
```
```
Returns: "Impossible"
```
```
50
```
```
1000
```
```
Returns: "Possible"
```

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.