SEAPERM3 - Editorial

PROBLEM LINK:

Practice
Contest

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 Pi > j and Pj > i
  • for all j between 1 and M we have PXj = Vj

EXPLANATION:

Let’s call a pair (i,j) good if it satisfy Pi > j and Pj > 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 PXj = Vj).

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 Pi ≤ i+2 for all i between 1 and N

proof: Let’s assume Pi = i+3 or bigger then all Pj 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 Pi ≤ 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 < Pi but we have Pi ≤ 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 Fi,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 Fi,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 Fi should be computed using only Fi-1, so let’s think of four cases

  • We want to set Pi = i+2 and Pi-1 = i-1+2: this will lead to have good pair so we should ignore this case.
  • We want to set Pi = i+2 and Pi-1 != i-1+2: so we have this transaction Fi,1 += Fi-1,0
  • We want to set Pi != i+2 and Pi-1 != i-1+2: note that we have exactly two ways to pick a value for Pi so Fi,0 += 2 * Fi-1,0
  • We want to set Pi != i+2 and Pi-1 = i-1+2: we have exactly one way to pick a value for Pi, 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 Pi != 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 Pi. so Fi,0 += Fi-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:

  • Xi-2, Xi-1, Xi, Xi+1 and Xi+2 for all i between 1 and M
  • Vi-2, Vi-1, Vi, Vi+1 and Vi+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 Q1Q2 is the same and also it’s same for range Q2Q3 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 107 on our own machine then paste the answers in the source code, now computing N! for any N will not take more than 107 operations

SETTER’S SOLUTION

Will be uploaded soon.

TESTER’S SOLUTION

Can be found here.

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

I think the explanation has weaknesses:

  1. In the explanation, the opposite of “at least one bad pair” should be “no bad pairs”.

  2. Observation 1 has an implicit assumption that \bf P is a permutation with no bad pairs.

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

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

1 Like

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.

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.

Fixed, thanks.

Nice Question …

1 Like

Learnt a lot…

1 Like

Thanks A lot

1 Like

Thanks a lot

1 Like