ExactTree | Topcoder Archive

Problem Statement

In this problem, if a tree has x nodes, the nodes are numbered 0 through x-1. Given a tree T, the distance dist(i,j) between nodes i and j is the number of edges on the unique simple path that connects them. The sum of all pairwise distances in T, denoted S(T), is the sum of dist(i,j) over all pairs i,j such that i<j.

You are given ints n, m, and r. We are interested in trees with the following properties:

The tree T has exactly n nodes (labeled 0 through n-1).
S(T) modulo m equals r.

If there are such trees, return the smallest possible value S(T). Otherwise, return -1.

Definition

Class:: ExactTree
Method:: getTree
Parameters:: int, int, int
Returns:: int
Method signature:: int getTree(int n, int m, int r)
(be sure your method is public)

Constraints

n will be between 2 and 50, inclusive.
m will be between 2 and 100, inclusive.
r will be between 0 and m-1, inclusive.

Examples

```
4
```
```
100
```
```
9
```
```
Returns: 9
```
For a tree T on 4 vertices there are only two possible values of S(T): 9 and 10. (One tree that has S(T)=9 is a tree with the edges 0-1, 0-2, and 0-3. One tree that has S(T)=10 is a tree with the edges 0-1, 1-2, and 2-3.) We are only interested in trees T such that S(T) modulo 100 = 9. Given this constraint, the smallest actually possible value S(T) is 9.
```
4
```
```
100
```
```
10
```
```
Returns: 10
```
```
4
```
```
100
```
```
0
```
```
Returns: -1
```
```
6
```
```
2
```
```
0
```
```
Returns: 28
```
```
6
```
```
2
```
```
1
```
```
Returns: 25
```
```
25
```
```
100
```
```
0
```
```
Returns: 700
```
```
50
```
```
97
```
```
89
```
```
Returns: 2708
```

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.