Обсуждение @ 1510. Порядок @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

There is algo in O(n). Try to find it ;) (-) Tbilisi SU: Andrew Lutsenko 30 окт 2006 14:28

Re: There is algo in O(n). Try to find it ;) (-) Alexander Prudaev 30 окт 2006 16:38

more exactly O(N*log(K))

Re: There is algo in O(n). Try to find it ;) (-) Tbilisi SU: Andrew Lutsenko 30 окт 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?

Re: There is algo in O(n). Try to find it ;) (-) Nechaev Ilya (Rybinsk SAAT) 30 окт 2006 20:02

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.

qsort is O(N*log(N)) (-) Vladimir Yakovlev (USU) 30 окт 2006 23:11

Re: There is algo in O(n). Try to find it ;) (-) Rooslan S. Khayrov 30 окт 2006 23:17

Nechaev Ilya (Rybinsk SAAT) писал(a) 30 октября 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.

Re: There is algo in O(n). Try to find it ;) (-) Midnight_Kitty 30 окт 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

Re: There is algo in O(n). Try to find it ;) (-) Alexander Sokolov [MAI] 31 окт 2006 23:05

My solution uses random function and got AC! lol

Re: There is algo in O(n). Try to find it ;) (-) Nechaev Ilya (Rybinsk SAAT) 1 ноя 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 =)

Re: There is algo in O(n). Try to find it ;) (-) Nechaev Ilya (Rybinsk SAAT) 4 ноя 2006 03:42

0.046 =P

Re: There is algo in O(n). Try to find it ;) (-) Magician 8 мар 2007 17:50

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 ;) (-) UdSU: Ajtkulov, Kotegov, Saitov 2 ноя 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

Re: There is algo in O(n). Try to find it ;) (-) Denis Koshman 13 июл 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

Re: There is algo in O(n). Try to find it ;) (-) djosacv 18 ноя 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 :)

Re: There is algo in O(n). Try to find it ;) (-) Vedernikoff Sergey (HSE: EconomicsForever!) 18 ноя 2008 16:02

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 ;) (-) PrankMaN 1 сен 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?

Re: There is algo in O(n). Try to find it ;) (-) Nenad Popovic 9 сен 2011 23:05

Thank you for this great suggestion!

Re: There is algo in O(n). Try to find it ;) (-) ACSpeed 24 ноя 2011 20:09

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 ;) (-) amirani 17 янв 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

Re: There is algo in O(n). Try to find it ;) (-) Bogatyr 22 ноя 2012 04:55

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

Обсуждение задачи 1510. Порядок