Given an array,

• Find out the number of inversions.
• Find out the number of inversions across all $$$n!$$$ permutation of the elements.
• Find out the expected value of the number of inversion if I permute elements randomly.

Then, define 2 arrays $$$A$$$ and $$$B$$$. This time, $$$A$$$ is fixed, and you have to permute $$$B$$$. After permuting and fixing $$$B$$$, define $$$C[i] = A[i] \cdot B[i]$$$

• Count the number of inversions in array $$$C$$$ across all permutations of $$$B$$$.
• If I permute $$$B$$$ randomly, what is the expected number of inversions that I'll find in the array $$$C$$$?

I created a video discussing how to solve these problems, starting from bruteforce and then optimizing it to $$$O(N^4)$$$ to $$$O(N^3 \cdot Log(N))$$$ to finally $$$O(N^2 \cdot Log(N))$$$.

This problem appeared at the fourth position in today's Div2 Round.