GraphAndPairs | Topcoder Archive

Problem Statement

Let G be a simple undirected graph. An unordered pair {a, b} of nodes in G is called a good pair if a and b are in the same connected component of G and the distance between a and b is exactly d. (The distance between two nodes is the smallest number of edges on a path from one node to the other.)

You are given the int d and an int k. Construct an undirected graph G with the following properties:

The graph must be simple (i.e., no self-loops and no multiple edges).
The number of nodes n must be between 3 and 1,000, inclusive.
The nodes must be numbered 0 through n-1.
The number of edges m must be between 2 and 1,000, inclusive.
The graph must contain exactly k good pairs of nodes.

Return a int[] with a description of the graph G you constructed: its number of vertices followed by a list of its edges. More precisely, the description should have the form {n, a[0], b[0], a[1], b[1], ..., a[m-1], b[m-1]}, where n is the number of nodes, and for each i the graph contains an edge between a[i] and b[i].

You may assume that each valid test case has a solution. If there are multiple solutions, you may return any of them.

Definition

Class:: GraphAndPairs
Method:: construct
Parameters:: int, int
Returns:: int[]
Method signature:: int[] construct(int d, int k)
(be sure your method is public)

Constraints

d will be between 2 and 50, inclusive.
k will be between 1 and 50,000, inclusive.

Examples

```
2
```
```
1
```
```
Returns: {4, 0, 1, 1, 3, 3, 2, 2, 0, 1, 2 }
```
The graph looks as follows: Â Â Â Â 0 - 1 | / | 2 - 3 The only good pair of vertices is {0, 3}.
```
2
```
```
2
```
```
Returns: {8, 0, 1, 1, 3, 3, 2, 2, 0, 1, 2, 4, 5, 5, 7, 7, 6, 6, 4, 5, 6 }
```
This time the graph looks as follows: Â Â Â Â 0 - 1 4 - 5 | / | | / | 2 - 3 6 - 7 The good pairs are {0, 3} and {4, 7}.

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

Returns: {10, 0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 9, 0, 5, 1, 6, 2, 7, 3, 8, 4, 9 }

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.