ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1126. Magnetic Storms

O(n*log(n)) solution in 0.328 seconds and new type of sorting!
Posted by Pasha 30 Jun 2004 21:07
Yes, this solution is very slow, but during solving this problem new type of sorting was invented, which sorts any massive in O(n*log(n)) time and doesn't require additional memory!
Are you kidding? :) New type of sorting? :) (+)
Posted by Dmitry 'Diman_YES' Kovalioff 30 Jun 2004 23:02
I think you should first read "The art of computer programming" by Donald E. Knuth (especially, Volume 3 "Sorting and Searching") and "Introduction to Algorithms", the MIT Press...
If you are not kidding,can you send your soure to yym2008@hotmail.com?
Posted by Yu YuanMing 7 Jul 2004 09:30
Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting!
Posted by Sandro 10 Aug 2004 10:43
Why is your solution so slow? My program works O(N*log(N)) too (using Qsort) but in 0.046 sec.
Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting!
Posted by BYF 4 Sep 2004 20:28
There are lots of sorts of sorting methods can do this(nlogn at any time) and faster than you.
Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting!
Posted by Korduban [Kiev] 4 Sep 2004 22:27
Please, send me your code - dkorduban[at]ukr.net
No subject
Posted by SSAU_618#1 25 Mar 2005 19:18


Edited by author 25.03.2005 19:49
Re: O(n*log(n)) solution in 0.328 seconds and new type of sorting!
Posted by Pasha 25 Mar 2005 19:18
I am giving my apologizing because I accidentally mislead everybody. I used silly Binary Search method to solve this problem. I've written the first lines because I contrived
this method myself during solving this problem, so I was
very pleased and wrote the strings at the beginning in the
heat of the solvation of the problems.

To <Dmitry 'Diman_YES' Kovalioff>: I've did't expect that
books of so kind even exists at that time, not mentioned
that I read one of them. You've opened my eyes. Thank You
very much for this.
To everyone who wants see my code (Pascal):
{In reading we trying to place the last read element into
 the massive of the last M read elements in the proper place
 following the value of it. So the last element in this
 massive will be the greatest - we write this element to the
 ouput.}
const
 lenmax=100000;
 upbone=100000;
var
 elkol: array [0..upbone] of word;
 elems, elist: array [1..lenmax] of longint;
 curno, curelem, m, els, elpos: longint;
 already_in_list: boolean;
function BinSearch(bsx: longint): longint;
var
 bsp, bsq, bsi: longint;
begin
 bsp:=1;  { Left border of the search  }
 bsq:=els;  { Right border of the search }
  while bsp <= bsq do
   begin
    bsi:=(bsp + bsq) div 2;
     if elist[bsi] = bsx then
      begin
       BinSearch := bsi;
       already_in_list:=true;
       exit
      end;
     if bsx < elist[bsi] then
       bsq := bsi - 1
     else
       bsp := bsi + 1
   end;
  if bsx>elist[bsq] then
    BinSearch:=bsp
  else
    BinSearch:=bsq;
 already_in_list:=false
end;
procedure ins_new_item;
begin
  if curelem<elist[1] then
   begin
    move(elist[1], elist[2], els*4);
    elist[1]:=curelem;
    inc(els)
   end
  else
     if curelem>elist[els] then
      begin
       inc(els);
       elist[els]:=curelem;
      end
     else
      begin
       elpos:=binsearch(curelem);
        if not already_in_list then
         begin
          move(elist[elpos], elist[elpos+1], (els-elpos+1)*4);
          elist[elpos]:=curelem;
          inc(els)
         end
      end
end;
begin
 fillchar(elkol, sizeof(elkol), 0);
 readln(m);
 readln(curelem);
  if curelem=-1 then
    exit;
 elist[1]:=curelem;
 els:=1;
 curno:=0;
  while (curno<m) and (curelem<>-1) do
   begin
    inc(curno);
    elems[curno]:=curelem;
    inc(elkol[curelem]);
     if curno>1 then
       ins_new_item;
    readln(curelem)
   end;
{First M or less elements are being read}
 writeln(elist[els]);
  if curelem=-1 then
    exit;
{If not end of sequence, reading until curelem=-1
 (condition of the end of the sequence)}
  while curelem<>-1 do
   begin
    inc(curno);
    elems[curno]:=curelem;
    inc(elkol[curelem]);
    ins_new_item;
    dec(elkol[elems[curno-m]]);
     if elkol[elems[curno-m]]=0 then
      begin
       elpos:=binsearch(elems[curno-m]);
       move(elist[elpos+1], elist[elpos], (els-elpos)*4);
       dec(els)
      end;
    writeln(elist[els]);
    readln(curelem)
   end
end.