10107 - What is the Median?

[Joseph Kurniawan]

Determine the input's position in the array once there's a new input.
Example:
input = 1 23 4 5 7 11
Array condition:
1. 1
2. 1 23
3. 1 4 23
4. 1 4 5 23
5. 1 4 5 7 23
6. 1 4 5 7 11 23
Try using linked list to improve the speed.

[Jewel of DIU]

My AC programm get TLE after rejudge .
I take the one input & then use qsort() and find median.
Is there any efficient way for solving this problem?

[shamim]

One way to do it is to use the fact that the inputs are already sorted and you could insert the new element at the right position.

[Jewel of DIU]

I have got AC in 0.246 sec using this method.Thanks.

[Nono]

I use O(lgn) algorithm to find the median in n numbers.
And permit the algorithm once on each input number(with preceding sequence)
But it takes about 1.3 seconds

Please tell me how to do it below 1 second... thx

[sohel]

My AC program took 0.021 seconds.

I maintained two heaps ( max and min ).
For Finding the median mine took O(1) time.
For insertion of each element it took appx. log n time.

[lovemagic]

I got TLE several times.
Here is my code.
#include <stdio.h>
#include <stdlib.h>

long input[10050];

int sort(const void *a,const void *b){
long p =*(long *)a,q =*(long *)b;
return p-q;
}

void main(){
long i=0;
while(scanf("%ld",&input)!=EOF){
i++;
qsort(input,i,sizeof(long),sort);
if(i%2==0)
printf("%ld\n",(input[i/2-1]+input[i/2])/2);
else
printf("%ld\n",input[(i-1)/2]);
}
}

[Ghust_omega]

Hi lovemagic the qsort takes so long in this prob because for each new input you call qsort try to think in other way to do it
Hope it Helps
Keep posting !!

[sohel]

You can use insertion sort to get rid of the TLE.
This problem can be solved more efficiently by using two heaps (one max heap and one min heap, to be more precise).

[lovemagic]

I tried with leaner search but also TLE.
Do u tell me how i use min-max heap here.

Here is my code----

#include <stdio.h>
int i;
int input[10050];

int sort(){
int i1,i2,tmp;
for(i1=0;i1<i-1;i1++)
for(i2=i1+1;i2<i;i2++)
if(input[i1]>input[i2]){
tmp=input[i1];
input[i1]=input[i2];
input[i2]=tmp;
}
}

void main(){
while(scanf("%d",&input)!=EOF){
i++;
sort();
if(i%2==0)
printf("%d\n",(input[i/2-1]+input[i/2])/2);
else
printf("%d\n",input[(i-1)/2]);
}
}

[lovemagic]

I tried with leaner search but also TLE.
Do u tell me how i use min-max heap here.

Here is my code----

#include <stdio.h>
int i;
int input[10050];

int sort(){
int i1,i2,tmp;
for(i1=0;i1<i-1;i1++)
for(i2=i1+1;i2<i;i2++)
if(input[i1]>input[i2]){
tmp=input[i1];
input[i1]=input[i2];
input[i2]=tmp;
}
}

void main(){
while(scanf("%d",&input)!=EOF){
i++;
sort();
if(i%2==0)
printf("%d\n",(input[i/2-1]+input[i/2])/2);
else
printf("%d\n",input[(i-1)/2]);
}
}

[GeorgeBusch]

Also, I usually use readln instead of read but I don't understand why this makes WA! I thought they should work similar in this kind of problem.

The problem with using read is, that you dont skip the newline at the end of line. So it doesnt matter while you are somewhere in the input, but when you arrive at last integer and read it, you dont skip the newline and so the EoF() statement gives true and you try to read another number. Since there is no number left you will get a runtime error, but the judge cant always differ between RTE and WA, cause the pascal program writes 'Error ...' to output. If you test your program with file input you can see this.
I usually use it like this:

while not (EoF()) do
if not (EoLn()) do
begin
read(x)
...
end
else readln(s);

where s is a string. so you skip the newlines, but it s a little bit slower. And the pro is that you can read more than one integer in one line.

[Pier]

It's wierd to get an answer after almost two years! Anyway, very good answer. Thanks!

PS: I think you can change your readln(s) for only readln and it would still work (and you wouldn't need the string).

[Salman]

Getting TLE from this course.


code is removed after got AC

[mohiul alam prince]

HI Salman
use insertion sort. Hope this will help you.

Thanks
MAP