This blog is inspired by problem 1591D - Yet Another Sorting Problem, hope you will enjoy it.
Basic concepts
First of all, let's define some basic things, you can skip it if you know it.
Parity of permutation $$$p$$$ is parity of number of inversions in it. Inversion is pair $$$(i, j)$$$ such that $$$i < j, p_i > p_j$$$.
Composition of permutations defined as follows $$$(f \circ g)_x = f_{g_x}$$$, we first apply $$$g$$$, then $$$f$$$.
Cycle is a permutation, where some indices are cyclic shifted, for example $$$p = \begin{pmatrix}1 & 5 & 2 & 4 & 3\end{pmatrix}$$$ is a cycle $$$\begin{pmatrix}2 & 3 & 5\end{pmatrix}$$$.
Theorem. Every permutation is composition of non-intersecting cycles.
Proof. Consider directed graph where vertices are numbers from $$$1$$$ to $$$n$$$, and edges are $$$i \to p_i$$$ for all $$$i$$$. Since $$$p$$$ is permutation, indegree and outdegree of each vertex is 1, hence our graph is collection of cycles, that's what we want.
Lemma. Applying swap to permutation will change its parity.
This lemma is very important, so it is left to reader as an exercise.
Fact. Parity of $$$(f \circ g)$$$ is sum of parities of $$$f$$$ and $$$g$$$.
Proof. Applying swap to permutation change its parity, thus if permutation $$$f$$$ can be represented as $$$k$$$ swaps, then parity of $$$k$$$ is parity of $$$f$$$. So if $$$f$$$ can be represented as $$$k$$$ swaps, and $$$g$$$ can be represented as $$$m$$$ swaps, then $$$f \circ g$$$ can be represented as $$$k + m$$$ swaps, but parity of $$$f \circ g$$$ is parity of $$$k + m$$$, which is sum of parities of $$$f$$$ and $$$g$$$, QED.
Counting inversions, parity of permutation
There are many ways to count number of inversions in $$$O(n \log n)$$$ time.
But there is a simple way to count parity of permutation, without directly counting number of inversions.
Theorem. Permutation can be represented as composition of 3-cycles if and only if it is even.
Proof. 3-cycle is even, so composition of 3-cycles must be even, so all that we need to do is proof, that for any even permutation exists such representation.
We will try to build our permutation from identical applying 3-cycles. On $$$i$$$-th iteration we assume, that first $$$i - 1$$$ elements of permutation are in place, and we will try to place $$$i$$$-th element. If $$$i$$$-th element is not in place, then now in current permutation it is on $$$j$$$-th place, $$$j > i$$$. Let's do cycle $$$n \to j \to i$$$, if $$$j \neq n$$$, and if $$$j = n$$$, do $$$n - 1 \to j \to i$$$, so we won't corrupt first $$$i - 1$$$ elements, and we will place $$$i$$$-th element.
So we can do $$$n - 2$$$ steps. After that there are two possible situations.
$$$n - 1$$$-th and $$$n$$$-th elements are in place, this means that we represented our permutation as 3-cycles, so our permutation is even and we've found representation for it.
They are not in place, they are swapped. Because on each step of algorithm permutation is even, and it differs from our permutation by one swap, thus our permutation is odd, so it can't be represented.
So we've proven this theorem and got $$$O(n)$$$ algorithm with good constant, which can be useful in other problems involving parity of permutation.
Excuse me, in the contest, I checked if there are even number of (even vertices cycles) then the answer would be "YES" which is the same as the parity of the permutation is even. But how to prove that they are actually the same?
Thanks.
Let's prove that the parity of $$$p \in S_n$$$ is the same as the parity of $$$n + cycles(p)$$$.
Let's do induction over all $$$p \in S_n$$$ on the number of inversions. If $$$p$$$ has $$$0$$$ inversions (base case), the condition trivially holds. If not, choose an arbitrary inversion $$$(i, i+1)$$$ and swap those elements (this effectively decreases the number of inversions by $$$1$$$). The number of cycles will either increase or decrease (so their parity changes) and so does the parity. Therefore induction holds.
As was mentioned above parity of $$$f \circ g$$$ is sum of parities of $$$f$$$ and $$$g$$$.
Note, that even length cycle is odd as permutation, and odd length cycle is even, because we can represent cycle length $$$L$$$ with $$$L - 1$$$ swaps. So if $$$f = C_1 \circ C_2 \circ \ldots \circ C_k$$$, and $$$m$$$ of them have even length, then $$$m$$$ of them are odd as permutations, so parity of $$$f$$$ is parity of $$$m$$$, that's exactly what you need.
And from this we can get, that parity of $$$f$$$ is $$$n + cycles(f)$$$. Indeed, if length of $$$C_i$$$ is $$$L_i$$$, then parity of $$$C_i$$$ is $$$L_i - 1$$$. Parity of $$$f$$$ is sum of parities over $$$C_i$$$, that is $$$(L_1 - 1) + (L_2 - 1) + \ldots + (L_k - 1)$$$, but sum of $$$L_i$$$ is $$$n$$$, so parity of $$$f$$$ is parity of $$$n - cycles(f)$$$, which is same as parity of $$$n + cycles(f)$$$
Are there any other problems similar to the one discussed above?
911D - Подсчет инверсий
987E - Petr and Permutations
https://codeforces.me/contest/1430/problem/E
hey man very intersting blog...are there any other resources where i can further read about thus stuff??
I am not able to prove the lemma..any hints ??? thematdev
Consider a permutation ________a_____b___________. Here we have to swap a and b. For now consider a > b (Similarly you can also prove for a<b).
Part1 = numbers appearing before a
Part2 = numbers appearing after a and before b
Part3 = numbers appearing after b
x2 = number of numbers less than b in part 2
y2 = number of numbers greater than b and less than a in part 2
z2 = number of numbers greater than a in part 2
x3 = number of numbers less than b in part 3
y3 = number of numbers greater than b and less than a in part 3
z3 = number of numbers greater than a in part 3
inversion count of a number 'k' is number of numbers < k coming after k
Now observe carefully, if we swap a and b, the change in number of inversions of whole permutation will be only due to change in numbers of inversions of sub-array a_______b.
By definition Inversion is pair (i,j) such that i<j, pi>pj. So before swaps number of inversion count of 'a' will be
n1 = x2 + y2 + x3 + y3 + 1
and inversion count of 'b' will bem1 = x3
After swap the values mentioned above will be
n2 = x3 + y3
andm2 = x2 + x3
respectively.After swap inversion count of all numbers > a, present in part2
(z2)
will increase by 1, coz 'a' which is less than them now will come after them. Similarly inversion count of all numbers > b, present in part2(z2+y2)
will decrease by 1, coz 'b' which is less than them now will come before them.so total change inversion count of whole permutation will be
n2+m2 - (n1+m1) + z2 - (z2+y2) = -2y2 - 1
, which is an odd number. So as change in inversion count is an odd number, after swapping two different numbers parity will definitely changeThank you very much man..i understood it. You are awesome
Swap of two adjacent elements will change parity, because it either increases of decreases number of inversions by 1.
Try to represent swap as odd number of adjacent swaps.
in the blog you have not made a relation between number of inversions and the cyclic representation of permutation..there must be some relation..You have proved the fact that permutation can be represented as composition of non-intersecting cycles..but how does it relate to the parity
Check comments above, I and bicsi have proved, that parity of permutation $$$p$$$ length $$$n$$$ is $$$n + cycles(p)$$$ and also parity of number of even cycles.
One thing to keep in mind is that, even though this algorithm is $$$O(n)$$$, it can be painfully slow for large values of $$$n$$$, for example, for $$$n=10^7$$$ it will usually take around $$$0.5$$$ seconds. I'm not aware of anything faster though maybe a Fenwick tree operating on single bits with XOR would be faster.
very good blog,,but some examples would have helped
Hello, I am having a bit of trouble seeing why a slightly easier approach was omitted (/ is wrong?)
With the above general idea in mind, can't we just represent our permutation as a number of transpositions and count the parity of this number?
example code:
my (AC) submission to 1591D using this idea.
*granted, the complexities (/ constants) of my solution and the one presented in the blog are virtually the same, but this seems more intuitive and I don't know why it wasn't presented.
Thank you! <3