Connection Status:
Competition Arena > WildPermutations

WildPermutations

TCO 22 Semi 2 · 2022-11-17 · by misof

TCO 22 Semi 2 · 2022-11-17 · by misof · Advanced Math
Class Name: WildPermutations
Return Type: int[]
Method Name: count
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

In this problem a permutation of order N is an array P[0..N-1] such that the elements of this array are mutually distinct values from 0 to N-1.

There are exactly N! permutations of order N.


Given a constraint K, a permutation of order N is called wild if for at least one index x the difference between x and P[x] is strictly bigger than N-K.

For example, for K=3:

  • The permutation P = {3, 0, 1, 2} is wild because abs( 0 - P[0] ) = 3 > N-3.
  • The permutation P = {0, 5, 2, 3, 4, 1} is wild because abs( 1 - P[1] ) = 4 > N-3, and also because abs( 5 - P[5] ) has the same value.
  • The permutation P = {1, 0, 3, 2, 5, 4} is not wild because for each x we have abs( x - P[x] ) = 1, which isn't large enough.

You are given K and the int[] queries. For each value N in queries count all wild permutations of order N, modulo 10^9 + 7. Return a int[] with the answers to all queries, in the order in which they were given.

Constraints

  • K will be between 1 and 2,500, inclusive.
  • queries will have between 1 and 50 elements, inclusive.
  • Each element of queries will be between 2*K and 10^9, inclusive.
Examples
0)
2
{4}
Returns: {10 }

We have K=2 and N=4. Hence, we are looking for permutations of order 4 in which at least one element x has the property abs( x - P[x] ) > N-2 = 2. There are ten such permutations. Their full list follows. (1, 2, 3, 0) (1, 3, 2, 0) (2, 1, 3, 0) (2, 3, 1, 0) (3, 0, 1, 2) (3, 0, 2, 1) (3, 1, 0, 2) (3, 1, 2, 0) (3, 2, 0, 1) (3, 2, 1, 0)

1)
2
{4, 4, 4, 5}
Returns: {10, 10, 10, 42 }

An example with multiple queries. We already know that each of the first three has the answer 10. The last one has 42 permutations.

2)
3
{10}
Returns: {1763280 }

About half of all 10! permutations of order 10 are wild for K = 3.

3)
1
{8, 7, 6, 5, 4, 3, 2}
Returns: {0, 0, 0, 0, 0, 0, 0 }

For K=1 the requirement for a wild permutation becomes "some x differs from P[x] by more than N-1". This is clearly impossible, as the difference between any index and any value is at most N-1. Thus, there are no wild permutations.

4)
2500
{999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999 }
Returns: {139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926, 139139926 }

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

Coding Area

Language: C++17 · define a public class WildPermutations with a public method vector<int> count(int K, vector<int> queries) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous