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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10810 - Ultra-QuickSort

Post by sazzadcsedu » Fri Jul 16, 2010 9:05 pm

I did not check your code.But one thing i can say even if ur code avoid run time error, it can't avoid time limit exceed .Input size is 50000.So (n^2) bubble sort cant pass time limit, u have to use (nlogn) sorting algorithm like merge sort.
Best of luck with merge sort.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

seraph
New poster
Posts: 9
Joined: Tue Dec 15, 2009 4:18 pm

Re: 10810 - Ultra-QuickSort

Post by seraph » Fri Sep 17, 2010 6:13 pm

why i got WA in my code ?

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
static long long sw,n;
static long long v[500001];
void gabung(int p,int q,int r)
{
    long long n1 = q-p+1;
    long long n2 = r-q;
    long long i,j;
    long long L[n1+1], R[n2+1];
    for (i=0;i<n1;i++)
        L[i]=v[p+i];
    for (j=0;j<n2;j++)
        R[j]=v[q+j+1];
    i=0;j=0;
    L[n1]=1000000000;
    R[n2]=1000000000;
    for (int k=p;k<=r;k++)
    {
        if (L[i]<=R[j])
        {
            v[k]=L[i];
            i++;
        }
        else
        {
            v[k]=R[j];
            j++;
            if (L[i]!=1000000000)
                sw+=j;
        }
    }
}
void divide(int awal, int akhir)
{
    if (awal < akhir)
    {
        long long q=(awal+akhir)/2;
        divide(awal,q);
        divide(q+1,akhir);
        gabung(awal,q,akhir);
    }
}
int main()
{
    int temp;
    
    while (cin>>n)
    {
        if (n==0)
            break;
        sw=0;
        memset(v,0,sizeof(v));
        for (int i=0;i<n;i++)
        {
            scanf("%lld",&v[i]);
        }
        divide(0,n-1);
        cout<<sw<<endl;
        //for (int i=0;i<n;i++)
        //    cout<<v[i]<<" ";
        //cout<<endl;
    }
    return 0;
}
please help me..

User avatar
N@$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm

10810 - Ultra-QuickSort (Data type 'long' is enough)

Post by N@$!M » Wed Nov 24, 2010 4:27 pm

I've used the Merge Sort approach and got Accepted with the long datatype. So, now a days I think long long is not necessary for this problem.
( <---- 24 November, 2010)

Also got Accepted in the BST approach... but it took greater runtime.
"I AM NOT SURE WHETHER I SHOULD BE CONFUSED OR NOT..."
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet- 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.
Bangladesh.

e-Mail Address:
tariqmnasim@gmail.com

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10810 - Ultra-QuickSort

Post by Shafaet_du » Sun May 01, 2011 4:19 pm

I got WA until i used LONG LONG.
Try this case:

Code: Select all

10
324 123 123 123 213 435 678 234 879 234
0
ans 11

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

Re: 10810 - Ultra-QuickSort

Post by surya ss » Tue May 17, 2011 11:18 am

I tried using long too and accepted :)
it mean the judge computer using 64bit now ?
i tried in the 64bit computer and print sizeof(long) and it return 8 which is sizeof(long long) in 32bit computer

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 10810 - Ultra-QuickSort

Post by sith » Fri Jun 22, 2012 11:02 pm

Hello
I've got WA

Why?

Here is my code

Code: Select all

AC

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10810 - Ultra-QuickSort

Post by lighted » Sun Oct 26, 2014 1:18 pm

Got accepted with mergesort 10810 (11858, 11495, 10327). This problem was useful to learn the way to find number of inversions in O(N*logN) with Divide and Conquer algorithm. :)
gvcormac wrote:
sohel wrote:I also used D&C and got AC in 2.14 seconds..

.. its funny that to solve a quicksort program, one has to implement merge sort.

- It also seems that some managed to solve it taking < 1sec time.
Is there any other method other then the classical merge sort?
The sort in the problem is "quicksort" in name only.

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 think that straightforward solution with Quicksort will get TLE.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 108 (10800-10899)”