Connection Status:
Competition Arena > TreeAndPathLength3

TreeAndPathLength3

SRM 675 · 2015-11-03 · by cgy4ever

SRM 675 · 2015-11-03 · by cgy4ever · Graph Theory
Class Name: TreeAndPathLength3
Return Type: int[]
Method Name: construct
Arg Types: (int)
Problem Statement

Problem Statement

You are given an int s. Your task is to construct an undirected tree such that:
  • The number of nodes is between 1 and 500, inclusive.
  • The number of simple paths of length 3 in the tree is exactly s.
Note that the direction of the simple path does not matter: A-B-C-D is the same simple path as D-C-B-A.

It is guaranteed that for the constraints used in this task a tree with the required properties always exists. Find one such tree.

If your tree has n nodes, they must be labeled 0 through n-1. Return a int[] with (n-1)*2 elements. For each valid i, elements 2i and 2i+1 of the return value should be the endpoints of one of the edges in your tree.
If there are multiple correct solutions, you may return any of them.

Constraints

  • s will be between 1 and 10,000, inclusive.
Examples
0)
1
Returns: {0, 1, 1, 2, 2, 3 }

The return value has 6 elements, so it has to describe a tree on 4 vertices. This tree contains the edges 0-1, 1-2, and 2-3. We can easily verify that this tree does indeed contain exactly one simple path of length 3: the path 0-1-2-3.

1)
2
Returns: {0, 1, 1, 2, 2, 3, 3, 4 }

The returned tree has 5 vertices. The two simple paths of length 3 in this tree are the paths 0-1-2-3 and 1-2-3-4.

2)
6
Returns: {0, 1, 1, 2, 0, 3, 3, 4, 0, 5, 5, 6 }

The six simple paths of length 3 in this tree are the following paths: 2-1-0-3, 2-1-0-5, 4-3-0-1, 4-3-0-5, 6-5-0-1, and 6-5-0-3.

3)
8
Returns: {0, 1, 1, 2, 1, 3, 3, 4, 3, 5, 5, 6, 5, 7 }
4)
10000
Returns: {0, 99, 1, 99, 2, 99, 3, 99, 4, 99, 5, 99, 6, 99, 7, 99, 8, 99, 9, 99, 10, 99, 11, 99, 12, 99, 13, 99, 14, 99, 15, 99, 16, 99, 17, 99, 18, 99, 19, 99, 20, 99, 21, 99, 22, 99, 23, 99, 24, 99, 25, 99, 26, 99, 27, 99, 28, 99, 29, 99, 30, 99, 31, 99, 32, 99, 33, 99, 34, 99, 35, 99, 36, 99, 37, 99, 38, 99, 39, 99, 40, 99, 41, 99, 42, 99, 43, 99, 44, 99, 45, 99, 46, 99, 47, 99, 48, 99, 49, 99, 50, 99, 51, 99, 52, 99, 53, 99, 54, 99, 55, 99, 56, 99, 57, 99, 58, 99, 59, 99, 60, 99, 61, 99, 62, 99, 63, 99, 64, 99, 65, 99, 66, 99, 67, 99, 68, 99, 69, 99, 70, 99, 71, 99, 72, 99, 73, 99, 74, 99, 75, 99, 76, 99, 77, 99, 78, 99, 79, 99, 80, 99, 81, 99, 82, 99, 83, 99, 84, 99, 85, 99, 86, 99, 87, 99, 88, 99, 89, 99, 90, 99, 91, 99, 92, 99, 93, 99, 94, 99, 95, 99, 96, 99, 97, 99, 98, 99, 99, 100, 100, 101, 101, 102, 100, 103, 100, 104, 100, 105, 100, 106, 100, 107, 100, 108, 100, 109, 100, 110, 100, 111, 100, 112, 100, 113, 100, 114, 100, 115, 100, 116, 100, 117, 100, 118, 100, 119, 100, 120, 100, 121, 100, 122, 100, 123, 100, 124, 100, 125, 100, 126, 100, 127, 100, 128, 100, 129, 100, 130, 100, 131, 100, 132, 100, 133, 100, 134, 100, 135, 100, 136, 100, 137, 100, 138, 100, 139, 100, 140, 100, 141, 100, 142, 100, 143, 100, 144, 100, 145, 100, 146, 100, 147, 100, 148, 100, 149, 100, 150, 100, 151, 100, 152, 100, 153, 100, 154, 100, 155, 100, 156, 100, 157, 100, 158, 100, 159, 100, 160, 100, 161, 100, 162, 100, 163, 100, 164, 100, 165, 100, 166, 100, 167, 100, 168, 100, 169, 100, 170, 100, 171, 100, 172, 100, 173, 100, 174, 100, 175, 100, 176, 100, 177, 100, 178, 100, 179, 100, 180, 100, 181, 100, 182, 100, 183, 100, 184, 100, 185, 100, 186, 100, 187, 100, 188, 100, 189, 100, 190, 100, 191, 100, 192, 100, 193, 100, 194, 100, 195, 100, 196, 100, 197, 100, 198, 100, 199, 100, 200, 100, 201 }

Submissions are judged against all 39 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TreeAndPathLength3 with a public method vector<int> construct(int s) · 39 test cases · 2 s / 256 MB per case

Submitting as anonymous