Connection Status:
Competition Arena > HamiltonianCircuits

HamiltonianCircuits

SRM 733 · 2018-04-13 · by ltdtl

SRM 733 · 2018-04-13 · by ltdtl · Graph Theory, Greedy
Class Name: HamiltonianCircuits
Return Type: int[]
Method Name: findCircuit
Arg Types: (int, int, int, int, int, vector<int>, vector<int>)
Problem Statement

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) <= 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]] := '-'

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
0)
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.

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

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

3)
6
1
1
1
1
{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: .+-+++ -.++++ +-.+-+ ---.+- --+-.+ ---+-.

4)
6
987654323
999777888
979797979
987654323
{0}
{1}
Returns: { }

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

5)
8
2018
1337
10001
10007
{0}
{2}
Returns: {3, 4, 0, 1, 2, 7, 6, 5 }

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

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

Coding Area

Language: C++17 · define a public class HamiltonianCircuits with a public method vector<int> findCircuit(int n, int seed, int a, int b, int c, vector<int> d, vector<int> e) · 189 test cases · 2 s / 256 MB per case

Submitting as anonymous