10810 - Ultra-QuickSort

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos » Thu Feb 17, 2005 10:10 pm


harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

10810 confuse

Post by harry » Sun Feb 27, 2005 10:07 pm

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;
}



User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Feb 27, 2005 11:05 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Feb 27, 2005 11:20 pm

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.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Mar 07, 2005 12:33 pm

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

Input
5
5
2
3
4
1
Output
7

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:

Post by nukeu666 » Mon Mar 21, 2005 6:28 am

filigabriel wrote:
technobug wrote:How fast is your D+C algorithm? What is its idea?
My original program runs 8) in 1.150 seconds

Main idea was already posted by Eduard :D

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 :(
google

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Mar 21, 2005 8:52 am

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
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

10810 UltraQuick Sort (Speed)

Post by dpitts » Thu Jul 07, 2005 3:57 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Jul 07, 2005 5:48 am

dpitts wrote: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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Re: AC

Post by Antonio Ocampo » Sun Oct 02, 2005 9:42 pm

gvcormac wrote: 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 :wink:

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Thu Oct 06, 2005 8:37 pm

Plz help me!! :cry:

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Tue Oct 18, 2005 10:36 pm

Antonio Ocampo wrote:Plz help me!! :cry:
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
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

10810 - Ultra-QuickSort , TLE

Post by kangroo » Tue Oct 28, 2008 7:38 am

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
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 10810 - Ultra-QuickSort

Post by zobayer » Thu Sep 17, 2009 10:55 am

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!
You should not always say what you know, but you should always know what you say.

mehrab
New poster
Posts: 10
Joined: Sat Jul 03, 2010 3:04 pm

Re: 10810 - Ultra-QuickSort

Post by mehrab » Fri Jul 16, 2010 7:35 pm

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;
}


Post Reply

Return to “Volume 108 (10800-10899)”