It's too hard to slove it in pascal
Послано
鳳の無望 30 мар 2004 11:13
the easiest way is save the 3/4 of the number.
but it's almost impossible in pascal.
Re: It's too hard to slove it in pascal
hm.. there is an O(N) algo for the problem, what else d'you need?
and what means - save the 3/4 of the number? and why is it impossible in pascal?
Re: It's too hard to slove it in pascal
Perhaps he wanted to save first 3N/4 numbers, sort them & then insert rest numbers into the list. But i think it will get TLE. But how can it be solved in O(n) ?
Re: It's too hard to slove it in pascal
I used to be puzzled about the memory either, and think it's a bit unfair for pascal. But I suggest the only thing we can do is to use the memory as less as possible. Since you can save 3/4 of the number to solve it, then what about 2/3 or 7/12 and so. The mothed is similar to yours and just do it more times.
Re: It's too hard to slove it in pascal
Послано
鳳の無望 31 мар 2004 10:21
It's won't be TLE if you use quick sort.
Re: It's too hard to slove it in pascal
Послано
鳳の無望 31 мар 2004 10:23
Someone else said this program can be sloved by saving n/2 numbers,use heap.
Re: It's too hard to slove it in pascal
There is an easy solution win n/2 memory and O(n*log(n)) time. But i don't know how to solve it with QSort or some algorithm with O(n) time without using n memory, please tell me how...
Re: It's too hard to slove it in pascal
hmmm the O(N) algo really needs too much memory.. sorry
Edited by author 01.04.2004 18:55
Re: It's too hard to slove it in pascal
Послано
buggzy 2 апр 2004 11:05
> there is an O(N) algo for the problem, what else d'you need?
I got TLE on O(N) algorithm ;) (input is parsed 32 times to calculate median bit-by-bit). Oh, my marasmatic brain not generated better solution yet...
