## 10107 - What is the Median?

Moderator: Board moderators

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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.
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Contact:

### 10107: TLE after rejudge :(

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?
Hate WA
Visit phpBB!

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Contact:
I have got AC in 0.246 sec using this method.Thanks.
Hate WA
Visit phpBB!

Nono
New poster
Posts: 3
Joined: Wed Oct 08, 2003 7:34 am

### 10107 What is the Median? - Algorithm Problem

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

### 10107-TLE plz help

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]);
}
}
khobaib

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am
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]);
}
}
khobaib

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am
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]);
}
}
khobaib

GeorgeBusch
New poster
Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm
Pier wrote: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
...
end

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
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

### Thanks!

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).
There are 10 kind of people on this world: those who understand binary and those who don't!

Salman
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

### 10107

Getting TLE from this course.

code is removed after got AC
Last edited by Salman on Thu Sep 01, 2005 11:27 am, edited 1 time in total.

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
HI Salman