ExactTree
SRM 662 · 2015-06-30 · by cgy4ever
SRM 662 · 2015-06-30 · by cgy4ever · Dynamic Programming
Problem Statement
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 givenint s n, m, and r.
We are interested in trees with the following properties:
If there are such trees, return the smallest possible value S(T). Otherwise, return -1.
You are given
- 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.
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
0)
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.
1)
4 100 10 Returns: 10
2)
4 100 0 Returns: -1
3)
6 2 0 Returns: 28
4)
6 2 1 Returns: 25
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ExactTree with a public method int getTree(int n, int m, int r) · 50 test cases · 2 s / 256 MB per case