10810 - Ultra-QuickSort

[lord_burgos]

input example : http://plg.uwaterloo.ca/~acm00/050205/data/B.1.dat
output example : http://plg.uwaterloo.ca/~acm00/050205/data/B.1.diff

[harry]

can any one explain why the output for
5 9 1 0 5 4
is 6
it seems to be 5 for me using mergesort

here is my code

#include<stdio.h>
#include<stdlib.h>
#define Max 500000
#define MaxValue 999999999

long long int A[Max+2],temp[Max+2],R[Max+2],swap,s,n,inf = MaxValue+1;




void merge(long long int numbers[],long long int temp[],long long int left,long long int mid,long long int right)
{
long long int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;

swap++;

}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
void m_sort(long long int numbers[], long long int temp[], long long int left, int right)
{
long long int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);
}
}


void mergeSort(long long numbers[], long long int temp[], long long int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}

int main()
{
long long int i;

while(1)
{
scanf("%lld",&n);
if(!n)break;
i=0;
while(i<n)
{
scanf("%lld",&A);
i++;
}
s=swap=0;
mergeSort(A,temp,n);
//qsort(&a[0],n,sizeof(a[0]),sort);
printf("%lld\n",swap);
//printf("%d\n",s);
}

return 0;
}

[Krzysztof Duleba]

9 1 0 5 4
9 0 1 5 4
0 9 1 5 4
0 1 9 5 4
0 1 9 4 5
0 1 4 9 5
0 1 4 5 9

There are 7 states and 6 steps. It's easy to see that this is the optimal solution.

In fact, it's also easy to see that what we should find is the number of inversions in the sequence (inversion is a situation when a > a[i + k]). In your sequence, there are 6 inversions (9 1, 9 0, 9 5, 9 4, 1 0, 5 4), hence the result.

I don't know what do you count with your mergesort - my algorithm is also based on divide and conquer and it gives correct answers.

[Larry]

swap++;

is not enough. Imagine, for example, an extreme (non-balanced) case of say:

100 101 102 103 104 105 106 107 1

and your partition is magically given as:
100 101 102 103 104 105 106 107
and
1

then you would return the number of swaps as 1.

[shamim]

if anyone gets WA after using long long, try this case:

Input

5
5
2
3
4
1

Output

7

[nukeu666]

How fast is your D+C algorithm? What is its idea?

My original program runs in 1.150 seconds

Main idea was already posted by Eduard

I've managed for optimization, and now runs in 0.771. Showing that scanf is slow.

um...scanf is slow? so any replacements?
im still a noobie so dont know about the algos talked about here
method i used was that when every number was enetered, it would count the number of numbers bigger than it before it and print the sum
takes 10.2 secs

[mf]

You can use functions fread() and read() to grab large blocks of input into your own buffers, then parse manually it. This way you'll avoid the overhead of calling scanf() millions times.
It will approximately save you 0.500-0.600 sec. on this problem.

[dpitts]

I have a working solution in ~1.3 seconds, but someone has it in .174? Did they know judges output, or can someone help me with a faster algorithm?

My current algorithm builds a tree based on the bits in the numbers. Each node in the tree has a left (zero) and right (one) child, and a count of how many numbers are to the right (one) side.
Each row in the tree represents that bit (starting with the MSB).

If you traverse left (there was a zero), then anything that had a one there was greater than the current number, and thus needed that many swaps. If you traverse right (there was a one), then you need to add one to the count.

This results in a complexity of O(N) I believe. however, each iteration has high constant time. Is there a faster O(N) algorithm? Or even an O(nlogn) that beats out for N <= 500000?

Yes, I know I should be proud enough of an AC answer, but I would like to know how to get a fast answer too

[mf]

I have a working solution in ~1.3 seconds, but someone has it in .174?

That's me.
I don't know any O(n) solution. My program is based on merge-sort, which is Theta(n log n). With some optimizations, it runs .434 seconds.
My .172 sec. submission has a hardcoded answer to the toughest test case (I don't know the judge's data, I just spent some submissions to figure out that number.)

[Antonio Ocampo]

There's a straightforward solution using quicksort. Just count the
number of inversions you have to do when you arrange the elements
about the pivot.

I has already gotten AC with merge sort but now i'm trying to solve this problem using quicksort. However, i'm a little bit confused with cormack's hint . How can I count the number of inversions? I tried it with this idea but I get incorrect answers when the numbers are already sorted.

Code: Select all

#include <stdio.h>

int a[500001];
long long cont;


int particion(int a[],int p, int r)
{
   int j,t,i=p-1,x=a[r];
   
   for(j=p; j<=r-1;++j)
   {
     if( a[j]<=x )
     {
       ++i;
       t=a[i];
       a[i]=a[j];
       a[j]=t;
       ++cont;
     }    
   }
   
   t=a[i+1];
   a[i+1]=a[r];
   a[r]=t;
   ++cont;
   
   return i+1;   
}

void quick(int a[],int p, int r)
{
   int q;
   
   if(p<r)
   {
     q=particion(a,p,r);
     quick(a,p,q-1);
     quick(a,q+1,r);
   }
}


int main()
{
  int i,n;
  
  while(1)
  {
    scanf("%i",&n);
    
    if(n==0)
     return 0;
  
    for(i=1; i<=n; ++i)
     scanf("%i",&a[i]);
         
    cont=0;
    quick(a,1,n);    
    printf("%lli\n",cont);                 
  }
}

Thx in advance

[Antonio Ocampo]

Plz help me!!

[misof]

Plz help me!!

When swapping two non-adjacent numbers the number of inversions doesn't have to decrease by 1.

E.g., in the array 8 1 2 3 0 if you swap 8 and 0, the number of inversions decreases by 4.

BTW, I find it easier to make mergesort count the number of inversions.

[kangroo]

Hi,
I tried to use binary tree and count the number of swaps needed but getting TLE......
below is my code...anyone pls help me !!
thanks in advance !!

Code: Select all

#include <iostream>
using namespace std;

struct node
{
 int val;
 struct node *left;
 struct node *right;
};

long long cnt;
struct node *root;

void right_subtree ( struct node *p )
{
 struct node *q;
 q = p -> right; 
 if ( q == NULL ) return;
 else
 {
  cnt ++;
  if ( q -> left != NULL )
   right_subtree( q -> left );
  if ( q -> right != NULL )
   right_subtree( q -> right );
 }
 return;
}

struct node *addtree ( struct node *p , int x )
{
 struct node* q;
 if ( p == NULL ) 
 {
  p = new node();
  p -> val = x;
  p -> left = p -> right = NULL;
 }

 else if ( x < p -> val )
 { 
  cnt ++; 
  right_subtree(p);
  p -> left = addtree ( p -> left , x );
 }
 else 
  p -> right = addtree ( p -> right , x );
  
 return p;
}

int main ()
{
 int n;
 while ( scanf ( "%d" , &n ) == 1 && n )
 {
  root = NULL; 
  cnt = 0;
  for ( int i = 0 ; i < n ; i ++ )
  {
   int x;
   scanf ( "%d" , &x );
   root = addtree ( root , x );
  }
  printf ( "%lld\n" , cnt );
  //if ( cnt%2 ) printf ( "Marcelo\n" ); 
  //else printf ( "Carlos\n" );
 }
 return 0;
}

thanks again !!

[zobayer]

I was trying to solve this problem using fread (just to test how it works)... but getting WA, I got AC in 0.188 using scanf and when I'm using fread, how much memory should I read at once... I tried 20MB but it fails

this is the parsing routine I am using:

Code: Select all

int main()
{
	int i, n, f = 1;
	//freopen("fread.in","r",stdin);
	fread(buffer,29999999,1,stdin); // char buffer[30000000];
	p = strtok(buffer," \n");
	while(p)
	{
		if(f)
		{
			n = atoi(p);
			i = f = res = 0;
		}
		else if(i<n)
		{
			a[i++] = atoi(p);
		}
		if(i==n)
		{
			solve(0,n-1);
			printf("%lld\n",res);
			f = 1;
		}
		p = strtok(0," \n");
	}
	return 0;
}

Please help and thanks in advance!

[mehrab]

Can anyone help me ... i'm getting runtime error for this problem...
can anyone tell me what mistake i have done?

Code: Select all

#include <stdio.h>


long long int number[50000];

long long int bubble_sort(long long int *a,long long int cas)

{
	long long int i,j,temp;
	int flag=1;
	long long int count=0;

	for(i=0;( (i<cas-1) && flag) ;i++)
	{
		flag=0;
		for(j=0;j<cas-1;j++)
		{
			if(a[j]>a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
				flag=1;
				count++;
			}
		}
	}

	return (count);
}




int main()
{
       long long int count1,cas,i;

       while(scanf("%lld",&cas)==1)
       {
	    if(cas==0)
	    break;

	    for(i=0;i<cas;i++)
	    {
		scanf("%lld",&number[i]);
	    }

	    count1=bubble_sort(&number[0],cas);
	    printf("%lld\n",count1);
       }
       return 0;
}