InvariantSets

SRM 628 · 2014-06-16 · by w10d

SRM 628 · 2014-06-16 · by w10d · Graph Theory, Recursion, Simple Math

Show categories

Class Name: InvariantSets

Return Type: long

Method Name: countSets

Arg Types: (vector<int>)

Problem Statement

Janusz is a young physicist. Recently he has been studying a dynamic system. There are n elements in the system. We will label them 0 through n-1. The set of all elements will be denoted E. Janusz models the changes in his system using a function that operates on elements of E. You are given this function as a int[] f with n elements, each between 0 and n-1, inclusive. The int[] f describes Janusz's function as follows: For each valid i, if the function is given the input i, its output will be f[i]. For Janusz, invariant subsets of E have a special significance.

A subset S of the set E is called invariant (with respect to f) if it has the following property: for any x in S, f[x] is also in S. For example, the entire set E is invariant (for any f). The empty set is always invariant as well.

Given is the int[] f. Compute and return the number of invariant subsets of E (including E itself and the empty set).

Notes

You may assume that the return value will fit into integer type long.

Constraints

f will have between 1 and 50 elements, inclusive.
Each element of f will be between 0 and n-1, inclusive, where n is the number of elements of f.

Examples

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

The invariant sets are: {}, {0,1}, {0,1,2}, {0,1,3}, {0,1,2,3}.

{1,2,0}
Returns: 2

There are only 2 invariants sets: {} and {0,1,2}.

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

The invariant sets are: {}, {0}, {0,1}, {0,1,2}, {0,1,2,3}.

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

Every set is invariant when f(x)=x for all x.

{12, 10, 0, 4, 0, 6, 3, 8, 9, 14, 1, 5, 6, 12, 5}
Returns: 90

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,19,21,22,23,24,25,26,27,28,28}
Returns: 210

Two paths.

10)

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

A lot of loops.

11)

{0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23}
Returns: 667786811

Binary tree.

15)

{0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 10, 10, 3, 10, 10, 10, 12, 10, 10, 10, 20, 20, 10, 20, 20, 20, 20, 20, 20, 20, 40, 30, 30, 30, 30, 41, 30, 30, 30, 30, 40, 40, 40, 40, 40, 0, 40, 40, 40, 40}
Returns: 13336537860225

Distorted stars.

17)

{19, 5, 13, 9, 19, 21, 4, 28, 20, 28, 1, 34, 15, 5, 19, 46, 29, 17, 26, 36, 29, 12, 2, 23, 30, 13, 3, 13, 15, 30, 36, 29, 46, 3, 0, 39, 27, 46, 31, 11, 46, 15, 1, 4, 21, 14, 14, 32, 22, 6}
Returns: 427714564

Random tests.

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

Coding Area

Language: C++17 · define a public class InvariantSets with a public method long long countSets(vector<int> f) · 36 test cases · 2 s / 256 MB per case