PROBLEM LINK:
DIFFICULTY:
HARD
PREREQUISITES:
dynamic programming, matrix expontiation
PROBLEM:
Given two arrays X and V of length M and an integer N, count the number of permutations P of length N which satisfy all the following:
- There exist at least one pair (i,j) such that P_{i} > j and P_{j} > i
- for all j between 1 and M we have P_{Xj} = V_{j}
EXPLANATION:
Let’s call a pair (i,j) good if it satisfy P_{i} > j and P_{j} > i, the problem asks us to count the number of permutations having at least one good pair and also satisfying second condition (i.e. for all j between 1 and M we have P_{Xj} = V_{j}).
instead of counting the number of permutations having at least one good pair we count the number of permutation having no good pairs then we subtract it from total number of permutations satisfying second condition.
Observation 1: All permutations which don’t have good pairs must satify P_{i} ≤ i+2 for all i between 1 and N
proof: Let’s assume P_{i} = i+3 or bigger then all P_{j} such that j < i+3 must have value less than i in order to prevent having a bad pair, but there are i+1 such elements to fill but only i different values available so this is impossible.
Observation 2: if P_{i} ≤ i+2 for some permutation then only consecutive elements can be good pair in that permutation.
proof: Let’s say elements with indices i and j are bad i < j then j < P_{i} but we have P_{i} ≤ i+2 so i < j < i+2 and that means j = i + 1
Special Case: arrays X and V are empty
This is can be solved by dynamic programming, let F_{i,0} means the number of ways to fill first i elements of the permutation and the value of i-th element is NOT i+2, and F_{i,1} means the number of ways to fill first i elements of the permutation and the value of i-th element is equal to i+2
now let’s think of transactions clearly all values of F_{i} should be computed using only F_{i-1}, so let’s think of four cases
- We want to set P_{i} = i+2 and P_{i-1} = i-1+2: this will lead to have good pair so we should ignore this case.
- We want to set P_{i} = i+2 and P_{i-1} != i-1+2: so we have this transaction F_{i,1} += F_{i-1,0}
- We want to set P_{i} != i+2 and P_{i-1} != i-1+2: note that we have exactly two ways to pick a value for P_{i} so F_{i,0} += 2 * F_{i-1,0}
- We want to set P_{i} != i+2 and P_{i-1} = i-1+2: we have exactly one way to pick a value for P_{i}, because there are exactly 3 values between 1 and i+2 not picked yet, one of them is i+2, and second one is i because if it was picked then (i-2,i-1) would be a good pair, and the last one is a value less than i, we don’t want to pick i+2 as we assumed P_{i} != i+2 from the beginning also we can’t pick i otherwise (i-1,i) would be a good pair, so the only option left is the value which is less than i, that’s why we have exactly one way to pick a value for P_{i}. so F_{i,0} += F_{i-1,1}
so this will lead to O(N) solution which can be done in O(log n) using matrix exponentiation
Full solution
in case X and V were empty we could use matrix exponentiation immediately because transformation matrix is fixed for all indices i. however, in case X and V are not empty then transformation matrix is not the same for all positions because coefficients of the transactions discussed above can be different and they depend on arrays X and V, so we need to divide the indices of the array P into ranges such that each range have a the same transformation matrix, in order to do so we create new array Q having those values:
- X_{i}-2, X_{i}-1, X_{i}, X_{i}+1 and X_{i}+2 for all i between 1 and M
- V_{i}-2, V_{i}-1, V_{i}, V_{i}+1 and V_{i}+2 for all i between 1 and M
- N-1 and N
after that we remove duplications from Q then sort it in increasing order, now it’s easy to see that transformation matrix on the range Q_{1}…Q_{2} is the same and also it’s same for range Q_{2}…Q_{3} and so on.
so we can apply matrix expontiation on each range alone and we would have complexity O(K log N) where K is the size of array Q, but K is O(M) so overall complexity is O(M log N) but it has very large constant factor (i.e. 8 from matrix multiplication and 10 from the size of Q)
Computing N factorial
We need to compute N! because as we said before we count the number of not required permutations then subtract them from total number of permutation, so to compute N! we can pre-compute the factorial for each N multiple of 10^{7} on our own machine then paste the answers in the source code, now computing N! for any N will not take more than 10^{7} operations
SETTER’S SOLUTION
Will be uploaded soon.
TESTER’S SOLUTION
Can be found here.