Discussion @ 1105. Observers Coloring @ Timus Online Judge

Is it possible to solve this problem without sorting?

Posted by shitty.Mishka 15 Nov 2001 02:10

I'm sure that my algorythm is correct. It's complexity is O
(n log n), because I use quicksort, and then 2 linear
procedures. Why do I get TimeLimitExceed? Is it possible
not to use sorting?

Re: Is it possible to solve this problem without sorting?

Posted by I have answers to all your questions :) 15 Nov 2001 12:27

> I'm sure that my algorythm is correct. It's complexity is
O
> (n log n), because I use quicksort, and then 2 linear
> procedures. Why do I get TimeLimitExceed? Is it possible
> not to use sorting?

because complexity of quicksort in worst case is O(n^2)
use heapsort or mergesort and ur program 'll get accepted (
or at least not TimeLimitExceeded ) ;)

Thank you very much! I used Merge Sort and I've just got and accepted. I appreciate your help a lot :)

Posted by shitty.Mishka 16 Nov 2001 00:31

Who said that qsort is an O(n^2) algorithm?I got accepted in 0.06sec using qsort.

Posted by Huang Yizheng 17 Jan 2002 05:35

Re: Is it possible to solve this problem without sorting?

Posted by liuchang 11 Jun 2004 17:58

Just use Random-Quick-Sort it'll take a little time to run it.

Re: Is it possible to solve this problem without sorting?

Posted by KING_OF_AZE 14 Feb 2007 19:52

you can use the quick sort in short algorithim

Re: Is it possible to solve this problem without sorting?

Posted by Fly [Yaroslavl_SU] 5 Apr 2007 00:14

Still AC with O(N^2). ::)
But sorting i use.

Re: Is it possible to solve this problem without sorting?

Posted by Alias (Alexander Prudaev) 5 Apr 2007 08:52

do as this
#include <algorithm>
using namespace std;

int a[n];
sort(a,a+n);

Discussion of Problem 1105. Observers Coloring