MA Mingyu (Derek) | Nov 10, 2017
derek.ma | derek.ma@connect.polyu.hk
For A, there are \((n-1)+(n-2)+...+1 = \frac{n^2-n}{2}\) good pairs.
Let \(X\) be a random variable indicate whether a pair of number is a good pair or not. For \(i \in \{1,2,...,\frac{n^2-n}{2}\}\), define an indicator random variable \(X_i = I\{whether\ this\ pair\ is\ a\ good\ pair\}\). \(X_i=1\) indicate it's a good pair between this pair, otherwise \(X_i = 0\).
Then \(X = \sum_{i=1}^{(n^2-n)/2} X_i\).
\(Pr\{pair\ i\ is\ a\ good\ pair\} = 1/2\) because the revert order of this pair exist in another permutation, and these two cases have same probability to happen in one permutation.
By Lemma 5.1, \(E[X_i] = Pr\{pair\ i\ is\ a\ good\ pair\}\).
According to linearity of expectation: \(E[X] = E[\sum_{i=1}^{(n^2-n)/2} X_i] = \sum_{i=1}^{(n^2-n)/2}E[X_i] = \sum_{i=1}^{(n^2-n)/2}1/2 = \frac{n^2-n}{4}\).
sort(array P){
sorted_by_digits = sort P according to elements' number of digits \
from smallest to largest using counting-sort \
save as a 2D array
# sorted_by_digits is in form: [[elements with 1 digit],[with 2 digits],...]
# loop the 2D array from smallest one
result = []
for each subarray in sorted_by_digits:
sorted = sort subarray using radix-sort from smallest to largest
result.append(sorted)
return result
}
# call sort(P)
The counting-sort for getting sorted_by_digits
takes \(O(k)\).
Then for total time complexity of all radix-sorts in the loop:
\[
Total\ Sorting\ Time = \sum{(\#\ of\ digits\ of\ subarray(10+\#\ of\ elements\ in\ subarray))} \\
= \sum{(10\times\#\ of\ digits\ of\ subarray)} + \\
\sum{(\#\ of\ digits\ of\ subarray\times\#\ of\ elements\ in\ subarray
)} \\
= 10k + k \\
= O(k)
\]
So the total time complexity is \(O(k)\).
Transfer this problem into a Exact String Matching Problem, try to match pattern S
in string R+R
.
findShift(String R, String S){
# call fast algorithm for Exact String Matching Problem
result = fastAlgorithm(T = R + R, P = S) # S is the pattern
if there are some output for matching position in result
return 'YES'
else
return 'NO'
}
# call findShift(R, S)
The time complexity is mainly the time for the fast algorithm which is \(\Theta(2|R|+|S|)\). So the time complexity is \(O(|R|+|S|)\).
If \(P = <(2,0), (5,1), (4,1.1), (2,4)>\), for point \((4,1.1)\), it's a maximal with respect to \(P\), but it's not on the convex hull. The following figure can illustrate the situation clearly:
findMaximal(array of points P){
sorted_by_x = sort P according to points' x value from largest to smallest \
using merge-sort, save as 2D array
# sorted_by_x is in form: [...,[point(s)],[point(s)],[point(s) at largest x]]
maximalList = []
yMaxGlobal = 0
for each array in sorted_by_x:
# get the point with largest y value at this x
yMax = 0
for each element in array:
if (element.y >= yMax):
yMax = element.y
maxYPoint = element
# compare with global max y value
if (maxYPoint.y > yMaxGlobal):
# if the point with largest y at this x is larger than previous max y value
# then this point is maximal
maximalList.append(maxYPoint)
yMaxGlobal = maxYPoint.y
return maximalList
}
# call findMaximal(P)
In this algorihtm, the time complexity of sorting by x value is \(O(nlgn)\). The loop in the loop to get the point with largest y value in that x will scan every individual points in P, so the time complexity is \(O(n)\). All in all, the dominant time complexity is the sorting, thus the total time complexity is \(O(nlgn)\).