HamiltonianConstruction | Topcoder Archive

Problem Statement

Given a directed graph with n vertices, a Hamiltonian path is a directed path of length n-1 that visits each vertex exactly once.

You are given an int k. Construct a directed graph with the following properties:

The number of vertices (denoted n) is between 2 and 20, inclusive.
The vertices are numbered 0 through n-1.
There are no self-loops in the graph.
For each pair of distinct vertices u and v, there is at most one edge from u to v and at most one edge from v to u.
There are exactly k Hamiltonian paths that start in vertex 0 and end in vertex n-1.

For each k that satisfies the constraints specified below there is at least one such graph. If there are multiple such graphs, you may construct and return any of them.

In order to return a graph with n vertices, return a String[] ret with n elements, each containing n characters. For each i and j, ret[i][j] should be 'Y' if there is an edge from i to j in your graph. Otherwise, ret[i][j] should be 'N'.

Definition

Class:: HamiltonianConstruction
Method:: construct
Parameters:: int
Returns:: String[]
Method signature:: String[] construct(int k)
(be sure your method is public)

Constraints

k will be between 1 and 100,000, inclusive.

Examples

```
1
```
```
Returns: {"NY", "NN" }
```
We are looking for a graph with exactly one Hamiltonian path from vertex 0 to vertex n-1. The simplest answer is a graph with n=2 vertices and a single edge 0 -> 1. Another correct answer is a graph with two vertices that contains both the edge 0 -> 1 and the edge 1 -> 0. There are also other correct answers with more than two vertices.
```
3
```
```
Returns: {"NYYNY", "YNYYY", "YYNYY", "YNYNY", "YYYYN" }
```
This graph has 3 Hamiltonian paths from 0 to 4: 0->1->2->3->4 0->1->3->2->4 0->2->1->3->4

Returns: {"NYYYYYYY", "YNYYYYYY", "YYNYYYYY", "YYYNYYYY", "YYYYNYYY", "YYYYYNYY", "YYYYYYNY", "YYYYYYYN" }

This is a complete graph, so we have (8-2)! = 720 Hamiltonian paths from 0 to 7.

Returns: {"NYYYYNYY", "YNYYYYYY", "YYNYYYNY", "YYYNYYYY", "YNYYNYYY", "YYYYYNYN", "YYNYYYNY", "YYYYYNNN" }

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.