Turbo Sort

Somehow, this problem is timing out with JAVA using even the best time complexity u can have, which is O(n)....

So far, only 1 person has been able to solve this using JAVA...what I mean is are JAVA programmers inferior to their C counterparts, or is it something with the constaints ??

it even timed out when using cout : cin in C . so i have to implement counting sort using scanf:printf

Inspite of using a good compexity of quicksort ! It times out!!

i have tried so much times but every time the problem compiled and run on my system but on codechef it gives compilation error plz help i m frusted now

@Kshitij I believe the time limit for java is 2x the time limit for C programs.

@varrun Quicksort has a worst case complexity of O(n^2)
@kamlendra codechef uses the GNU compiler collection. What compiler are you compiling on?

Merge sort didn't work for me either. Even heap sort so it can sort while reading input didn't work in Java...

using the in-built Arrays.sort() times out in Java... so what is the solution to this problem?

@siddharth Write your own sort function?

The top 6 contenders here (the best competitors on codechef...) have somehow managed to optimize their code to an extent that is much greater than the pack (which includes me here). Everyone, except these 6 are beyond 2 seconds. Anybody knows how to get down to those time scales?

What other optimizations are possible in Java ? The algorithm is already O(n). Using primitive arrays... any pointers would be appreciated.

Faster IO maybe?

I have implemented my solution in c, and it runs fine on my machine. However on their servers it says I get the wrong answer. Is there any way to figure out where they were saying mine went wrong.

Not at the moment. You need to take care that the numbers need not be distinct.

@Directi Admin
Thanks for the big "faster IO" hint!!! :)

I implemented Merge-sort in Java and I ran out of time :(

I programmed the solution in C. For 10^6 input values my program runs 1.2sec on my machine.
Then I ported the code to java. It uses primitive arrays, data and operations all over. I read input using System.in.read() - the result is a run time of 17sec.
I'm so curious if someone has solved this using java and how!

This problem has been solved in Java. See the successful submissions' list.

Hi, I've contacted that person and am waiting for an answer. My suggestion is that the i/o part is the bottleneck. What means of i/o should one use in Java generally? Thx.

For Java, it's suggested to create your own reader class.
http://www.spoj.pl/forum/viewtopic.php?f=43

I got a timeout error for this, does that mean that the solution was right it just took too long, or does the program cut off at 5s and it could still be a wrong answer?

A timeout means that your code took more than the specified time. It says nothing about the correctness of your code.

guys since we know the range of the numbers we can use Counting Sort which will be O(n) .Comparison sort based algos wont work with this problem . Besided ,using fread etc for I/O will further speed up the soln .the secret to a successful soln lies in the algo .

This can be solved using comparison based sorting techniques :)

yes ,using comparison based techniques this can certainly be solved, but keeping within the time limit of 5s may become very difficult. counting sort works much faster.

why i am getting a wrong answer? i did merge sort. when i am testing with numbers i am getting right answers. Admins kindly please check.

@admin: Can you please tell more about faster I/O? Are you talking about NIO Apis or are you suggesting to use the Buffered I/O?

Any kind of I/O which is faster than the normal methods of printf(), scanf() etc are considered to be faster I/O. You can do this in a lot of different ways.

which sort method can be used in this problem

There are a lot of different sorting algorithms that can be used to sort the numbers here. Most efficient implementations of algorithms with complexity O(n logn) should clear.

mine works well with C++ but dosnt work with java. Same code gives compile time error in JAVA i dont know why.

Please read the FAQ

The example for Turbo Sort is in error. According to the instructions you want sorted output in non decreasing order. Your output is 1 3 5 6 7 which is an example of increasing order. Non decreasing order would be 1 3 5 5 6 7. Do you want decreasing order as specified or increasing order as shown?

Thank you,

 

Robert

 

 

@robert non decreasing order means !(decreasing order) which IS the "increasing" order

@robert the first number in the input in the no. of inputs tht r to b sorted ...so first 5 in the input says tht there r 5 numbers tht r to b sorted.....jst read the ques carefully....

Ravi, Shivmitra,

Thank you very much.

Robert

Even by using treeset its giving timeout............wat is the soln for this problem in Java

Very odd discrepencies between my results on my machine and on the server machine...

My first method:
My machine: 2.5 secs
Server: 3.14 secs

Second highly optimized method:
My machine: 0.405 secs !!!!
Server: 3.78 secs ?!

This is very frustrating, are there any technical specs for the server / build command? I'd like to know how such a huge improvement on my end actually slowed down my running time!

If you calculate the performance difference between the machines:
3.14 / 2.5 = 1.256
Based on that number, the approximate runtime would be expected to be roughly:
0.405 * 1.256 = 0.509 secs !! (Faster than the current best!)

With such discrepancies, it's extremely difficult to predict how any changes will affect the server's runtime numbers.. so I'll just give up on this and take it as a personal win!! ;)

If only michael hayter could send me his code so I can compare on my machine >:-)

why is it coming runtime error ??? its working fine on bloodshed dev ....

Please read the FAQ and Sample Solutions

I have had seven TLE's on this sort. My latest algorithm has been a very simple counting sort. It is designed to work with a maximim number of 1,000,000 numbers between 0 and 1,000,000. To test the algorithm I used a random number generator to generate a file of first 100 numbers to check the accuracy of the sort and then 1,000,000 numbers to check timing.  The one hundred number test ran well as did the million number test. The language used is Python. The timings for the million item test run was a user time of 4.588 seconds and a system time of 1.640 seconds. Total of 6.228 seconds. In reviewing the results for those python programs which passed this test, the results ran from 5.98 seconds to 14.59 seconds. Doubling my time to possibly account for timing differences between your machine and mine that still places me in the passing range.

Is it possible for one of your moderators to look at my code and tell me if:

1)  I am approaching the problem from the totally wrong perspective,

2)  The approach is correct but that some of the code is superfluous, and,

3)  If the approach is correct, and I have a silly glaring error in logic, perhaps a hint would be truly appreciated.

I will be happy to send you the code if you cannot review the latest run.

 

Thank you,

 

Robert

 

why doesn't non-decreading order mean anything but non-decreasing order?

 

It could be scrambled numbers and still be non decreasing order. which means that it should not necessiarly be in increasing order.

 

You should clarify the problem.

@Robert You might want to try an NlogN algorithm.

 

@Notneeded Could you give an example of what you mean?

I keep getting a segfault on your machine with my nasm program, which runs fine on my laptop. I've tried it with various boundary conditions: a file with just one line of "0"; a file with "1" followed by "0"; your sample inputs above; and with 1000000 inputs ranging from 0 to 1000000. I've made sure it works with both unix (n) and windows (rn) newlines. Any hints as to boundary conditions I haven't considered?

@notNeeded: it says "non-decreasing" instead of "increasing" because there could be duplicate samples, in which case it won't increase at all from one to the next; non-decreasing in this case means it NEVER decreases from one output to the next. Scrambled numbers thus wouldn't qualify.

10
10
11
22 } non-decreasing
22
33

10
11
10 <- decrease from 11 here
22
33
22 <- decrease from 33 here

what's wrong with this approach?

 

#define RANGE 1000001
#include <iostream>
int main() {
int T,num; scanf("%d", &T);
unsigned int arr[RANGE];
for(int i=0; i<RANGE; i++) arr[i] = 0;
while(T--) {
scanf("%d", &num);
arr[num]++;
}
for(int i=0; i<RANGE; i++) {
while(arr[i]--) printf("%dn",i);
}
return 0;
}

You don't initialise the values of arr, which is a local variable thus won't be 0s.

that bug bit me once too, in another program. if you place your arrays outside of a function, they'll be placed in the .bss segment, which IIRC is guaranteed by the ELF loader to be zeroed.

@bezgin: that's the approach used by my C program, but I had to replace scanf and printf with optimized routines in order to get the execution time down.

finally got my nasm program running on CodeChef! the "boundary" condition I wasn't prepared for was lack of a newline at the end of the last sample!

lol at your nasm adventure :)

my turbosort works fine now, i had OFF-BY-ONE bug, the above code works! Thx.

@bezgin: you're right, the merry man was wrong, you DID initialize the array to zeros. but if you'd put the array outside of main(), you wouldn't have had to.

my optimized assembly language is only 5 hundredths of a second faster than my C program! and far less maintainable! wtf!?!?! think it's time for a beer...

No he didn't, and no I wasn't :P He edited his comment to have accepted code as his last post states ;)

@Stephen: ah. my bad. wasn't aware that comments could be edited.

Is it right to try and use threads in java for this program?

I also got a runtime error, would that be because i used up to much memory?

Ok i cant figure out the answer. Im reading everything into an int array[] doing Arrays.sort() then printing everything out. I have been messing around with output but cant seem to find anything. Can any one tell me where i could atleast start looking for an answer?

Try moving w.flush() outside of the loop.

i used w.flush() but little boxes are printed out instead of integers

You have got to be kidding me.... i figured it out. Wow... this was bugging me.

wrong answer plz help

 

#include<stdio.h>
int main()
{
int i,j,temp,a[100],t;
if(t<=1000000)
{
scanf("%d",&t);
}
else
{
return 0;
}
for(i=0;i<t;i++)
{
scanf("%d", &a[i]);
if(a[i]>1000000)
{
return 0;
}
}
for(i=0;i<t;i++)
{
for(j=i;j<t;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(i=0;i<t;i++)
{
printf("%dn",a[i]);
}
return 0;
}

There are two lines in the section called 'Input'. Try reading the first one.

the input conditions are met in my program .... i m not able to understand the error!! plz help

Tell me what the first line of the input says. And then how that is met by your program.

I tried count sort with python. Still get TLE.

Any suggestions?

 

I used xrange instead of range. And I initialized the array using:

numbers = [0] * 1000001

 

Is that okay?

I have implemented counting sort in ruby. Still it gives me time limit exceeded. What should I do ?

how to define this big array in C .  My programme in codeblocks doesn't give any compile time error  or warning , but on running it computer is hanging .

 

 

On reducing the array length programme in working fine.

 

help

Try declaring it outside of any function.

what is better I/O than printf and scnaf ?? i tried to figure out but cudnt

does codechef passes files as

< filename to the executables ???

I believe it would be very difficult to get an interpreted language like Python or Ruby to pass this test. Even using psyco for JIT compilation rarely gets you even close to C or C++ speeds. Python is good for many problems but not this particular one. Probably same story with Ruby, I'm not as familiar with it.

I usually prototype a solution in Python, then port to C for speed once the algorithm is somewhat optimized. Don't know if it's the best approach but it works for me. When it doesn't it usually means my algorithm sucks.

I just can't pass this "Time Limit Exceeded" error . Did anyone managed to solve this using C# ?

my third try gave me correct answer ..

...

I am using count sort in C . and getting time of 2.33 sec

hmmm im having problems declaring an array with 10^6 size ....help guys??

First, i'm using java, i did the o(n) sort thing, then i found that i got the TLE error, so i tried using faster input and output according to the admin's hint and what this page said but i still couldn't work it out, i still get the TLE error.. what else could i do.. cause i still see java programmers who found a way to solve this.. any hints?

Your read method isn't very good at all; it is probably slower than just using a BufferedReader. You are using immutable strings and concatenating these multiple times which is very very slow. You should be writing your own parseInt function which works directly with the characters, not using Strings at all.

ok finally got it to work lol, had to look around for fast input AND output codes :(

hello everyone,

if anybody submitted this problem in pythonthen pls help me ....

You've gotta know some asm for this

Wow...I don't understand why people don't make their questions clearer....

 

Instead of trying to be all "l33t", just write out the question exactly how you want it solved.

How could this question possibly be made clearer?

@Shailendra: my Python solution took over 12 seconds to run, but here's the code: http://www.codechef.com/viewsolution/113103

sir my program is here.there is runtime error.

cn u tell me wht problem is der?

my programm:

#include<stdio.h>
int main()
{
  long int *p;
  long int no;
  long int i,j,temp;

  printf("input:n");
  scanf("%ld",&no);
  for(i=0;i<no;i++)
  {
     scanf("%ld",(p+i));

  }
  for(i=0;i<no;i++)
  {
     for(j=i+1;j<no;j++)
     {
     if(*(p+i)>*(p+j))
 {
    temp=*(p+i);
    *(p+i)=*(p+j);
    *(p+j)=temp;
 }
     }
  }
  printf("noutput:n");
  for(i=0;i<no;i++)
  {
    printf("%ldn",*(p+i));
  }
  return 0;
}

tell me wht's the run time error.

my id_:rajesh91bhatia@gmail.com

 

hello sir

how can i find the compiletion time??????????///

pls tell me

 

What do you mean by that?

Hi,

I'm using a counting sort in C and I'm using the int_fast32_t data type. However I'm still getting TLE! I'm attaching my code. Can you tell me why this isn't working within the time limits. Thank you

#define MAX 1000001
#include<stdio.h>
#include<stdint.h>
#include<inttypes.h>

int_fast32_t arr[MAX];
int_fast32_t i,num;

int main()
{
int_fast32_t T;
scanf(SCNdFAST32,&T);

for(i=0; i<t; i++)
{
scanf(SCNdFAST32,&num);
arr[num]++;
}
for(i=0; i<MAX; i++)
{
while(arr[i]--)
printf(PRIdFAST32"n",i);
}   
}

Ok, so I went back and tried doing this program in Java. I'm using a counting sort and my own input routine which reads in 64K bytes at one go into a buffer. The code is given here:

http://www.codechef.com/viewsolution/168217

I understand that C will be much faster; but I would really like to know what part of my program is causing Time Limit Exceeded given that it's in Java which is a language I'm allowed to code in.

Please don't reply Java is too slow etc etc. I would really appreciate it if someone could point me to how to make the exisiting Java code work within the time constraints. Thank you.

CAN ANYONE TELL ME OR PROVIDE ME WITH A LINK ON HOW TO CREATE MY OWN IO CLASSES IN C,C++ ????

plzzzzzzzzz HELP !!!!!

@Hiren: there are plenty of world-readable solutions here at CodeChef.com. Look at the fastest programs in C and C++ and you will find an assortment of highly optimized input routines. You don't really mean "classes" in the OO sense, do you?

@Saurajit: some suggestions: have you created your own stress testdeck? Have you tried one of the profilers available for Java? Have you commented out parts of the code to see if you can get WA rather than TLE?

IT RUNS FINE ON MY COMPUTER WATS WRONG WITH IT. IT GIVES RUNTIME ERROR ON OUR SITE

THE OUTPUT IS LIKE THIS:

5
5
3
6
7
1

1
3
5
6
7

plzzzzzzzzz tell me wats wrong, why it gives runtime error. m using gcc compiler

IS IT BECAUSE OF THE LINE SPACE BETWEEN INPUT AND OUTPUT

 

You have already solved your own problem, but please read the FAQ before posting a comment.

@java developers.

 

tis possible to use Arrays.sort(). and get the job done. (I did it) u just need faster I/O

 

System.out.println() for output wont do it for u neither will using a BufferedReader for input

@anthony and john

 

Thanks for the input! Unfortunately, I'm new to this and I don't know how to create a stress test deck for my java program.

I reworked the output part of the code. Earlier I was using System.out.println. Now, this is the section that outputs (i'm using counting sort and the buffer length is 8192):

oplen=0;     
for(i=0; i<1000001; i++)
{    while(arr[i]-- >0 )
{
String s=Integer.toString(i);
int len = s.length();
char[] temp = s.toCharArray();
if(oplen<SIZE-len-1)
{
for(int jj=0; jj<len; jj++)
buf[oplen++]=(byte)temp[jj];
buf[oplen++]=10;                         //newline
}
else
{
System.out.write(buf,0,oplen);
oplen=0;
}
}
}
//System.out.println(Arrays.toString(buf));   
if(oplen>0)
{   
System.out.write(buf,0,oplen);        
}

But now I'm getting a WA!! Since this is the only part of the code I've changed, I'm assuming the error's here, but for the life of me I can't figure out what it is!

we can't use vectors ?

Sure you can. Except you've submitted your code as C code; they don't exist in C.

please show the solutions as well plzzzzzz

counting sort get accepted in 2.** sec, And further doing fast INPUT OUTPUT method decrease to 0.9 sec :)

Hi,

I just submitted my bash script but it failed with a runtime exception. Is "sort" installed?
Is there a list of all the unix utilities installed on your system (e.g. sort, cut, grep, bc etc)?

Thanks

Hi I was wondering what else I can do to speed up my code. I have changed all cin and cout to printf and scanf, and have eliminated all loops that seemed excessive, and have only one while loop. Does anyone have any other suggestions as to how to speed up my code.

@bob

i think there is some problem in code inside while loop ... its not working properly...

try algorithm of O(nlog(n)) like quick sort to solve this problem in time limit ... for better u can also use liner complexity algo but i think quick sort is sufficient to solve in time limit

@Devendra Pratap Singh

 

Thanks both of your suggestions led to solutions under the time limit.

ok I implemented MergeSort and its working fine on my PC.

But when i load it up on the server, It says wrong answer. Not Time Out, Wrong Answer.. how can that be? its working fine on the PC!!!!

runtime error plz help

#include <iostream>

 

using namespace std;

 

int main()

{

int n[100],k,t;

cin>>t;

for(int i=0;i<t;i++)

{cin>>n[i];

for(int j=0;j<i;j++)

{if(n[j]<n[i])

{continue;}

else {

k=n[i];

n[i]=n[j];

n[j]=k;}

}

}

cout<<"the outputn";

for(int m=0;m<t;m++)

cout<<n[m]<<endl;

return 0;

}

Read the input/output format. The errors are obvious.

hi :)

just a quick question to those who successfully submitted solutions to the above question in PYTHON... which algorithm would be suitable??

I used bucket sort, counting sort, as well as running an insertion sort over the elements after dividing them into buckets... but I'm still not able to get the code to run within the specified time limits. Can someone please give me some suggestions ?? Any help would be appreciated :) thanks

how do u input and store such large set of numbers ?

please tell me ????

@Admin :

Please Help me out with this problem, can't seem to find what is going wrong. It gives TLE, i have tried all the methods i know. Please help.

The links to two different approaches are:

http://www.codechef.com/viewsolution/245663

http://www.codechef.com/viewsolution/245683

both give wrong answers :(

 

PLEASE HELP :(

@Amit :

There is nothing you need to do in it. just take input sort using STL function sort. that will accepted.

@Pankaj

Sir, i would still want to know the problem with my approach. I mean are all the type of input methods i'm using giving these TLE errors ? Because i can't seem to find why the randomized QS with expect n*logn time shouldn't work.

The first thing I tested your code on was a million ones. It still hasn't finished running.

Hey Stephen, thanks for your valuable hint :)

runtime error...plz help

 

#include<iostream>

#include<stdlib.h>

//#include <conio.h>

 

using namespace std;

 

void swap(int *x,int *y)

{

int temp;

temp=*x;

*x=*y;

*y=temp;

}

int partition(int a[],int p,int r)

{

int x=a[r];

int i=p-1;

for(int j=p;j<=r-1;j++){

if(a[j]<=x){

i=i+1;

swap(&a[i],&a[j]);

}

}

swap(&a[i+1],&a[r]);

return i+1;

}

void quicksort(int a[],int p,int r)

{

if(p<r){

int q=partition(a,p,r);

quicksort(a,p,q-1);

quicksort(a,q+1,r);

}

 

}

 

int main()

{

int n;

int a[100]={1};

//cout<<"enter the number of elements"<<endl;

cin>>n;

//cout<<"now enter the elements"<<endl;

for(int i=0;i<n;i++)

cin>>a[i];

quicksort(a,0,n-1);

//cout<<"sorted array is---->"<<endl;

//cout<<a[0];

for(int i=0;i<n;i++)

cout<<a[i]<<endl;

//getch();

system("pause");

return 0;

}

read input statement again

 

t – the number of numbers in list, then t lines follow [t <= 10^6].

 

array u use can store maximum 100 number  while input can be till 10^6  ... thats why it result to run time error

my program run correct on my system. But gave run time error on code craft the code is

#include<iostream>
using namespace std;
int t,a[100];
void del(int);
int main()
{
int i,j,k;
cin>>t;
for(j=0;j<t;j++)
cin>>a[j];  
for(j=0;j<t;j++)
for(k=j+1;k<t;k++)
{ if(a[j]>a[k])
{int temp;
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
}
a:
for(k=0;k<t;k++)
{  if(a[k]==a[k+1])
{ for(int i=k;i<t;i++)
a[i]=a[i+1];
t--;
goto a; 
}                        
}
for(j=0;j<t;j++)
cout<<a[j]<<"n";
return 0; 
}

 

please any body help if their is problem in input or output..........

i will highly thankful to him .My email id-bhogal.1198@gmail.com

@above

 

reason for runtime eroor is that u r using array of size 100 ... so how it can store more than 100 element...

change ur array to a[1000010]

<pre>a   a</pre>

Can anyone please tell me what improvements can be done to this code in JAVA to pass the time limit. Its giving time limite exceeded (TLE). I have already tried scanning all the input and then doing the computation, that didnt work either.

counting sort

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;

/*counting sort*/

public class dexp {
    public static void main (String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out, true);
        int t = Integer.parseInt(in.readLine());        
        int[] frequency = new int[t];
        for(int i = 0; i < t; i++)
            frequency[Integer.parseInt(in.readLine())]++;
        for(int i = 0; i < t; i++) {
            for(int j = 0; j < frequency[i]; j++)
                out.println(i);
        }
    }
}

class name that I submitted was Main.java so thats not the error.

@digviay Singh / saurajit

instead of using a PrintWriter try using

PrintStream out =new PrintStream(new BufferedOutputStream(System.out));

@anthony musyoki

Thanks, it worked, though it showed 7.63 seconds. I need to work on input method.

how can i see others' solution of this problem????

can any one sort this array with complexity O(n)?????

an array normally doesnt take more than 10^4...... it gives a compile time error if we try to declare more than this.... how can i declare an array of max size 10^6.....

I get this error when I submit! contest_problem_id field is required.

Any headers I need to place in the file?

Each line contains one integer: N [0 <= N <= 10^6]

 

the above line means the value of N should not exceed 10  ,am i correct?

plz let me know.

@ravi:

No , that means

N<=1000000

I first tried implementing quick sort in C++, but got runtime error. I guess I was using up too much memory to create vector<unsigned int>s. Then I used std::sort and it worked just fine.

i used bubble sort can anyone tell the mistake in my code

 

 

 

Please don't post your code here. Have you tested your code on an input of size 1000000? Bubble sort is O(n^2), so it will be far too slow.

Simple printing of numbers from 1 to 1000000 takes lot of time in C#

int start = Environment.TickCount;
for (int i = 0; i < 1000001; i++)
Console.WriteLine(i);
int stop = Environment.TickCount;
int time = stop - start;

I got time = 123210 which is in ms. so it comes out ~= 2 minutes. I have latest PC configuration again.

Are you sure you are timing the execution time of your program, and not how long it takes to display the numbers on your screen? (You should test by redirecting output to a file as mentioned in the FAQ).

then wht is the solution for storing 10^6 nos. if array can only store 100. why does not it shows error while in my computer ?

An array can easily store 10^6 numbers..

Hi Stephen,

I didn't get you exactly & from FAQ, So do we need to direct the output to console or to out.txt? directly to console takes time in minutes while directing to txt file doesn't take time I mean hardly 1-2 sec. FAQ & test programs given tells it should be directed to console output except for testing which tells out.txt. And after submission it shows time limit exceeded if directed to console output & runtime error if directed to "out.txt"?

Please help on this one.

Your program should always write to the standard output stream. But when testing your program, Codechef will redirect the standard output stream to a file, it will not run your program and display the results on its 'screen' (which is the part that takes a long time).

Ok Stephen last question, So if the solution is O(n) basically 2n, & if it is time limit exceeded, then is it problem with algorithm or language or chodechef environment, or something else. because further optimization looks difficult.

well thn why i am getting runtime error... my program is correct and runing in my computer... i used insertion sort ... plez explain where is the problem ...i am confused

"Internal error" - is that codechef buckling under load?

This is so wrong. Same algorithm pass the time in when written in C++ but does not pass when written in C#. It looks bound checking or extra activities ususally takes place in C#

A priority queue works like a charm

which input stream should i use for taking to take input

i tried nearly all sorting algorithm but it is always showing time out error

java programmer please help

All of the sorting algorithms you have tried so far are too slow; they run in O(n log n) time. You need something faster for this problem.

could a java programmer tell me whats the complexity of this and if its even a good idea. im a noob at this so if u think that the reason its timing out is obvious please excuse my eh.. noobness but i think that its a pretty fast algorithm

btw i made it using inspiration from binary sort

http://www.codechef.com/viewsolution/382377 thats my code

Unfortunately, while you may finding the position to insert the next element with a binary search in O(log n) time, you then have to move all of the elements after it forward one - and that is the part which takes all the time, as there could be n of them (n/2 on average). So the binary search ends up not actually being any more useful than searching the entire array in the first place, and your algorithm ends up with O(n^2) complexity.

There are many famous algorithms which sort numbers in O(n log n) time (try searching for some). That is the fastest complexity you can get for sorting numbers in general.

In this problem you need something even faster - use the fact that the numbers are all less than a million.

Please help me i am getting run time error

#include<stdio.h>
int main()
{
long int a[100000],t,c;
register int i,j;
scanf("%d",&t);
printf("n");
for(i=1;i<=t;i++)
scanf("%d",&a[i]);
for(i=1;i<t;i++)
{
for(j=1;j<t-i+1;j++)
{
if(a[j]>=a[j+1])
{
c=a[j];
a[j]=a[j+1];
a[j+1]=c;
}
}
}
printf("%dn",a[1]);
for(i=2;i<=t;i++)
{
if(a[i]==a[i-1])
continue;
printf("%dn",a[i]);
}
return 0;
}

in this case backslash is not printed but its there in the profram so dont worry about that

The problem statement says t can be up to 1000000. You don't allow anywhere near enough space for that.

@ stephen merriman Thank you however if i make my array size to 1000000 it times out why would that happen?? Could you please answer me

Because your algorithm is too slow.

No need to use arrays for this one.. I used vectors and built in sort algorithm function..easiest to understand

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <conio.h>

using namespace std;

int main(){
int t;
scanf("%d",&t);
int n;
vector<int> result;
while(t--){
scanf("%d",&n);
result.push_back(n);
}
sort(result.begin(),result.end());
for(int i=0;i<result.size();i++){
printf("%dn",result.at(i));
}
getch();
return 0;
}

 

PS : gave time limit exceeded when i used cin and cout..so had to replace them with printf and scanf

@ Stephen Merriman

Thank you i changed my algo and its working well now. One more question- when I write int a[1000000] is the space already alloted by the compiler or does it allot space only after initialisation?

@amogha: whenever an array is declared space is reserved for it

my submission id is 406216..

i am gettin runtime error.. WHY....????

my submission id is 410257

I have submitted a solution for this problem, which uses the pthreads library, and i am getting a linker error. also do i need to input the unordered set from standart input ? I am currently generating the numbers randomly and sorting them. Please suggest me how can i make a successful submission for this problem.

You aren't allowed to use threads in your solution.

You must use input from standard input and write output to standard output; read the FAQ.

thanks for the help, everything is clear now.

@Admin, I have solved this question in 2s and my solution is http://www.codechef.com/viewsolution/452897

There are solution on scoreboard which ran in 0.0s I checked solution of user 'gdkapil' (8th on scorboard) and his solution is exactly what I have done. Yet his time is 0.0s and mine 2s, what fact justifies that?

getting run time error on submission of my cod is..

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{    int i,n,a[100000];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);

for(i=0;i<n;i++)
cout<<a[i]<<"n";
return 0;
}
please any body help me

I get "wrong answer" but in my own test cases it works well. Why isn't possible to see test cases? Or just to know how many test i passed... :(

 

#include <stdio.h>

int v[1000001]={0};

int main()

{

int n,i,a;

scanf("%d",&n);

for (i=0;i<n; i++){ scanf("%d",&a); v[a]=1;  }

for (i=0;i<=1000000; i++) if (v[i]) printf("%dn",i);

return 0;

}

Ok, i did it.

I saw two "5"s in the input (and one in output) so i tought that numbers should be distinct...

Execution time: 2.19

Corrected code:

#include <stdio.h>

int v[1000001]={0};

int main()

{

int n,i,j,a;

scanf("%d",&n);

for (i=0;i<n; i++){ scanf("%d",&a); v[a]++; }

for (n=0;n<=1000000; n++) for (i=0;i<v[n];i++) printf("%dn",n);

return 0;

}

can anyone plz tell me wats wrong wid this code. i cant find wats the reason for getting runtime error.

I m really fade up.

plz help me.                                                                     
                                                                     
                                                                     
                                             
#include<stdio.h>
#include<stdlib.h>

int main()
{
   unsigned long  int t,i,temp,j;
    i=0;
    int *n=calloc(1000000,2);
    scanf("%ldn",&t);
    while(t--)
    {
      scanf("%ldn",&n[i]);
      i++;
    }  
    for(i=0;i<t;i++)
      {
         for(j=0;j<t;j++)
            { 
              if(n[i]<n[j])
              {
              temp=n[i];
              n[i]=n[j];
              n[j]=temp;
              }
            }
      }
  
  for(i=0;i<t;i++)
  printf("%ldn",n[i]);
return 0;//(scanf("%ld",&i));
}               

#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<alloc.h>

void main()

{

int *a,i,j,k,t;

printf("enter the number of linesn");

scanf("%d",&t);

a=(int *)malloc(pow(10,6));

if(t<=pow(10,6))

{

for(j=0;j<t;j++)

{

scanf("%d",&a[j]);

if(a[j]<0 && a[j]>pow(10,6))

break;

}

}

for(i=0;i<t;i++)

{

for(j=i+1;j<t;j++)

{

if(a[i]>a[j])

{

k=a[i];

a[i]=a[j];

a[j]=k;

}

}

}

for(i=0;i<t;i++)

printf("%dn",a[i]);

getch();

}

The Server Test Time Meausrement is not precisely. It depend on server's load.

This times out in java any suggestions i am using counting sort :(

i dont know why is this happening but a counting sort in java doesnt work but the internal implementation of qsort in C works .........
admin any guesses..........

import java.util.Scanner;

public class Main {
public static void main(String args[]) {
int i = 0;
int arr[] = new int[1000000];
Scanner in = new Scanner(System.in);
Integer x = new Integer(in.nextLine());
for (i = 0; i < x; i++) {
Integer num=new Integer(in.nextLine());
arr[num]++;
}
int size=0;
for(i=0;i<1000000;i++)
{
int count=arr[i];
if(count==0)
continue;
for(int j=0;j<count;j++)
{
System.out.println(i);
}
size=size+count;
if(size==arr.length)
break;
}
}

Code for counting sort

Simple, slow, yet AC solution in java:

array = new int[Integer.parseInt( br.readLine()    )];
for(int i = 0; i < array.length; ++i){
array[i] = Integer.parseInt( br.readLine() );
}
java.util.Arrays.sort(array);
for(int i: array){
sb.append(i); // sb = stringbuffer
sb.append('n');
}
System.out.println(sb.toString());

Quote from Java API about the sorting algorithm used:

Sorts the specified array of ints into ascending numerical order. [...]  This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int n,i;

int a[1000000];
scanf("%d",&n);
for(i=0; i<n; i++)

scanf("%d",a+i);

sort(a,a+n);

for(i=0; i<n; i++)
printf("%dn",a[i]);
return 0;
}


Though i am able to submit the correct answer the following program doesnot work in DEV C++.. Why?

coz the max size of array depends upon the system architecture.your system doesnt have capacity to allocates memory for 10^6  integers ,while the codechef judge (system) has

thnks bro

i am using Dev-cpp. the program is running fine in it but is showing runtime error here...plaease help

@ anul _lundia::your program can never work fine on dev c++..bcoz u cant allocate int n[100000] in dev cpp.It will immidiately encounter stack overflow.Also the algo bubble sort u used wont wrk here coz the timelimit is only 5 sec.Try some other sorting algorith or usie c++ stl #include <algorithm>

can anyone please help... whats wrong with my algo here : its a perl program for quick-sort. O/P is wrong sample i/p: 6 3 8 1 6 5 4 o/p: 1 1 4 4 4 4 #!/usr/bin/perl my $t=STDIN; #not using > and < signs around stdin as then there is posting problem int($t); my @n; while($t) { push(@n,int(STDIN)); $t--; } &quick(0,$#n); sub quick { if($_[0]<$_[1]) { my $pivot = $n[$_[1]]; my $from = $_[0]; my $to = $_[1]; my $i=$from-1; my $j=$from; my $temp; while($j<$to) { if($n[$j]<=$pivot) { $i=$i+1; $temp=$n[$i]; $n[$i]=$n[$j]; $n[$j]=$temp; } $j=$j+1; } $i=$i+1; $temp=$n[$i]; $n[$i]=$pivot; $pivot=$n[$i]; &quick($from,$i-1); &quick($i+1,$to); } } foreach(@n) { print $_."n"; }

Don't just look at the word "sort" and think of a well-known sorting algorithm. Yes, quicksort is fast but it is O(nlogn). There is an O(n) solution.

my program not providing any output ..plz any 1 help import java.util.Scanner; import java.util.Arrays; public class main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int arrayvalue= scan.nextInt(); if (arrayvalue<=1000001) { int[] el=new int[arrayvalue]; for (int elements=0; elements<=el.length; elements++) { int num=scan.nextInt(); // System.out.println(num); if (num>=0 && num<=1000001) { el[elements]=num; } } Arrays.sort(el);//method for sorting an array for (int i = 0; i < el.length; i++) { System.out.println(el[i]); } } } }

Why the solution is not getting accepted in JAVA? Here's my solution: http://www.codechef.com/viewsolution/575251 It is showing TLE every time. In my P4 2.8 ghz it takes 1.5 seconds approx. for10^6 elements. Admin plz take note...

@arnab_das: Quick Sort is very inefficient for this problem. It's average running time is O(N log N) which will time out. Use an algorithm with a better running time. Hint: Look at the constraints carefully.

but when I converted the same program to run in C, it was accepted. see: http://www.codechef.com/viewsolution/575333

Maybe its because IO is much slower in Java as compared to C/C++.

hi admin and all other, my programme in c got TLE....shud it mean that it is showing correct output but not compiling within time????mean can i be sure about the correctness of my programme??

what is runtime error code SIGSEGV????help me out please

@hundrycoder: TLE means your program was compiled but failed to complete its execution within the time limit. The judge cannot decide whether it is right or wrong because your program did not finish its execution. SIGSEGV is for invalid memory reference or segmentation fault. Look it up in wikipedia. Most commonly it is because the program tried to access an array element outside the array bounds.

@balajiganapath thanks

using System; using System.Diagnostics; namespace Turbo_Sort { class Program { static void Main( string[] args ) { int limit, i=0; limit = int.Parse(Console.ReadLine()); int[] arr = new int[limit]; Stopwatch stopwatch = new Stopwatch(); for(i=0;i

using System; using System.Diagnostics; namespace Turbo_Sort { class Program { static void Main( string[] args ) { int limit, i=0; limit = int.Parse(Console.ReadLine()); int[] arr = new int[limit]; Stopwatch stopwatch = new Stopwatch(); for(i=0;i

Looks like code written in Python always times out :(

I have submitted the following code, its working fine when i tested on my pc but the online judge is throwing "wrong answer" message. Can anyone kindly point the mistake. Thanks in advance... ============== #include #define RANGE 1000001 int main() { int index,i,tot,cnt; short int arr[RANGE]; for(i=0;i

Hey could anyone solve it with quicksort...or even randomized version of it...???

Why the people are trying to solve this problem with sort algorithm? It's not the best way to solve this problem.

//why time limit exceed? #include #include int main() { int *p; p=(int*)malloc(1000001*sizeof(int)); int i,j,k,n,temp; scanf("%d",&n); for(k=0;kp[j]) { temp=p[i]; p[i]=p[j]; p[j]=temp; } } for(i=0;i

#include int main() { int i,j=0,temp,a[20],t; scanf("n%d",&t); for(i=0;ia[j]){ temp=a[j]; a[j]=a[i]; a[i]=temp; } } } for(i=0;i

#include int main() { int i,j=0,temp,a[20],t; scanf("n%d",&t); for(i=0;ia[j]){ temp=a[j]; a[j]=a[i]; a[i]=temp; } } } for(i=0;i

This problem is somehow so strange. I submitted my application in Java and it returned me with Wrong Answer. I then convert my Java code to C, and it returned me with Accepted. Hhmm... Don't know where the wrong part is.... If any of you can find anything wrong, either with my code, or having similar experience, please do let me know. Below are the links for my source code. The first one using java, and the second one using C. Source in Java: http://www.codechef.com/viewsolution/633234 Source in C: http://www.codechef.com/viewsolution/633268

@admin //this program is working well (it shows the bugs in your system) #include int main(void) { int T,i=0,arr[1000000]={0},x; scanf("%d",&T); for(;i

my program is working correctly in with my compiler. can ny1 plz tell why is it showing WRONG ANSWER here... #include /*TSORT*/ int main() { int t,i,x,min,max; char c[1000002]; scanf("%d",&t); for(i=0;i<=1000000;i++) c[i]='0'; scanf("%d",&x);c[x]='1'; min=max=x; for(i=2;i<=t;i++) { scanf("%d",&x); c[x]=c[x]+1; if(xmax) max=x; } for(i=min;i<=max;i++) { if(c[i]!='0') { x=c[i]-'0'; while(x>0) {printf("%dn",i);--x;} } } return 0; }

can any1 plz tell me why is it showing WRONG RESULT for the solution no:644717 though its is working correctly with my compiler

672171 Why runtime error?? plz help

anyone tell me wots wrong?? It is giving runtime error?? namespace TurboSort { class Program { static void Main(string[] args) { int temp; int t = System.Convert.ToInt32(System.Console.ReadLine()); int[] n = new int[t]; for(temp=0;temp

namespace TurboSort { class Program { static void Main(string[] args) { int temp; int t = System.Convert.ToInt32(System.Console.ReadLine()); int[] n = new int[t]; for(temp=0;temp

plz help me.i used quicksort.here i post my solution link. http://www.codechef.com/viewsolution/678694

My absolutely primitive solution passes every test in Java

Talk about lucky solved in 4.99 seconds

Plz anyone tell me wats wrong.... it's giving fine results with all test cases i tried on Dev C++ Here's my code:: #include #include #include int compare(const void *a,const void *b) { return(*(int*)a-*(int*)b); } int main() { int t,i,j,temp,z;t=i=j=temp=0;z=pow(10,6)+1; scanf("%d",&t);int a[t];int b[t]; for(i=0;i

it gives me a runtime error with d usage of 1.9M but it accepts code with mem usage upto 100M....

@garv24: 0<=N<=10^6

On my computer if I run the program as time ./a.out < input > abc real 0m0.626s user 0m0.604s sys 0m0.016s The time limits are very well satisfied, but I still get the time limit exceeded error, I can't understand why?

Can someone comment on what's wrong with http://www.codechef.com/viewsolution/728169 ? it seems to pass my test. It would also be useful to know what the inputs are to the test when there is a runtime error. thanks,

I have written the program in python but it is showing error. Can you please help me? Following is the code: 1. #!/usr/bin/python 2. L= [] 3. count = 0 4. while (count < 9): 5. var = input("Enter something: ") 6. L.append(var) 7. count = count + 1 8. L.sort() 9. for x in L: # Second Example 10. print x 11.

can someone comment on my above code in python ?

sigh.. Runtime error got me really pissed off........

It got you pissed off? Man that made me want to pull off all my hair

my heapsort code works well in my machine but unfortunately codechef shows run-time error.... help plz

i solved the problem with quick sort. But it is showing time limit. May i know wat might be the reason