Connection Status:
Competition Arena > ThePermutationGameDiv2

ThePermutationGameDiv2

SRM 652 · 2015-01-29 · by lg5293

SRM 652 · 2015-01-29 · by lg5293 · Simple Math
Class Name: ThePermutationGameDiv2
Return Type: long
Method Name: findMin
Arg Types: (int)
Problem Statement

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.

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

1)
3
Returns: 6
2)
6
Returns: 60
3)
11
Returns: 27720
4)
25
Returns: 26771144400

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

Coding Area

Language: C++17 · define a public class ThePermutationGameDiv2 with a public method long long findMin(int N) · 36 test cases · 2 s / 256 MB per case

Submitting as anonymous