Question: https://codility.com/demo/take-sample-test/array_inversion_count
Question Name: ArrayInversionCount
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | def mergesort( aList, first, last ): ''' Modified merge sort algorithm. Record the inversion count during sort. ''' mid = ( first + last ) / 2 if first < last: # Recursive calling left_inver = mergesort( aList, first, mid ) right_inver = mergesort( aList, mid + 1, last ) else: # Terminate condition return 0 first_index = first # The index for the left part second_index = mid + 1 # The index for the right part temp = [0] * (last-first+1) # To hold the sorted content temp_index = 0 merge_inver = 0 # Number of inversion in merging while first_index <= mid and second_index <= last: if aList[first_index] <= aList[second_index]: # Less index indicates less value. No inversion. temp[temp_index] = aList[first_index] first_index += 1 else: # Greater index has less value. Inversion exists. # For exampe: # [ 4, 5, 2, 3 ] # | Left part | |Right Part| # and first_index = 1, second_index = 3, mid = 2 # We need the item "2" to be the position 0. So it # has to pass all the unwritten items in left part. # Here these unwritten items are "4" and "5". So # two more inversions are involved. # In general, the left part is sorted. So all the # elements, being and after first_index, are greater # than element in position second_index. AND all of # them have less indexes. As the result, # there are mid-first_index+1 new reversions. temp[temp_index] = aList[second_index] second_index += 1 merge_inver += mid - first_index + 1 temp_index += 1 if first_index != mid+1: # Some element in the left part left. They have less # indexes, but greater values. Inversion involves. # BUT these inversions have already been counted. while first_index <= mid: temp[temp_index] = aList[first_index] first_index += 1 temp_index += 1 if second_index != last+1: # Some element in the right part left. They have both # greater indexes and values than all in the left part. # No inversion is involved. while second_index <= last: temp[temp_index] = aList[second_index] second_index += 1 temp_index += 1 # Rewrite the sorted content into the original array aList[first:last+1] = temp[:] return merge_inver + left_inver + right_inver def solution(A): return mergesort( A * 1, 0, len(A)-1) |
UPDATE on July 18, 2014: Thanks to @Andrew, there is another solution with Binary Indexed Tree.
UPDATE on October 8, 2014: Thanks to @Piotrek Martynowicz, there was a bug for the statement: “computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.”
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | def mergesort( aList, first, last ): ''' Modified merge sort algorithm. Record the inversion count during sort. ''' mid = ( first + last ) // 2 if first < last: # Recursive calling left_inver = mergesort( aList, first, mid ) if left_inver == -1: return -1 right_inver = mergesort( aList, mid + 1, last ) if left_inver == -1: return -1 else: # Terminate condition return 0 first_index = first # The index for the left part second_index = mid + 1 # The index for the right part temp = [0] * (last-first+1) # To hold the sorted content temp_index = 0 merge_inver = 0 # Number of inversion in merging while first_index <= mid and second_index <= last: if aList[first_index] <= aList[second_index]: # Less index indicates less value. No inversion. temp[temp_index] = aList[first_index] first_index += 1 else: # Greater index has less value. Inversion exists. # For exampe: # [ 4, 5, 2, 3 ] # | Left part | |Right Part| # and first_index = 1, second_index = 3, mid = 2 # We need the item "2" to be the position 0. So it # has to pass all the unwritten items in left part. # Here these unwritten items are "4" and "5". So # two more inversions are involved. # In general, the left part is sorted. So all the # elements, being and after first_index, are greater # than element in position second_index. AND all of # them have less indexes. As the result, # there are mid-first_index+1 new reversions. temp[temp_index] = aList[second_index] second_index += 1 merge_inver += mid - first_index + 1 if merge_inver > 1000000000: return -1 temp_index += 1 if first_index != mid+1: # Some element in the left part left. They have less # indexes, but greater values. Inversion involves. # BUT these inversions have already been counted. while first_index <= mid: temp[temp_index] = aList[first_index] first_index += 1 temp_index += 1 if second_index != last+1: # Some element in the right part left. They have both # greater indexes and values than all in the left part. # No inversion is involved. while second_index <= last: temp[temp_index] = aList[second_index] second_index += 1 temp_index += 1 # Rewrite the sorted content into the original array aList[first:last+1] = temp[:] if merge_inver + left_inver + right_inver > 1000000000: return -1 else: return merge_inver + left_inver + right_inver def solution(A): return mergesort( A * 1, 0, len(A)-1) |
Hello! Check out simpler solution using bisect module:
https://gist.github.com/tymofij/9027062
First of all, thanks for your comment! For this question, we could use ANY sorting algorithm, and count the swap times. But limited to the time complexity requirement, only Mergesort and Heapsort are qualified (http://bigocheatsheet.com/). Your method is Binary Insertion Sort, http://www.geneffects.com/briarskin/theory/binary/index.html, and http://www.brpreiss.com/books/opus5/html/page487.html. Even though it passed all the test, the time complexity should be O(n**2).
This problem can also be solved in O(n * log n) time and O(n) space by using a Binary Indexed Tree (aka Fenwick Tree).
The basic idea is to use the BIT to keep track, during a right to left scan of the input, of the cumulative frequency of elements previously seen that are strictly less than the current element.
My implementation of this idea is here:
https://codility.com/demo/results/demoSD6QAC-XDX/
And a great write up of how to use a BIT to solve the inversion counting problem is here:
http://pavelsimo.blogspot.co.uk/2012/09/counting-inversions-in-array-using-BIT.html
Wonderful morning! Learn something new! THAAAAAANKS!!!
My solution using binary search and sorted array.
[code was removed by admin, because of missing tag/content]
This is horrible. Did you at least check if it compiles?
Part of the code should be missing, without the pre tags. I’ve removed the incomplete code.
Hi Sheng,
I tried running your Solution (not the Wrong Solution) and it is exceeding recursion limit. Could you please check if this is not the case?
When I finished the problem, the site was using Python 2.X. While nowadays, they switched to Python3. As a result, the divide op “/” is changed, at line #5. I have updated the solution for Python 3. Thanks for pointing it out 🙂
My bad, I didn’t think about the version issue. Anyway, thanks a lot for updating the solution. I was looking at the BIT solution and honestly, I don’t get it.
Here is my 100/100 solution in C#.
Algorithm is quite easy : create a sorted copy of the list, then for each value of the first list, binary search its index in the sorted one. That index corresponds to the number of inversions.
Then remove the value you just searched from the sorted list, and repeat.
This is my C++ solution:
https://app.codility.com/demo/results/trainingYJX2GY-6RU/