BipartiteConstruction | Topcoder Archive

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.

Definition

Class:: BipartiteConstruction
Method:: construct
Parameters:: int
Returns:: int[]
Method signature:: int[] construct(int K)
(be sure your method is public)

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

```
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)}.
```
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.
```
0
```
```
Returns: {2, 1, 0 }
```

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 }

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.