Connection Status:
Competition Arena > HamiltonianConstruction

HamiltonianConstruction

SRM 704 · 2016-12-04 · by cgy4ever

SRM 704 · 2016-12-04 · by cgy4ever · Graph Theory
Class Name: HamiltonianConstruction
Return Type: String[]
Method Name: construct
Arg Types: (int)
Problem Statement

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'.

Constraints

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

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

2)
720
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.

3)
288
Returns: {"NYYYYNYY", "YNYYYYYY", "YYNYYYNY", "YYYNYYYY", "YNYYNYYY", "YYYYYNYN", "YYNYYYNY", "YYYYYNNN" }
4)
10000
Returns: {"NNNNYNNYYYNNNNYYYYYY", "YNYYYYYYYYYYYYYYYYYY", "NYNYYYYYYYYYYYYYYYYY", "NNYNYYYYYYYYYYYYYYYY", "NNNYNYYYYYYYYYYYYYYY", "NNNNYNYYYYYYYYYYYYYY", "NNNNNYNYYYYYYYYYYYYY", "NNNNNNYNYYYYYYYYYYYY", "NNNNNNNYNYYYYYYYYYYY", "NNNNNNNNYNYYYYYYYYYY", "NNNNNNNNNYNYYYYYYYYY", "NNNNNNNNNNYNYYYYYYYY", "NNNNNNNNNNNYNYYYYYYY", "NNNNNNNNNNNNYNYYYYYY", "NNNNNNNNNNNNNYNYYYYY", "NNNNNNNNNNNNNNYNYYYY", "NNNNNNNNNNNNNNNYNYYY", "NNNNNNNNNNNNNNNNYNYY", "NNNNNNNNNNNNNNNNNYNY", "NNNNNNNNNNNNNNNNNNYN" }

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

Coding Area

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

Submitting as anonymous