UVA 11495 Bubbles and Buckets Solution

Problem Statement

Solution :
 This is a counting inversion problem.An inversion occurs when i < j and A[i] > A[j] where A is a list of numbers.

 

Algorithm to count inversion

Use divide and conquer

divide: size of sequence n to two lists of size n/2
conquer: count recursively two lists
combine:  this is a trick part (to do it in linear time)

combine use merge-and-count. Suppose the two lists are A, B.  They are already sorted.  Produce an output list L from A, B while also counting the number of inversions, (a,b) where a is-in A, b is-in B and a > b.

These algorithm is close enough to Merge sort. Using merge sort this problem can be solved easily.

Here is the C++ implementation of the problem.

#include <stdio.h>

#define sz 500000
#define inf 1000000000
long a[sz+2],cnt,L[sz+2],R[sz+2];

void merge(long p,long q,long r){
 long i,j,k,ind1,ind2;

 for(i = p,ind1 = 1;i <= q;i++){
  L[ind1++] = a[i];
 }
 L[ind1] = inf;

 for(i = q+1, ind2 = 1;i <= r;i++){
  R[ind2++] = a[i];
 }
 R[ind2] = inf;

 i = j = 1;

 for(k = p;k <= r;k++){
  if( L[i] > R[j] ){
   cnt += ind1 - i;
   a[k] = R[j];
   j++;
  }
  else{
   a[k] = L[i];
   i++;
  }
 }
}

void mergeSort(long p,long r){
 if( p < r){
  long q = (p+r)/2;
  mergeSort(p,q);
  mergeSort(q+1,r);
  merge(p,q,r);
 }
}

int main(){
 long i,n;

 while(scanf("%ld",&n)&&n){
  for( i = 1; i <= n; i++){
   scanf("%ld",&a[i]);
  }
  cnt = 0;
  mergeSort(1,n);
  if(cnt&1)
   printf("Marcelo\n");
  else
   printf("Carlos\n");

 }

 return 0;
}

Related UVA Problems:

299	Train Swapping
10327	Flip Sort
10810	Ultra Quicksort		Solution
11495	Bubbles and Buckets