Statistics

Problem Statement for "TreeAndPathLength2"

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

  1. 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.

  2. 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. 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.

  4. 5

    4

    Returns: "Possible"

  5. 50

    999

    Returns: "Impossible"

  6. 50

    1000

    Returns: "Possible"

  7. 50

    49

    Returns: "Possible"

  8. 50

    48

    Returns: "Possible"

  9. 50

    47

    Returns: "Impossible"

  10. 50

    123

    Returns: "Possible"

  11. 50

    124

    Returns: "Possible"

  12. 50

    125

    Returns: "Possible"

  13. 50

    126

    Returns: "Possible"

  14. 50

    53

    Returns: "Possible"

  15. 48

    456

    Returns: "Possible"

  16. 2

    1

    Returns: "Impossible"

  17. 3

    1

    Returns: "Possible"

  18. 3

    2

    Returns: "Impossible"

  19. 2

    1000

    Returns: "Impossible"

  20. 10

    25

    Returns: "Impossible"

  21. 10

    20

    Returns: "Possible"

  22. 10

    8

    Returns: "Possible"

  23. 10

    36

    Returns: "Possible"

  24. 10

    35

    Returns: "Impossible"

  25. 45

    75

    Returns: "Possible"

  26. 45

    666

    Returns: "Possible"

  27. 49

    999

    Returns: "Impossible"

  28. 5

    10

    Returns: "Impossible"

  29. 6

    3

    Returns: "Impossible"

  30. 7

    14

    Returns: "Impossible"

  31. 5

    5

    Returns: "Impossible"

  32. 7

    5

    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.
This problem was used for: