10107 - What is the Median?

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Thu Oct 23, 2003 7:28 am

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
Location: Daffodil Univ, Bangladesh
Contact:

10107: TLE after rejudge :(

Post by Jewel of DIU » Sun Nov 02, 2003 7:13 am

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!

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Nov 02, 2003 9:10 am

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
Location: Daffodil Univ, Bangladesh
Contact:

Post by Jewel of DIU » Sun Nov 02, 2003 12:34 pm

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

Post by Nono » Mon Feb 09, 2004 12:12 pm

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Feb 09, 2004 12:39 pm

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

Post by lovemagic » Mon Oct 11, 2004 9:16 pm

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

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Tue Oct 12, 2004 3:12 am

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 !! :D

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Oct 12, 2004 9:26 am

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

Post by lovemagic » Tue Oct 12, 2004 9:31 pm

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

Post by lovemagic » Tue Oct 12, 2004 9:32 pm

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

Post by GeorgeBusch » Mon Jun 13, 2005 1:51 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
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.

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Thanks!

Post by Pier » Mon Jun 13, 2005 3:08 pm

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

Post by Salman » Wed Aug 24, 2005 9:43 am

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.

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

Post by mohiul alam prince » Wed Aug 24, 2005 11:41 am

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

Thanks
MAP

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest