SPOJ INVCNT Solution

| July 01, 2015

The correct, optimal and working solution for programming question INVCNT on spoj

#include <stdio.h>
#include <stdlib.h>

#define swap(array,i,j) int t; t=array[i];array[i]=array[j];array[j]=t;

void print_array ( long long int * array , long long int start , long long int end ) {

	long long int i = 0;
	printf("Array to count_inv : ");
	for ( i = start ; i <= end ; i++ ) {
		printf("%lld " , array[i]);
	}
	printf("\n");

}

long long int merge ( long long int * array , long long int l , long long int m , long long int h ) {

	//print_array ( array , l , h );
	//printf("h-l+3 = %d\n" , h-l+1);
	//int * b_array = (int *) malloc ( (h-l+1) * sizeof(int) );
	long long int b_array[200010];
	long long int i = 0 , j = 0 , k = 0;
	long long int count = 0;

	i = k = l;
	j = m+1;
	//printf("merging\n");
	while ( i <= m && j <= h ) {
		//printf("comparing array[i] = %d and array[j] = %d\n" , array[i] , array[j]);
		if ( array[i] <= array[j] ) {
			b_array[k++] = array[i++];
		}
		else {

			count += ( m - i + 1 );
			//printf("inversion exist so count++ = %d\n" , count);
			b_array[k++] = array[j++];
		}

	}
	if ( i > m ) {
		while ( j <= h ) {
			b_array[k++] = array[j++];
		}
	}
	else if ( j > h ) {
		while ( i <= m ) {
			b_array[k++] = array[i++];
		}
	}

	k = l;
//
	while ( k <= h ) {
		array[k] = b_array[k];
		k++;
	}
	//printf(" Array after merging :\n ");
	//print_array ( array , l , h);
	//printf("FREEEE RETURNING\n");
	//free(b_array);
	//printf("RETURNING\n");
	return count;
}

long long int count_inv ( long long int * array , long long int start , long long int end ) {

	//print_array ( array , start , end );

	if ( start >= end ) return 0;

	//printf("end - start > 1 ... so\n");

	long long int mid = (start + end ) / 2;
	//print_array ( array , start , mid );

	long long int count_l = count_inv ( array , start , mid );
	//printf("count_inv of left_array = %d\n" , count_l);
	//print_array ( array , mid+1 , end );

	long long int count_r = count_inv ( array , mid+1 , end );
	//printf("count_inv of right_array = %d\n" , count_r);

	long long int count_m = merge ( array , start , mid , end );
	//printf("count_inv of merge = %d\n" , count_m);

	return count_l + count_r + count_m;
}

int main ( int argc , char * argv[] ) {

	long long int n , i , t;
	long long int *array;

	scanf("%lld" , &t);

	while ( t-- ) {

		scanf("%lld" , &n);

		array = (long long int *) malloc ( n * sizeof(long long int) );

		for ( i = 0 ; i < n ; i++ ) {
			scanf("%lld" , &array[i]);
		}
		
		printf("%lld\n" , count_inv( array , 0 , n-1 ) );

		free(array);

	}

	return 0;
}