PROBLEM LINK:
DIFFICULTY:
Medium
PREREQUISITES:
Probability, Expectation, Binary Index Tree/Segment Tree
PROBLEM:
You’re given an array of integers B. An array is created out of this array as following : A[i] is equal to B[i] + d with probability P[i], and it is equal to B[i] with probability 1-P[i]. Your task is to find out expected number of swaps bubble sort will make on array A.
QUICK EXPLANATION:
Number of swaps made by bubble sort on sequence is number of inversions - so we’re to find the expected number of inversions. By linearity of expectation, we have to find out sum of probabilities of (i,j) forming an inversion for all i, j. This can be done using a data-structure like Binary Index Tree/Segment tree in O(N logN) time.
DETAILED EXPLANATION:
Let’s try to understand how many swaps would Bubble sort make on a general
sequence. In ith pass, ith largest element of the sequence goes in the ith last position and order of all other elements doesn’t change. Let’s focus on the largest element for now. Once the largest element reaches end of the array, it is not
involved in any other swaps later. If this element was at ith position initially
in how many swaps was it involved? It is easy to see that this number is N-i-1.
By same logic for other elements, for each element, number of swaps it is involved in is equal to the number of places it is left to its position in the sorted array. This is nothing but
number of inversions this element creates and so total number of swaps is equal
to total number of inversions in array.
More formally number of inversions is the number of pairs (i,j) where A[i] > A[j]
and i < j. So essentially we’ve to calculate the expected number of pairs (i,j)
with i < j and A[i] > A[j] in the array A. Now let’s see how to calculate expectation E :
Let’s define an indicator variable X(i,j) = 1 if i and j create an inversion
else 0.
So it is clear from definition that E = Expectation of ( Sum over all i and j where i < j { X(i, j) } )
Using linearity of expectation : E = Sum over all pairs i and j where i < j { Expectation of ( X(i, j) }
Now what is Expectation of X(i, j) (denoted as E(i,j) from now on) ?
E(i, j) = Prob (X(i, j) = 1) * 1 + Prob( X(i, j) = 0) * 0 which is equal to Prob (X(i, j) = 1) . i.e the probability that ith element and jth element form an inversion.
Approach 1:
Move over i from 1 to N, move j from i+1 to N. There are two possibilities for A[i] : either B[i] or B[i] + d. Similarly there are two possibilities for jth element and so total there are 4 possibilities for the (A[i], A[j]) pair. For each possibility we know the probability of its occurence (product of individual probabilities) and we also know if A[i] > A[j] or not. So we can find E(i,j) in constant time. This approach is O(N2) and is probably slow for the given constraints.
Approach 2:
We need to speed up our algorithm to O(N log N) or faster. There is indeed a way out - by using segment tree or binary indexed tree. Let’s try to understand the high level idea. Say you’ve processed first i elements of array and in the process have also constructed all possible numbers that could belong to A[1…i] each with probability of its occurrence as well. Now we see x = B[i+1]. With probability P[i+1], A[i+1] would be x + d. So we find out sum of probabilities of occurrence of all those elements which are greater than x + d and are generated in first i elements of A. We multiply the probability by P[i+1] and add that to the answer. Similarly with probability (1-P[i]), A[i+1] would be B[i+1]. We can again find out sum of probabilites of numbers generated by first i elements greater than B[i], multiply it by (1-P[i]) and add it to answer.
Pseudo code of the algorithm:
ans = 0
S = {} // S is map of integers to probabilities
for i = 1 to N
ans += P[i] * ( query(S, B[i] + d) ) // query(S, x) gives : sum over y > x { S[y] }
ans += (1- P[i]) * query( S, B[i])
S[B[i] + d] += P[i]
S[B[i]] += 1 - P[i]
A binary index tree or segment tree could be used after cordinate compression for this algorithm.
Refer to setter/tester code for a better understanding.
Note : Beware of precision issues. One could completely avoid usage of floating point numbers by interpreting probabilities as integers and later dividing by 10000.
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.
