Problem Link: contest, practice
Difficulty: Medium
Pre-requisites: Maths, Inversions, Fenwick Tree
Problem:
We are given two arrays A[] and B[]. At first, we shuffle B[] randomly, then we merge A[] and B[] into array C[] also at random.
Our task is to count the expected number of inversions in C[].
There are N elements in A[] and M elements in B[].
Explanation:
Firstly, as far as the expected value has linear properties, we can represent the answer as AA + BB + AB.
AA is the expected number of inversions between two elements from A[];
BB is the expected number of inversions between two elements from B[];
AB is the expected number of inversions between two elements, such that one of them is from A[] while another is from B[].
Let’s focus on each of this summands and calculate them separately.
Calculation of AA:
As far as the elements from A[] preserve their order in C[], AA is a constant and equals to the number of inversions in A[].
It’s a well-known problem, you can read about that, for example, here: link
Calculation of BB:
As far as the elements from B[] were shuffled before merging them with A[], they can appear in any order in C[]. By using linear properties of the expected value, we can consider each pair of elements from B[] separetely.
I.e. we consider a pair (X, Y) of integers, assuming that X appears in initial, non-shuffled array B[] earlier than Y. If X equals to Y, then there is no way for this pair to become an inversion. Otherwise(X is different with Y) either X < Y or X > Y. The expected number of inversions of this pair is 1/2.
So, in order to find BB, we should count the number of pairs of elements from B[], such that the numbers from each pair don’t equal to each other, and divide it by 2.
Here is a pseudocode, that shows the implementation of the algorithm of calculation BB.
MEM[] is an array, consisting of 100000 zeroes initially
BB = 0
for i from 1 to M do
begin
BB = BB + MEM[ B[i] ]
MEM[ B[i] ] = MEM[ B[i] ] + 1
end
BB = BB / 2
Calculation of AB:
We can use the same logic, as we do for calculating BB: By using linear properties of the expected value, we can consider each pair of elements, such that one of them is from A[] while another is from B[], separetely.
I.e. we consider a pair (X, Y) of integers, assuming that X is a number from A[] while Y is a number from B[].
If X equals to Y, then there is no way for this pair to become an inversion. Otherwise(X is different with Y) either X < Y or X > Y.
In case X < Y the expected number of inversions of this pair equals to i / (N + 1), where i is an index of X in array A[].
In case X > Y the expected number of inversions of this pair equals to (N + 1 - i) / (N + 1), where i is an index of X in array A[].
Why it’s so? The point is that the numbers from A[] preserve their initial order in C[]. Then there are (N + 1) different interesting positions for Y in C[]: before A[1], after A[1] and before A[2], after A[2] and before A[3], …, after A[N]. So, we count only positions that lead pair (X, Y) to an inversion.
How to count AB quickly? We can preprocess numbers from A[], and then for each number from B[] count the expected number of inversions of pairs, where the current B[] is Y.
Here is a pseudocode, that shows the implementation of the algorithm of calculation AB.
MEM1[] is an array, consisting of 100000 zeroes initially
MEM2[] is an array, consisting of 100000 zeroes initially
AB = 0
for i from 1 to N do
begin
MEM1[ A[i] ] = MEM1[ A[i] ] + i
MEM2[ A[i] ] = MEM2[ A[i] ] + (N + 1 - i)
end
for i from 2 to 100000 do
begin
MEM1[ i ] = MEM1[ i - 1 ] + MEM1[ i ]
end
for i from 99999 to 1 do
begin
MEM2[ i ] = MEM2[ i + 1 ] + MEM2[ i ]
end
for i from 1 to M do
begin
AB = AB + MEM1[ B[i] - 1 ] + MEM2[ B[i] + 1 ]
end
AB = AB / (N + 1)
Some words about the pseudocode.
Here MEM1[i] denotes the sum of indexes of elements from A[], which are not greater than i.
Also MEM2[I] denotes the sum of ( N + 1 - index ) of elements from A[], which are not less than i.
Please, look carefully through this section one more time if you don’t understand it.
Setter’s Solution: link
Tester’s Solution: link