Insertion Sort Solutions (InterviewStreet CodeSprint Fall 2011)

Hint.md

The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.

problemsetter.cpp

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std ;
#define MAXN 100002
#define MAX 1000002
int n,a[MAXN],c[MAX] ;
int main()
{
 int runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d",&n) ;
  for(int i = 0;i < n;i++) scanf("%d",&a[i]) ;
  long long ret = 1LL * n * (n - 1) / 2 ;
  memset(c,0,sizeof c) ;
  for(int i = 0;i < n;i++)
  {
   for(int j = a[i];j > 0;j -= j & -j) ret -= c[j] ;
   for(int j = a[i];j < MAX;j += j & -j) c[j]++ ;  
  }
  cout << ret << endl ;
 }
 return 0 ;
}

What "j & -j" means in lines 20 and 21?

@lvsl: search "binary indexed tree"

@lvsl: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

i did not understand 16 and 17 lines,please explain..............

I just don't understand how "int n,a[MAXN],c[MAX]" will make the prog. work. In compilers where integer is 2 byte, this will fail. Please use long instead.

plz anyone tell me more abot the statement

j-=j&-j
Thanks in advance

this will make it easier to understand

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Python version on pythontutor.com, the code visualization might help.

http://goo.gl/uKh8Z

@nma Line 8 should be

for x in range(MAX):

in the code on pythontutor you linked to. Thanks.