TreeAndPathLength2
SRM 675 · 2015-11-03 · by cgy4ever
Problem Statement
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.
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.
Constraints
- n will be between 2 and 50, inclusive.
- s will be between 1 and 1,000, inclusive.
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"
Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TreeAndPathLength2 with a public method string possible(int n, int s) · 32 test cases · 2 s / 256 MB per case