Connection Status:
Competition Arena > ThePermutationGame

ThePermutationGame

SRM 652 · 2015-01-29 · by lg5293

SRM 652 · 2015-01-29 · by lg5293 · Brute Force, Simple Math
Class Name: ThePermutationGame
Return Type: int
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 modulo 1,000,000,007.

Notes

  • 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 100,000 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)
11
Returns: 27720
3)
102
Returns: 53580071
4)
9999
Returns: 927702802

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

Coding Area

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

Submitting as anonymous