HamiltonianCircuits | Topcoder Archive

Problem Statement

Consider a directed graph G on n vertices (labeled 0, 1, 2, ..., n-1) with exactly n*(n-1)/2 edges: for every pair of distinct vertices (i, j) there is either an edge from i to j or an edge from j to i, but not both. (Hence, if we ignore the orientation of edges, G is a complete graph.)

Let X be a String[] that contains the adjacency matrix of G. More precisely, X[i][j] = '+' denotes that G contains an edge from i to j, and X[i][j] = '-' denotes that there is no such edge. On the diagonal we have X[i][i] = '.' denoting that there are no self-loops in G.

A Hamiltonian circuit in G is a cycle of length n that contains each vertex of G exactly once. Find and return a Hamiltonian circuit in G. More precisely, return a int[] of length n: the order of vertices on one Hamiltonian circuit in G. All valid Hamiltonian circuits will be accepted. If G does not contain any Hamiltonian circuits, return an empty int[] instead.

In order to keep the input small, the array X is generated from the input parameters as described below.

You are given the following inputs:

The int n: the number of vertices.
The ints seed, a, b, and c. These are used to generate pseudorandom directions of all edges.
The int[]s d and e. These are used later to specify the directions of some edges.

Use the following pseudocode to generate X:

    value := seed
    for i = 0 .. n-1:
        X[i][i] := '.'
        for j = i+1 .. n-1:
            if (value MOD 1000) &lt;= 250:
                X[i][j] := '+' and X[j][i] := '-' // edge from i to j.
            else
                X[i][j] := '-' and X[j][i] := '+' // edge from j to i.
            value := (a * value + b) MOD c
    m := length of d
    for k = 0 .. m-1:
        X[d[k]][e[k]] := '+'
        X[e[k]][d[k]] := '-'

Definition

Class:: HamiltonianCircuits
Method:: findCircuit
Parameters:: int, int, int, int, int, int[], int[]
Returns:: int[]
Method signature:: int[] findCircuit(int n, int seed, int a, int b, int c, int[] d, int[] e)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom generator. It should solve any test case with n ≤ 1000 within the given limits.

Constraints

n will be between 3 and 1,000, inclusive.
seed will be between 1 and 10^9, inclusive.
a will be between 1 and 10^9, inclusive.
b will be between 1 and 10^9, inclusive.
c will be between 1 and 10^9, inclusive.
d will contain between 1 and 1,000 elements, inclusive.
e will contain between 1 and 1,000 elements, inclusive.
d and e will contain the same number of elements.
Each element of d will be between 0 and n-1.
Each element of e will be between 0 and n-1.
d[i] != e[i] for all i.

Examples

```
3
```
```
1
```
```
1
```
```
1
```
```
1
```
```
{0,0,1}
```
```
{1,2,2}
```
```
Returns: { }
```
The pseudocode will generate the following adjacency matrix X: .++ -.+ --. In this graph there is no Hamiltonian circuit.
```
4
```
```
1
```
```
1
```
```
1
```
```
1
```
```
{0,1,1,2,3,3}
```
```
{3,0,2,0,1,2}
```
```
Returns: {1, 2, 0, 3 }
```
For this input X looks as follows: .--+ +.+- +-.- -++. This graph has a single Hamiltonian circuit, but as you may start in any of its vertices, there are four correct outputs: {0, 3, 1, 2} {1, 2, 0, 3} {2, 0, 3, 1} {3, 1, 2, 0}
```
4
```
```
1
```
```
1
```
```
1
```
```
1
```
```
{0,0,1,2,2,3,1,0}
```
```
{1,3,2,0,3,1,0,1}
```
```
Returns: {1, 2, 0, 3 }
```
The input describes the following X: .+-+ -.+- +-.+ -+-. Note that the edge (0, 1) appeared three times in d and e (twice as (0, 1) and once as (1, 0)), but according to the problem statement's pseudocode only the last appearance matters.

{5, 4, 4, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0}

{3, 5, 2, 4, 5, 3, 0, 5, 4, 3, 2, 5, 4, 3, 1}

Returns: {3, 4, 2, 0, 1, 5 }

Here the adjacency matrix X looks as follows: .+-+++ -.++++ +-.+-+ ---.+- --+-.+ ---+-.

```
6
```
```
987654323
```
```
999777888
```
```
979797979
```
```
987654323
```
```
{0}
```
```
{1}
```
```
Returns: { }
```
Here the adjacency matrix X looks as follows: .---++ +.---- ++.+-- ++-.+- -++-.- -++++.
```
8
```
```
2018
```
```
1337
```
```
10001
```
```
10007
```
```
{0}
```
```
{2}
```
```
Returns: {3, 4, 0, 1, 2, 7, 6, 5 }
```
Here the adjacency matrix X looks as follows: .++----- -.+--+-+ --.--+-+ +++.+--- +++-.++- +--+-.-- ++++-+.- +--++++.

315301770

177340464

144591777

{45,29,34,41,36,27,28,3,20,48,44,33,20,42,0,47,1,7,5,20}

{6,8,9,2,23,7,6,22,42,19,5,21,34,8,28,22,6,21,44,29}

Returns: {47, 45, 49, 43, 42, 40, 39, 37, 36, 35, 33, 34, 32, 31, 29, 26, 30, 28, 25, 24, 20, 21, 16, 14, 18, 13, 11, 9, 8, 12, 10, 7, 5, 4, 3, 2, 1, 0, 6, 15, 17, 19, 22, 23, 27, 38, 41, 44, 46, 48 }

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.