There is algo in O(n). Try to find it ;) (-)
Re: There is algo in O(n). Try to find it ;) (-)
more exactly O(N*log(K))
Re: There is algo in O(n). Try to find it ;) (-)
My algo is exactly O(n). Constant is 1. Just reading input, sometimes even not the whole input.
What is K in your formula?
Re: There is algo in O(n). Try to find it ;) (-)
I have O(N) solution, AC (0.156). I use "bucketing".
But there is solution that works two times faster :(
Re: There is algo in O(n). Try to find it ;) (-)
Послано
svr 30 окт 2006 22:31
I think for this problem O(n) algorithms as many as stars in the sky. For example
1) qsort;
2) moving along and counting copies of equal values.
Re: There is algo in O(n). Try to find it ;) (-)
I have O(N) solution, AC (0.156). I use "bucketing".
But there is solution that works two times faster :(
In this problem I/O hacks gave me much more speedup than algorithmic issues.
My 0.078s solution uses the same linear time, constant memory algorithm as the 0.546s one.
Re: There is algo in O(n). Try to find it ;) (-)
0.062 :P
just use your own procedure for reading numbers instead of fscanf. It must read numbers char-by-char
Edited by author 31.10.2006 02:17
Re: There is algo in O(n). Try to find it ;) (-)
My solution uses random function and got AC! lol
Re: There is algo in O(n). Try to find it ;) (-)
Hehe. I think there are no tests like this:
11
1 2 1 2 1 2 1 2 1 2 1
or you are very lucky =)
Re: There is algo in O(n). Try to find it ;) (-)
Re: There is algo in O(n). Try to find it ;) (-)
0.046 =P
Re: There is algo in O(n). Try to find it ;) (-)
My program have AC(0.046) too. But I use only 96kB memory:-)
Edited by author 08.03.2007 17:51
Re: There is algo in O(n). Try to find it ;) (-)
Bucketing assumes that we keep an array as big as the value range, which is one billion in this problem.
So I suppose you talk about per-digit bucketing, but it is still O(N*log(K)) if we treat input numbers regardless of their base-10 representation. Did you get that constant because of limited length of particular number, given limit on its value?
Just telling that it is O(N) just becase representation is fixed to base-10 is not quite far from telling that it is O(1) becase N itself is limited by 500'000 - a constant :)
Edited by author 13.07.2008 20:45
Edited by author 13.07.2008 20:45
Re: There is algo in O(n). Try to find it ;) (-)
The O(n) algorithm is Boyer-Moore Majority Vote Algorithm, which time is linear, and memory constant... in fact you don't need more than 3 integer variables to run this algorithm... As some people have mentioned, writing your own int input procedure may improve your performance a lot. First time with no optimization i got 1.06s, then i used a getc() based int input procedure and did some little changes in the code and got 0.046s :)
Re: There is algo in O(n). Try to find it ;) (-)
One more O(N) algo is K-th ordered statistics, which is explained in Kormen et. al.
Re: There is algo in O(n). Try to find it ;) (-)
So, will program, which reads number and increases the variable, which counts how many times did we meet that number get AC, but not TLE?
Re: There is algo in O(n). Try to find it ;) (-)
Thank you for this great suggestion!
Re: There is algo in O(n). Try to find it ;) (-)
How did you guys optimize I/O ? Can send me your I/O procedure, my email : tungnk1993@gmail.com
Re: There is algo in O(n). Try to find it ;) (-)
i tryed many different ways but always got tle on 19 or 20 tests .Than i saw Boyer-Moore Majority Vote Algorithm.it's really good algo for this problem .Here is algo
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html. here is'n written than number of majority element must be more than half so i thought that it would write right answer in any case for example in that case B B B B A A A A A C C C but no .in that algo it's very important the number of majority element to be more than (n/2)
thanks .
Sorry for bad English.
Edited by author 17.01.2012 14:52