ThePermutationGameDiv2 | Topcoder Archive

Problem Statement

Alice and Bob are playing a game called "The Permutation Game". The game is parameterized with the int N. At the start of the game, Alice chooses a positive integer x, and Bob chooses a permutation of the first N positive integers. Let p be Bob's permutation. Alice will start at 1, and apply the permutation to this value x times. More formally, let f(1) = p[1], and f(m) = p[f(m-1)] for all m >= 2. Alice's final value will be f(x). Alice wants to choose the smallest x such that f(x) = 1 for any permutation Bob can provide. Compute and return the value of such x.

Definition

Class:: ThePermutationGameDiv2
Method:: findMin
Parameters:: int
Returns:: long
Method signature:: long findMin(int N)
(be sure your method is public)

Notes

The return value will fit into a signed 64-bit integer.
A permutation of the first N positive integers is a sequence of length N that contains each of the integers 1 through N exactly once. The i-th (1-indexed) element of a permutation p is denoted by p[i].

Constraints

N will be between 1 and 35 inclusive.

Examples

```
2
```
```
Returns: 2
```
Bob can choose the permutations {1,2} or {2,1}. If Alice chooses 1, then, Bob can choose the permutation {2,1}, which would would make f(1) = 2. However, if Alice chooses 2, no matter which permutation Bob chooses, Alice will get f(2) = 1. Thus the answer in this case is 2.
```
3
```
```
Returns: 6
```
```
6
```
```
Returns: 60
```
```
11
```
```
Returns: 27720
```
```
25
```
```
Returns: 26771144400
```

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.