Statistics

Problem Statement for "ThePermutationGameDiv2"

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

  1. 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.

  2. 3

    Returns: 6

  3. 6

    Returns: 60

  4. 11

    Returns: 27720

  5. 25

    Returns: 26771144400

  6. 4

    Returns: 12

  7. 5

    Returns: 60

  8. 7

    Returns: 420

  9. 8

    Returns: 840

  10. 9

    Returns: 2520

  11. 10

    Returns: 2520

  12. 12

    Returns: 27720

  13. 13

    Returns: 360360

  14. 14

    Returns: 360360

  15. 15

    Returns: 360360

  16. 16

    Returns: 720720

  17. 17

    Returns: 12252240

  18. 18

    Returns: 12252240

  19. 19

    Returns: 232792560

  20. 20

    Returns: 232792560

  21. 21

    Returns: 232792560

  22. 22

    Returns: 232792560

  23. 23

    Returns: 5354228880

  24. 24

    Returns: 5354228880

  25. 20

    Returns: 232792560

  26. 26

    Returns: 26771144400

  27. 27

    Returns: 80313433200

  28. 28

    Returns: 80313433200

  29. 29

    Returns: 2329089562800

  30. 30

    Returns: 2329089562800

  31. 31

    Returns: 72201776446800

  32. 32

    Returns: 144403552893600

  33. 33

    Returns: 144403552893600

  34. 34

    Returns: 144403552893600

  35. 35

    Returns: 144403552893600

  36. 1

    Returns: 1

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.
This problem was used for: