SEAPERM3 - Editorial

kingofnumbers · November 9, 2016, 2:50am

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_{X_j} = 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_{X_j} = 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₁…Q₂ is the same and also it’s same for range Q₂…Q₃ 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⁷ on our own machine then paste the answers in the source code, now computing N! for any N will not take more than 10⁷ operations

SETTER’S SOLUTION

Will be uploaded soon.

TESTER’S SOLUTION

Can be found here.

john_smith_3 · November 18, 2016, 4:35am

It is tricky question. I also find the editorial too tough to follow.

I think the explanation has weaknesses:

In the explanation, the opposite of “at least one bad pair” should be “no bad pairs”.
Observation 1 has an implicit assumption that \bf P is a permutation with no bad pairs.
Observation 2 has a slightly different implicit assumption, this time that \bf P is a permutation with {\bf P}_i \le i+2 for all i.
In the analysis of the special case where there are no constraints, in the fourth sub-case, can we reach the conclusion that {\bf F}_{i,0} \ += {\bf F}_{i-1,1} by looking at the observations, or is some more subtle calculation needed? (I agree with the conclusion, but I can’t see why)

But I’m completely confused by the analysis of the full solution. I can’t grasp the motivation of the new array \bf Q, or how it should be populated. Can anyone explain?

I did answer the question during the competition after much experimentation. I was hoping for a neat explanation.

Overall I found the November questions to be a very good set, well phrased, and of just the right standard for me. Sorry if this reply sounds critical.

kingofnumbers · November 18, 2016, 10:44pm

Thanks for your feedback, and sorry for late reply I was travelling today.

I have made changes in the editorial so that to fix all points you mentioned, please read the editorial from beginning again and don’t hesitate to point out any more mistakes/weakness exist in the editorial.

john_smith_3 · November 19, 2016, 5:24am

I fear your argument for the fourth sub-case of the special case is now wrong. If P_{i-1}=i-1+2 and P_i=i, then (i-1,i) forms a bad pair.

I think the right argument goes like this:

From observation 1 there are i+2 potential values for P_i. Of these, P_1, P_2, ..., P_{i-1} have consumed i-1 of them, leaving three to consider.

One of the three is i+2. But we rule that out because we seek P_i \ne i+2.

One of the three is i (because P_{i-2} \ne i, because otherwise (i-2,i-1) would form a bad pair, and none of the other P_j=i because of observation 1.) But we rule out P_i=i, because otherwise (i-1,i) would form a bad pair.

The final one of the three is some value less than i. Observation 2 tells us to check whether or not (i-1,i) is a bad pair. It is not bad, because we would have P_i < i so certainly not true that P_i > i-1, so (i-1,i) is not a bad pair.

So the conclusion is that if P_{i-1} = i-1+2, then there is just one available valid value for P_i.

kingofnumbers · November 19, 2016, 4:10pm

Fixed, thanks.

lud1161 · November 19, 2016, 8:43pm

Nice Question …

thunder_blade · November 19, 2016, 8:59pm

Learnt a lot…

tester1161 · November 19, 2016, 10:48pm

Thanks A lot

tester1161 · November 19, 2016, 10:50pm

Thanks a lot