10810  UltraQuickSort
Moderator: Board moderators
 lord_burgos
 New poster
 Posts: 43
 Joined: Mon Oct 13, 2003 4:54 pm
 Location: Mexico
 Contact:
10810 confuse
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
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
 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
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.
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.

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
is not enough. Imagine, for example, an extreme (nonbalanced) case of say:swap++;
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.
Check out http://www.algorithmist.com !
um...scanf is slow? so any replacements?filigabriel wrote:My original program runs in 1.150 secondstechnobug wrote:How fast is your D+C algorithm? What is its idea?
Main idea was already posted by Eduard
I've managed for optimization, and now runs in 0.771. Showing that scanf is slow.
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
10810 UltraQuick Sort (Speed)
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
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
That's me.dpitts wrote:I have a working solution in ~1.3 seconds, but someone has it in .174?
I don't know any O(n) solution. My program is based on mergesort, 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.)

 Experienced poster
 Posts: 131
 Joined: Sat Jul 17, 2004 4:09 am
 Location: Lima, Per
Re: AC
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.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.
Code: Select all
#include <stdio.h>
int a[500001];
long long cont;
int particion(int a[],int p, int r)
{
int j,t,i=p1,x=a[r];
for(j=p; j<=r1;++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,q1);
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);
}
}

 Experienced poster
 Posts: 131
 Joined: Sat Jul 17, 2004 4:09 am
 Location: Lima, Per
10810  UltraQuickSort , TLE
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 !!
thanks again !!
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;
}

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 10810  UltraQuickSort
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:
Please help and thanks in advance!
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,n1);
printf("%lld\n",res);
f = 1;
}
p = strtok(0," \n");
}
return 0;
}
You should not always say what you know, but you should always know what you say.
Re: 10810  UltraQuickSort
Can anyone help me ... i'm getting runtime error for this problem...
can anyone tell me what mistake i have done?
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<cas1) && flag) ;i++)
{
flag=0;
for(j=0;j<cas1;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;
}