PERSHFTS - Editorial

[xcwgf666]

Problem Link

Practice

Contest

Difficulty

Medium

Pre-requisites

Finding the rank of permutation, modular inverse

Problem

Find the rank of the permutation Q in the set, containing all the strings that are obtained from the permutation P by cyclic shifts of the subsegments of P the length of K. If Q doesn’t belong S, output -1 instead.

How to get 10 points

Let’s solve subtask #2, where k = n.

Let’s find such x, that P₁ = Q_x. In other words, we need to find such x, that index 1 in the permutation P corresponds to the index x in the permutation Q. Note that if the index y in the permutation P corresponds to the index z in the permutation Q, then z mod n = (x+y+n-1) mod n holds. Using this fact, we can check whether Q can be obtained from P or not by iterating through all the indices from 1 to n and comparing the corresponding elements of the permutations.

If we figured out that P can be obtained from Q, then the answer is equal to Q₁, because S will contain exactly n permutations, and all the first elements of these permutations will be distinct.

Making further insights

From now on, we will consider that k < n. Let’s consider two cases: when k is even and when k is odd

The first case: k < n, k is even

Let’s prove that we can obtain any permutation from the permutation P. It is easy to move the last n-k numbers to their places.

Now we need to figure out, how to swap the first two numbers of permutation P. If we can do this, we can swap any two consecutive numbers among the first k numbers and use the algorithm, similar to the bubble sort to place all these numbers to their places.

Let L denote cyclic shift of segment (P₁,P₂,…,P_k) and R denote the cyclic shift of the subsegment (P₂,P₃,…,P_(k+1)). Applying there shifts consecutively - first L, and then then R moves elements P_k and P_(k+1) to the first two places, saving their relative order and the relative order of the first k-1 elements. Using this combination several times, we get the permutation (P₂,P₃,…,P_(k+1), P₁,…). Finally, making the shift R we get the permutation (P₂,P₁,P₃,P₄,…).

Now we have swapped first two elements of the permutation.

Thus, we’ve showed that if k < n, k is even, any permutation can be obtained from P.

The second case: k < n, k is odd

Note that we can perform a cyclic shift of any k consecutive elements using k-1 swaps of the consecutive elements. Since k is odd, k-1 is even. It means that the parity of the permutation won’t change during operations. So, if parities of permutations P and Q aren’t equal, the answer is -1. Now let’s show that any other permutation belong to S, or, in other words, that S consists of all the permutations of the parity the same to the parity of P.

Now we can’t swap the first two elements like in the previous case, because it changes parity of the permutation. Instead of that we can cyclically shift the first three elements of the permutation. We do this in similar manner: using several LR-combinations to obtain the permutation (P₃,P₄,…,P_(k+1),P₁,P₂,…) and make the RR-combination to get permutation (P₃,P₁,P₂,P₄,…).

Using this construction, we are able to place the first k-2 numbers to their places. The order of the remaining 2 numbers is determined by the parity of the initial permutation.

So, if the parities of the permutations P and Q are equal, these elements will go in the right order, so we can obtain the permutation Q from the permutation P.

Reformulating the problem

Now we need to solve the following problem:

• If k is even, find the rank of the permutation Q.
• If k is odd, find the rank of the permutation Q among all the permutations having the same parity with P.

Note that the permutations with the lexicographic indices 2i and 2i+1 (0-based) have distinct parities - we can prove this using induction by length of permutation. So, if lexicographic the index of the permutation Q is x, the 0-based answer will be equal to ⌊x/2⌋, and 1-based answer will be bigger by one.

Solving the reformulated problem

First of all, if k is odd, we need to check, whether the parities of Q and P coincide or not. The parity of the permutation is basically the parity of the number of the inversions in this permutation. Here is the detailed tutorial on finding the number of inversions in the permutation.

After the check is done, all that is left is to find the rank of the permutation Q (and then, if k is odd, to divide it by two using modular inverse).

Finding the rank of the permutation

The 0-based rank of the permutation will be equal to the number of the permutations that are lexicographically smaller than this permutation. In order to calculate it, let’s calculate the sum of the total number of permutations that have the first element smaller than the first element in the sought permutation, the total number of permutations that have the first element equal to the sought permutation but the second element smaller than the second element in the sought permutation, the total number of the permutations that have the first two elements equal to the first two elements of the sought permutation and the third element smaller than the third element in the sought permutation, and so on.

The number of the permutations where the first element is smaller than the first element of the sought permutation is (Q₁-1)*((n-1)!) because the first element should be less than
Q₁ and the rest can be chosen arbitrarily, so there are (n-1)! ways to do that.

Similarly, the number of permutations where the first element is equal to the first element of the sought permutation, but the second one is less than the second element of the sought permutation is Q₂ - (1, if (Q₁<Q₂) and 0, otherwise)*((n-2)!) because after processing the first element, we can throw it away and consider a permutation of (n-1) integers.

All in all, we can write the pseudocode for calculating the rank of the permutation Q:

    answer = 0
    factorial[0] = 1
    for i = 1 to n do : factorial[i] = factorial[i - 1] * i mod (10<sup>9</sup>+7)
    for i = 1 to n do : isOccured[i] = 0
    for i = 1 to n do :
        elementsSmaller = 0
        for j = 1 to Q[i]-1 : elementsSmaller = elementsSmaller + isOccured[j]
        answer = (answer + elementsSmaller * factorial[n - i]) mod (10<sup>9</sup>+7)
        isOccured[Q[i]] = 1

The code above runs in O(n²), so if you use it without any changes, it will bring you at most 60 points. But now, we can notice that since all we do is the single element modification and finding the sum on the subsegment, it can be replaced with a fenwick tree or a segment tree, thus, reducing the complexity to O(n log n) and giving us the 100-point solution.

Setter’s Solution

Can be found here

Tester’s Solution

Can be found here

[c1_6]

How do you find a/2 modulo m? I was checking this and it seems to be impossible

[pkacprzak]

I did it in the following way:

When I compute (A + B) M or (A + B) M, I store the parity of the result. Notice that you can compute the parity of A + B or A * B, if you know the parity of A and B.

If you want to compute (A / 2) % M, there are two cases to consider:

Let inv(2, M) be the modular inverse of 2 mod M.

1. A is even, then (A / 2) M = (A * inv(2, M)) M
2. A is odd, then (A / 2) M = ((A - 1) * inv(2, M)) M

This is the case when you want to compute floor(A / 2) M. You can compute ceil(A / 2) M in the same way, just replace A - 1 with A + 1 in the second case.

[grebnesieh]

For the issues in diving by 2 while under modulo, a pretty simple solution is to observe that all the permutation having an odd rank have their second last element smaller than their last element. Just use

if(B[n - 2] < B[n - 1]) r += 1;

before you use modinverse with 2 and you should be fine.

This can be shown as being true since calculation of rank involved a sum over multiplication of (n - i - 1)! with the elements smaller than B[i] for indexes > i. Whenever it is 2! or bigger it will render 0 mod 2. Therefore, only depending on 1!, that is the second last element and 0! that is the last element, can an odd rank be generated. for 0! smaller elements are always 0, so we are left with 1! which is the case the code snippet I posted above handles.

Full code: https://www.codechef.com/viewsolution/8340947

[adityank007]

I did the same way as explained in the editorial. I have used nlog(n) for counting inversions(Merge Sort) and nlog(n) for finding the rank using segment tree. But one of the last subtask showed tle.
https://www.codechef.com/viewsolution/8528467
Someone please tell me where is my mistake…

[greendragons]

You can also compute it as a%(2m)/m…

[noble_mushtak]

Setter’s Solution gives Access Denied error.

[kay_kay]

The below code is from Setter’s solution.
After the line, int id = index(q,MOD); , why can’t we just print (id/2)+1 as MOD has already been applied to id?

        if (parity(p) == parity(q))
		{
			//Answer exists
			int id = index(q, MOD);
			//If index is odd, we need to substract 1 from it
			if (index(q, 2) == 1)
				id = (id + MOD - 1) % MOD;
			//500,000,004 is inverse element of 2 by modulo MOD
			id = id*500000004ll % MOD;
			cout << (id + 1) % MOD << endl;
		}

[eartemov]

In case of modular arithmetic we can’t just divide one number by another, because in most cases \frac{A*MOD + B}{C*MOD + D} \ne \frac{B}{D}. For example, if 0-based rank of Q is equal to 2,000,000,000, then required answer is 1,000,000,001. But in this case id = 2,000,000,000 % 1,000,000,007 = 999,999,993 and (id/2) + 1 = 499,999,997. We must use modular multiplicative inverse for dividing in modular arithmetic. If b^{-1} is modular multiplicative inverse of b by modulo M, then \frac{a}{b}=a \cdot b^{-1} (mod~M) (of course, if b divides a).

[kay_kay]

Thanks @eartemov!!I Guess,I have to learn more about Modular Arithmetic.

[omerjerk]

In case of K = N, the editorial says “If we figured out that P can be obtained from Q, then the answer is equal to Q1, because S will contain exactly n permutations, and all the first elements of these permutations will be distinct”.

I’m unable to get why the rank of the permutation will be equal to Q1.

What if P was 4 5 8 6 and Q was 6 4 5 8 ?
Q1 in this case would be 6. Although the possible permutations are only 4.

Also, why would the first element of all the permutations from set S be different ?

[pkacprzak]

P and Q are permutation of numbers from 1 to N only

[siddhant034]

There is an error in the pseudocode given on this page for calculating the rank of the permutation Q.
The following is the correct pseudocode.

answer = 0
    factorial[0] = 1
    for i = 1 to n do : factorial[i] = factorial[i - 1] * i mod (10^9+7)
    for i = 1 to n do : isOccured[i] = 1
    for i = 1 to n do :
        elementsSmaller = 0
        for j = 1 to Q[i]-1 : elementsSmaller = elementsSmaller + isOccured[j]
        answer = (answer + elementsSmaller * factorial[n - i]) mod (10^9+7)
        isOccured[Q[i]] = 0

[omerjerk]

oooops.

[cvarad]

The index of the permutation can be found in O(nlogn) even without a special data structure (Fenwick tree/Segment Tree).

Finding the index of the permutation reduces to finding the Lehmer Code of a permutation.

Now, Lehmer Code is nothing but finding the number of inversions from each element in the array.
Example: 1, 5, 0, 6, 3, 4, 2 has the Lehmer Code 1, 4, 0, 3, 1, 1, 0.

This can be done by modifying merge sort such that it gives you the number of inversions from each element in the array!

[tao_of_coding]

Getting AC on tasks 0, 1 , and 2, but WA on subtask 3. Anyone know what is different between task 2 and 3? They are both Sub-Task 3…

https://www.codechef.com/viewsolution/8563442