Connection Status:
Competition Arena > BipartiteConstruction

BipartiteConstruction

SRM 693 · 2016-06-04 · by jcvb

SRM 693 · 2016-06-04 · by jcvb · Graph Theory
Class Name: BipartiteConstruction
Return Type: int[]
Method Name: construct
Arg Types: (int)
Problem Statement

Problem Statement

You are given a single int K. Your task is to construct any bipartite graph with the following properties:
  • The graph must contain n white and n black vertices, where n is between 1 and 20, inclusive. The white vertices must be numbered 0 through n-1, and the black vertices must also be numbered 0 through n-1.
  • The graph must contain between 0 and 120 edges, inclusive.
  • Each edge of the graph must connect a white and a black vertex.
  • The number of different perfect matchings in the graph must be exactly K. Note that a perfect matching in a graph is a set of edges of the graph that contains each vertex exactly once.
Note that each pair of differently-colored vertices may be connected by arbitrarily many edges. These edges are all considered distinct.
Return a int[] with the description of the graph you constructed. This int[] should have m+1 elements, where m is the number of edges in your graph. Element 0 of the return value should be n. Each of the other elements should encode one edge of your graph. An edge that connects the i-th white vertex and the j-th black vertex is encoded as the integer (i*n + j).
It is guaranteed that for the given constraints a solution always exists. If there are multiple solutions, you may return any of them.

Notes

  • A perfect matching in a graph is a set of edges of the graph that contains each vertex exactly once.

Constraints

  • K will be between 0 and 1,000,000,000, inclusive.
Examples
0)
2
Returns: {3, 8, 1, 7, 4, 3, 0 }

The edges are (2,2), (0,1), (2,1), (1,1), (1,0), (0,0). It has two different perfect matchings: {(2,2), (0,1), (1,0)} and {(2,2), (1,1), (0,0)}.

1)
5
Returns: {1, 0, 0, 0, 0, 0 }

This return value describes a graph with a single white vertex and a single black vertex. These vertices are connected by five distinct edges. Each of these edges forms a perfect matching in our graph.

2)
0
Returns: {2, 1, 0 }
3)
2333333
Returns: {20, 93, 195, 195, 211, 87, 114, 369, 390, 216, 195, 305, 17, 370, 356, 308, 150, 263, 20, 153, 331, 79, 344, 108, 114, 257, 245, 289, 211, 388, 388, 359, 293, 263, 219, 131, 201, 293, 279, 204, 97, 367, 90, 279, 308, 324, 323, 359, 338, 63, 26, 318, 218, 226, 164, 361, 276, 388, 343, 149, 17, 336, 88, 161, 76, 237, 136, 278, 302, 107, 271, 15, 382, 45, 338, 264, 78, 150, 220, 341, 180, 20, 252, 94, 114, 161 }
4)
555
Returns: {20, 21, 21, 21, 20, 42, 42, 42, 41, 63, 63, 63, 62, 84, 84, 84, 83, 105, 105, 105, 104, 126, 126, 126, 125, 147, 147, 147, 146, 168, 168, 168, 167, 189, 189, 189, 188, 210, 210, 210, 209, 231, 231, 231, 230, 252, 252, 252, 251, 273, 273, 273, 272, 294, 294, 294, 293, 315, 315, 315, 314, 336, 336, 336, 335, 357, 357, 357, 356, 378, 378, 378, 377, 399, 399, 399, 398, 18, 18, 17, 16, 16, 14, 14 }

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

Coding Area

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

Submitting as anonymous