TopCoder Statistics - Problem Statement

Problem Statement

Let S(n) be the set of directed graphs with n vertices labeled from 0 to n-1 such that there is exactly one outgoing edge from each vertex. Self-loops are allowed. Therefore, we have |S(n)| = nⁿ.

Given such a graph, a twirl is an operation that takes three distinct vertices labeled A, B, C and relabels them B, C, A. For example, if you choose the vertices labeled 4, 2, and 77, the following three things will happen simultaneously:

The label of the first chosen vertex will change from 4 to 2.
The label of the second chosen vertex will change from 2 to 77.
The label of the third chosen vertex will change from 77 to 4.

Two graphs are called trisomorphic if we can transform one into the other by performing a sequence of zero or more twirls.

You are given the int[] edgeTo with n elements. This int[] describes a graph G from the set S(n). For each valid i, the graph G contains an edge from vertex i to vertex edgeTo[i].

Return the number of graphs other than G that are trisomorphic to G.

Definition

Class:: TrisomorphismEasy
Method:: count
Parameters:: int[]
Returns:: int
Method signature:: int count(int[] edgeTo)
(be sure your method is public)

Constraints

n will be between 1 and 10, inclusive.
edgeTo will contain exactly n elements.
Each element of edgeTo will be between 0 and n-1, inclusive.

Examples

{1, 0}

Returns: 0

It's impossible to pick three distinct vertices when n = 2. Every graph is trisomorphic to itself only.
{2, 2, 0}

Returns: 2

The other two graphs trisomophic to the given one are {1, 2, 1} and {1, 0, 0}.
{0, 1, 2, 3}

Returns: 0

Any twirl applied to this graph keeps it unchanged.
{4, 5, 3, 1, 1, 5}

Returns: 179
{1, 2, 3, 4, 5, 6, 7, 8, 9, 9}

Returns: 1814399
{0}

Returns: 0
{0, 0}

Returns: 0
{0, 1, 2}

Returns: 0
{1, 1, 2}

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

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

Returns: 2
{2, 2, 2, 2}

Returns: 3
{0, 2, 2, 0}

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

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

Returns: 0
{4, 4, 4, 4, 4}

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

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

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

Returns: 14
{2, 2, 3, 2, 2}

Returns: 19
{0, 1, 1, 3, 0}

Returns: 29
{1, 0, 3, 0, 0}

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

Returns: 0
{0, 0, 0, 0, 0, 0}

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

Returns: 14
{4, 4, 4, 4, 5, 5}

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

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

Returns: 44
{2, 1, 2, 2, 4, 2}

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

Returns: 71
{3, 2, 2, 3, 2, 3}

Returns: 89
{5, 4, 3, 5, 3, 4}

Returns: 119
{0, 2, 0, 2, 5, 4}

Returns: 179
{5, 5, 5, 5, 3, 1}

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

Returns: 0
{6, 6, 6, 6, 6, 6, 6}

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

Returns: 20
{0, 1, 2, 3, 4, 1, 6}

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

Returns: 69
{2, 5, 2, 2, 2, 1, 2}

Returns: 104
{0, 6, 6, 6, 4, 5, 6}

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

Returns: 209
{3, 2, 2, 5, 2, 0, 2}

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

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

Returns: 359
{6, 5, 6, 3, 6, 1, 6}

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

Returns: 503
{1, 6, 1, 5, 5, 6, 6}

Returns: 629
{0, 5, 5, 0, 3, 5, 5}

Returns: 839
{0, 6, 2, 3, 3, 2, 1}

Returns: 1259
{0, 0, 5, 1, 6, 4, 6}

Returns: 2519
{0, 1, 2, 3, 4, 5, 6, 7}

Returns: 0
{1, 1, 1, 1, 1, 1, 1, 1}

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

Returns: 27
{3, 1, 3, 1, 3, 3, 3, 3}

Returns: 55
{5, 6, 3, 2, 7, 0, 1, 4}

Returns: 104
{0, 2, 7, 3, 4, 5, 6, 1}

Returns: 111
{0, 1, 2, 6, 6, 5, 6, 7}

Returns: 167
{0, 6, 2, 3, 4, 7, 1, 5}

Returns: 209
{4, 4, 4, 4, 4, 5, 6, 7}

Returns: 279
{4, 4, 4, 4, 1, 4, 1, 4}

Returns: 335
{0, 7, 2, 3, 4, 6, 1, 5}

Returns: 419
{6, 0, 6, 0, 6, 0, 0, 6}

Returns: 559
{3, 6, 4, 0, 2, 7, 1, 7}

Returns: 839
{6, 7, 0, 4, 5, 3, 2, 1}

Returns: 1119
{1, 3, 5, 7, 6, 2, 4, 0}

Returns: 1259
{0, 1, 3, 4, 7, 2, 6, 5}

Returns: 1343
{5, 5, 5, 3, 0, 0, 5, 5}

Returns: 1679
{0, 4, 2, 7, 4, 3, 6, 5}

Returns: 2239
{7, 4, 5, 4, 4, 2, 6, 0}

Returns: 2519
{2, 4, 7, 0, 6, 5, 3, 1}

Returns: 2879
{0, 3, 1, 0, 4, 1, 1, 7}

Returns: 3359
{7, 1, 6, 5, 2, 4, 3, 0}

Returns: 4031
{7, 0, 7, 7, 0, 3, 3, 7}

Returns: 5039
{2, 7, 0, 7, 7, 5, 2, 2}

Returns: 6719
{2, 2, 1, 7, 2, 6, 0, 0}

Returns: 10079
{1, 4, 7, 5, 4, 7, 1, 2}

Returns: 20159
{0, 1, 2, 3, 4, 5, 6, 7, 8}

Returns: 0
{6, 6, 6, 6, 6, 6, 6, 6, 6}

Returns: 8
{0, 1, 5, 3, 4, 2, 6, 7, 8}

Returns: 35
{7, 7, 2, 7, 7, 7, 7, 2, 7}

Returns: 71
{0, 1, 2, 6, 4, 5, 8, 7, 3}

Returns: 167
{8, 7, 8, 8, 8, 8, 8, 1, 8}

Returns: 251
{8, 1, 7, 3, 4, 5, 6, 2, 0}

Returns: 377
{0, 1, 2, 3, 2, 5, 6, 4, 8}

Returns: 503
{3, 1, 2, 3, 3, 3, 6, 7, 3}

Returns: 629
{0, 5, 3, 1, 4, 2, 6, 7, 8}

Returns: 755
{7, 6, 8, 4, 3, 5, 1, 0, 2}

Returns: 944
{8, 8, 8, 6, 8, 8, 7, 3, 8}

Returns: 1007
{0, 6, 2, 4, 3, 7, 1, 5, 8}

Returns: 1259
{5, 8, 5, 5, 5, 5, 5, 8, 5}

Returns: 1511
{6, 3, 3, 3, 3, 3, 0, 8, 7}

Returns: 1889
{1, 5, 6, 4, 8, 0, 7, 2, 3}

Returns: 2239
{3, 7, 7, 3, 7, 3, 7, 7, 3}

Returns: 2519
{7, 0, 0, 0, 0, 7, 0, 0, 8}

Returns: 3023
{2, 1, 3, 0, 4, 5, 8, 6, 7}

Returns: 3359
{2, 6, 2, 7, 5, 4, 1, 3, 2}

Returns: 3779
{0, 8, 2, 6, 6, 6, 6, 7, 1}

Returns: 5039
{7, 5, 4, 4, 2, 1, 8, 0, 6}

Returns: 7559
{8, 2, 3, 5, 6, 7, 4, 1, 0}

Returns: 9071
{6, 2, 2, 2, 6, 5, 5, 2, 6}

Returns: 10079
{5, 0, 1, 4, 6, 2, 8, 7, 3}

Returns: 11339
{1, 1, 5, 7, 3, 4, 1, 2, 1}

Returns: 12095
{0, 4, 4, 4, 7, 7, 4, 8, 7}

Returns: 15119
{2, 5, 6, 0, 1, 7, 3, 8, 4}

Returns: 18143
{7, 6, 2, 3, 0, 5, 8, 4, 8}

Returns: 20159
{4, 5, 2, 3, 6, 1, 4, 8, 7}

Returns: 22679
{8, 3, 6, 7, 1, 2, 4, 5, 0}

Returns: 25919
{3, 3, 4, 6, 3, 7, 6, 5, 3}

Returns: 30239
{6, 7, 8, 6, 2, 0, 6, 4, 1}

Returns: 36287
{7, 2, 1, 0, 3, 6, 5, 3, 4}

Returns: 45359
{6, 2, 8, 7, 6, 7, 4, 3, 2}

Returns: 60479
{3, 4, 1, 8, 2, 1, 8, 7, 0}

Returns: 90719
{8, 5, 4, 6, 1, 8, 0, 2, 4}

Returns: 181439
{6, 6, 6, 6, 6, 6, 6, 6, 6, 6}

Returns: 9
{3, 3, 3, 2, 3, 3, 3, 3, 3, 3}

Returns: 89
{6, 6, 6, 6, 6, 9, 6, 6, 6, 5}

Returns: 359
{5, 3, 3, 5, 3, 3, 3, 3, 3, 3}

Returns: 719
{2, 1, 2, 3, 2, 2, 2, 2, 8, 2}

Returns: 839
{0, 0, 2, 3, 0, 0, 6, 7, 8, 0}

Returns: 1259
{3, 1, 0, 2, 1, 1, 1, 1, 1, 1}

Returns: 1679
{5, 5, 5, 3, 4, 8, 5, 5, 8, 5}

Returns: 2519
{0, 8, 0, 8, 8, 0, 0, 0, 8, 8}

Returns: 3149
{4, 9, 4, 4, 4, 7, 4, 5, 4, 1}

Returns: 3779
{5, 7, 5, 5, 5, 7, 5, 7, 5, 9}

Returns: 5039
{8, 1, 0, 3, 0, 0, 0, 7, 8, 9}

Returns: 6299
{8, 8, 3, 9, 8, 8, 8, 2, 8, 7}

Returns: 7559
{8, 0, 4, 4, 4, 5, 4, 4, 1, 4}

Returns: 10079
{0, 2, 2, 3, 9, 2, 2, 2, 8, 4}

Returns: 12599
{1, 0, 4, 4, 4, 9, 4, 4, 4, 4}

Returns: 15119
{4, 4, 4, 8, 6, 7, 4, 5, 3, 4}

Returns: 18899
{0, 1, 5, 5, 4, 5, 5, 6, 5, 9}

Returns: 25199
{5, 6, 4, 4, 0, 6, 5, 4, 4, 4}

Returns: 30239
{9, 3, 8, 3, 0, 3, 3, 2, 7, 4}

Returns: 33599
{0, 8, 4, 4, 3, 5, 4, 4, 1, 4}

Returns: 37799
{7, 7, 7, 8, 8, 5, 8, 9, 9, 9}

Returns: 50399
{9, 2, 1, 9, 8, 6, 9, 6, 4, 6}

Returns: 56699
{0, 2, 2, 7, 0, 2, 0, 2, 0, 0}

Returns: 75599
{2, 6, 1, 2, 4, 2, 9, 7, 8, 1}

Returns: 100799
{5, 6, 0, 8, 2, 4, 8, 6, 6, 8}

Returns: 113399
{2, 4, 5, 7, 0, 1, 7, 9, 7, 7}

Returns: 120959
{1, 4, 5, 1, 5, 1, 1, 1, 8, 4}

Returns: 151199
{0, 2, 7, 5, 8, 4, 5, 1, 0, 5}

Returns: 201599
{7, 0, 6, 0, 0, 6, 0, 0, 3, 3}

Returns: 226799
{6, 2, 9, 5, 8, 7, 4, 5, 5, 5}

Returns: 1814399
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Returns: 0
{4, 4, 6, 0, 0, 1, 3, 9, 2, 3}

Returns: 1814399
{6, 6, 8, 7, 0, 7, 4, 1, 0, 0}

Returns: 1814399
{9, 2, 6, 1, 5, 5, 1, 2, 1, 9}

Returns: 907199
{7, 3, 4, 3, 7, 3, 3, 7, 8, 7}

Returns: 302399
{9, 5, 4, 9, 6, 2, 1, 8, 9, 3}

Returns: 362879
{1, 4, 1, 2, 5, 1, 6, 2, 8, 1}

Returns: 453599
{0, 2, 8, 2, 0, 8, 0, 2, 5, 6}

Returns: 604799
{9, 5, 1, 8, 3, 6, 9, 8, 3, 2}

Returns: 907199
{7, 6, 4, 8, 6, 0, 3, 9, 4, 3}

Returns: 1814399
{2, 2, 0 }

Returns: 2
{0, 4, 7, 1, 5, 4, 2, 8, 4, 6 }

Returns: 1814399
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: 0
{1, 2, 3, 4, 5, 6, 7, 8, 9, 9 }

Returns: 1814399

Statistics

Problem Statement for "TrisomorphismEasy"

Problem Statement

Definition

Constraints

Examples