Connection Status:
Competition Arena > GraphAndPairs

GraphAndPairs

SRM 721 · 2017-08-30 · by cgy4ever

SRM 721 · 2017-08-30 · by cgy4ever · Graph Theory
Class Name: GraphAndPairs
Return Type: int[]
Method Name: construct
Arg Types: (int, int)
Problem Statement

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.

Constraints

  • d will be between 2 and 50, inclusive.
  • k will be between 1 and 50,000, inclusive.
Examples
0)
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}.

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

2)
4
4
Returns: {8, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 0 }
3)
5
2
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 }
4)
2
100
Returns: {24, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 0, 11, 0, 12, 0, 13, 0, 14, 0, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23 }

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

Coding Area

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

Submitting as anonymous