Discussion @ 1510. Order @ Timus Online Judge

Tbilisi SU: Andrew Lutsenko There is algo in O(n). Try to find it ;) (-) [20] // Problem 1510. Order 30 Oct 2006 14:28

Alexander Prudaev Re: There is algo in O(n). Try to find it ;) (-) [10] // Problem 1510. Order 30 Oct 2006 16:38

more exactly O(N*log(K))

Tbilisi SU: Andrew Lutsenko Re: There is algo in O(n). Try to find it ;) (-) [9] // Problem 1510. Order 30 Oct 2006 18:04

My algo is exactly O(n). Constant is 1. Just reading input, sometimes even not the whole input.
What is K in your formula?

Nechaev Ilya (Rybinsk SAAT) Re: There is algo in O(n). Try to find it ;) (-) [8] // Problem 1510. Order 30 Oct 2006 20:02

I have O(N) solution, AC (0.156). I use "bucketing".
But there is solution that works two times faster :(

svr Re: There is algo in O(n). Try to find it ;) (-) [1] // Problem 1510. Order 30 Oct 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.

Vladimir Yakovlev (USU) qsort is O(N*log(N)) (-) // Problem 1510. Order 30 Oct 2006 23:11

Rooslan S. Khayrov Re: There is algo in O(n). Try to find it ;) (-) [5] // Problem 1510. Order 30 Oct 2006 23:17

Nechaev Ilya (Rybinsk SAAT) wrote 30 October 2006 20:02

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.

Midnight_Kitty Re: There is algo in O(n). Try to find it ;) (-) [4] // Problem 1510. Order 30 Oct 2006 23:35

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

Alexander Sokolov [MAI] Re: There is algo in O(n). Try to find it ;) (-) [1] // Problem 1510. Order 31 Oct 2006 23:05

My solution uses random function and got AC! lol

Nechaev Ilya (Rybinsk SAAT) Re: There is algo in O(n). Try to find it ;) (-) // Problem 1510. Order 1 Nov 2006 17:23

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 =)

Nechaev Ilya (Rybinsk SAAT) Re: There is algo in O(n). Try to find it ;) (-) [1] // Problem 1510. Order 4 Nov 2006 03:42

0.046 =P

Magician Re: There is algo in O(n). Try to find it ;) (-) // Problem 1510. Order 8 Mar 2007 17:50

My program have AC(0.046) too. But I use only 96kB memory:-)

Edited by author 08.03.2007 17:51

UdSU: Ajtkulov, Kotegov, Saitov Re: There is algo in O(n). Try to find it ;) (-) // Problem 1510. Order 2 Nov 2006 22:16

Bayan.
http://algolist.manual.ru/olimp/poi_prb.php
Problem 15.
http://algolist.manual.ru/olimp/poi_sol.php#a15

Edited by author 02.11.2006 22:18

Denis Koshman Re: There is algo in O(n). Try to find it ;) (-) [7] // Problem 1510. Order 13 Jul 2008 20:41

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

djosacv Re: There is algo in O(n). Try to find it ;) (-) [6] // Problem 1510. Order 18 Nov 2008 11:43

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 :)

Vedernikoff Sergey (HSE: EconomicsForever!) Re: There is algo in O(n). Try to find it ;) (-) [1] // Problem 1510. Order 18 Nov 2008 16:02

One more O(N) algo is K-th ordered statistics, which is explained in Kormen et. al.

PrankMaN Re: There is algo in O(n). Try to find it ;) (-) // Problem 1510. Order 1 Sep 2011 02:21

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?

Nenad Popovic Re: There is algo in O(n). Try to find it ;) (-) [3] // Problem 1510. Order 9 Sep 2011 23:05

Thank you for this great suggestion!

ACSpeed Re: There is algo in O(n). Try to find it ;) (-) [2] // Problem 1510. Order 24 Nov 2011 20:09

How did you guys optimize I/O ? Can send me your I/O procedure, my email : tungnk1993@gmail.com

amirani Re: There is algo in O(n). Try to find it ;) (-) [1] // Problem 1510. Order 17 Jan 2012 14:40

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

Bogatyr Re: There is algo in O(n). Try to find it ;) (-) // Problem 1510. Order 22 Nov 2012 04:55

Boyer-Moore is one of those "brilliant in its simplicity" types of algorithms. Beautiful!

Discussion of Problem 1510. Order