HamiltonianPaths
2016 TCO Final · 2016-03-24 · by lg5293
Problem Statement
You are given an undirected graph G1.
This graph has k vertices, numbered 0 through k-1.
You are given the
Finally, you are given an
- Take n distinct copies of G1. We will call them "copy 0" through "copy n-1".
- For each i, in copy i, increment the numbers of all vertices by i*k. After this change, the vertices in our graph have distinct numbers from 0 to (k*n-1).
- Take the complement of the graph you currently have. I.e., a pair of vertices is connected by an edge after this step if and only if it wasn't connected before this step.
A Hamiltonian path in G2 is a path that visits each vertex of G2 exactly once. The path may start and end in any vertex of G2. The first and the last vertex of the path do not have to be connected by an edge.
Two paths differ if their sequences of visited vertices differ. In particular, the path (0,1,2,3) differs from the path (3,2,1,0).
Count the number of Hamiltonian paths in G2. Return that count modulo 998244353 (a prime number).
Constraints
- k will be between 1 and 14, inclusive.
- a will have between 0 and k*(k-1)/2 elements, inclusive.
- b will have exactly the same number of elements as a.
- The graph described by the edges a,b will not have any self-loops or multiple edges.
- n will be between 1 and 50,000, inclusive.
3
{0,1}
{1,2}
2
Returns: 152
Our graph G1 looks as follows: 0 - 1 - 2 When constructing G2, we start by taking two copies of G1 and relabeling them: 0 - 1 - 2 3 - 4 - 5 Finally, we take the complement of this graph. The result looks as follows: ----- | | 0 1 2 |\/|\/| |/\|/\| 3 4 5 | | ----- The resulting graph does also contain the edges 0-5 and 2-3, these are not shown in the figure above. Some examples of Hamiltonian paths in this graph: 0-2-5-3-1-4 4-1-3-5-2-0 0-2-4-1-3-5 0-3-1-4-2-5 0-5-2-3-1-4
12
{}
{}
10000
Returns: 129246395
The final graph will be a complete graph with 12*10000 nodes. So, the answer in this case is (120000)! mod 998244353 = 129246395.
5
{0,1,2,3,4}
{1,2,3,4,0}
1
Returns: 10
1
{}
{}
1
Returns: 1
The resulting graph G2 has a single isolated vertex 0. There is exactly one Hamiltonian path: the path that starts in vertex 0 and ends immediately.
4
{1,2,3,2,3,3}
{0,0,0,1,1,2}
1
Returns: 0
Submissions are judged against all 157 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HamiltonianPaths with a public method int countPaths(int k, vector<int> a, vector<int> b, int n) · 157 test cases · 2 s / 256 MB per case