Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Нет компиляторов разрешонных языков, но мой вариант на C#:
/// Псеводсортировка
int[] M = new int[10000];
for (int i = 0; i < N; i++) M[N_array[i]]++; // Инициализируем, как второй вариант
int ii = 1;
for (int i = 0; i < M.Length; i++) // Устанавливаем в M[element] порядковый номер этого элемента, либо 0 если его нет
if (M[i] > 0)
{
int j = M[i];
M[i] = ii;
ii += j;
}
///Анализ
Console.WriteLine("Case# 1:");
for (int i = 0; i < Q; i++)
{
int n = M[Q_array[i]];
if (n == 0)
Console.WriteLine("{0} not found", Q_array[i]);
else
Console.WriteLine("{0} found at {1}", Q_array[i], n);
}
Console.ReadLine();
Для скорости можно в цикле for (int i = 0; i < N; i++) искать max, а цикл for (int i = 0; i < M.Length; i++) заменить на for (int i = 0; i < max; i++)
Я рад, что вы так быстро пришли к выводу, что с нашими граничными условиями на числа, можно обойтись не только без сортировки, но и без поиска. Но спешу вас огорчить: я проверял такой подход, он медленнее, чем первый вариант. Мою реализацию вашего подхода на C++ можно скачать тут и проверить. Accepted (0.488)
Предполагаю, что такой подход дает бешеный прирост производительности в случаях, когда у нас много разных чисел от 1 до 10000, но когда чисел мало, а разброс между ними большой (например два числа: 1 и 10000) и Q стремится к максимуму, то все преимущества сразу пропадают, потому что независимо от количества разных чисел нам все равно приходится работать с массивом в 10000 элементов.
Предполагаю, что такой подход дает бешеный прирост производительности в случаях, когда у нас много разных чисел от 1 до 10000, но когда чисел мало, а разброс между ними большой (например два числа: 1 и 10000) и Q стремится к максимуму, то все преимущества сразу пропадают, потому что независимо от количества разных чисел нам все равно приходится работать с массивом в 10000 элементов.
Просто нужно владеть инструментом: pastebin.com/Rhr7Uswk (этот же алгоритм, но правильно написанный на C): Accepted (0.108)
Ошибки, приводящие к значительному падению быстродействия:
Если же говорить о теории, то самый быстрый из возможных алгоритмов — отсортировать оба списка: и самих элементов, и и запрашиваемых. А затем использовать бинарный поиск в массиве M, каждый раз отталкиваясь от предыдущего найденного элемента.
Ошибки, приводящие к значительному падению быстродействия:
- использование iostream
- динамичсекое выделение памяти
- «плохие» типы данных (работа с 16-битными целыми медленнее, чем с 32-битным в 32-битном и 64-битном режимах)
Если же говорить о теории, то самый быстрый из возможных алгоритмов — отсортировать оба списка: и самих элементов, и и запрашиваемых. А затем использовать бинарный поиск в массиве M, каждый раз отталкиваясь от предыдущего найденного элемента.
Сомневаюсь, что быстрая сортировка и бинпоиск с асимптотикой O(n log n) могут быть быстрее сортировки подсчетом с асимптотикой O(n).
А вот моё решение на С++: pastebin.com/E9Xc4aBm Accepted (0.104).
А вот моё решение на С++: pastebin.com/E9Xc4aBm Accepted (0.104).
Благодарю за то, что открыли мне глаза на некоторые особенности языка C++. Теперь мне удалось ускорить второй вариант решения до Accepted (0.108)
Честно говоря, я сначала полагал, что такое решение должно быть значительно быстрее чем оба варианта из поста, но это оказалось не так. Думаю, что тут все дело в «не очень удачных тестовых наборах» под такой подход.
Ещё один вариант. Хорош, когда на одном наборе мало тестов.
Проходимся по массиву, подсчитывая числа, которые меньше нашего. Заодно ищем наше число — есть оно или нет.
Когда на одном наборе 10 тыс. тестов — ваш вариант, наверно, лучше.
Проходимся по массиву, подсчитывая числа, которые меньше нашего. Заодно ищем наше число — есть оно или нет.
Когда на одном наборе 10 тыс. тестов — ваш вариант, наверно, лучше.
Несмотря на всю полезность знания алгоритмов быстрой сортировки и бинпоиска, должен напомнить, что олимпиадные задачи важно не только правильно решить, но и написать это решение за минимальное время.
Поэтому на реальном контесте все-таки будет разумнее воспользоваться готовыми функциями qsort и lower_bound (которые делают в точности то, что нужно в данной задаче), вместо того, чтобы писать их руками — иначе на это уйдет гораздо больше времени, и значительно возрастут шансы ошибиться.
Поэтому на реальном контесте все-таки будет разумнее воспользоваться готовыми функциями qsort и lower_bound (которые делают в точности то, что нужно в данной задаче), вместо того, чтобы писать их руками — иначе на это уйдет гораздо больше времени, и значительно возрастут шансы ошибиться.
Поэтому на реальном контесте все-таки будет разумнее...
… уметь быстро и без ошибок писать эти алгоритмы.
Собственно, подобные задачи на проверку знания алгоритмов и рассчитаны.
>> уметь быстро и без ошибок писать эти алгоритмы.
вовсе нет. на этих соревнованиях необходимо выжимать все что только можно из компилятора, стандартной библиотеки и языка как такового в целом. Попытка «написать быстро и без ошибок qsort» равносильна провалу, потому что пока вы ее будете писать другие команды уже решат задачу.
вовсе нет. на этих соревнованиях необходимо выжимать все что только можно из компилятора, стандартной библиотеки и языка как такового в целом. Попытка «написать быстро и без ошибок qsort» равносильна провалу, потому что пока вы ее будете писать другие команды уже решат задачу.
Лично я уже не помню, когда последний раз писал вручную быструю сортировку — как в Си, так и в более привычной для меня Java присутствуют ее реализации с возможностью использования произвольных компараторов. Задачи, в которых этого не хватает, исключительно редки.
Бинпоиск — да, нередко бывает нужно самому написать, но в данной задаче этого можно избежать, что и следует делать в реальных условиях.
Я, может, вас разочарую, но тестирующий сервер никак не оценивает вашу степень знания базовых алгоритмов. Он оценивает только результаты, которые выдает ваше решение.
Поэтому важно не только знать реализации простейших вещей, но и быть в курсе всего арсенала функций, которых можно использовать уже готовыми.
Бинпоиск — да, нередко бывает нужно самому написать, но в данной задаче этого можно избежать, что и следует делать в реальных условиях.
Я, может, вас разочарую, но тестирующий сервер никак не оценивает вашу степень знания базовых алгоритмов. Он оценивает только результаты, которые выдает ваше решение.
Поэтому важно не только знать реализации простейших вещей, но и быть в курсе всего арсенала функций, которых можно использовать уже готовыми.
Когда я учился, все быстрые сортировки как раз таки писались ручками, потому что STL был в то время весьма зачаточным, а самым популярным языком на олимпиадах в тогда был Pascal, где никакими ништяками вроде std::map и близко не пахло. И такие задачи «на знание алгоритмов» определенно наследие прошлого.
Из условия задачи не смог понять, какое ограничение на N и Q.
Ваш второй способ — тоже сортировка (черпаком, если не ошибаюсь).
Мне кажется, что идея с bucket sort тут должна выстрелить в массив Elements[] на позицию RequestedNumber мы кладем число, где впервые встречается этот элемент (aavezel предлагает что-то очень похожее, только не понятно зачем ему более одного массива), т.е.
4 1
2
3
5
1
5
Elements[2] = 2
Elements[3] = 3
Elements[5] = 4
Elements[1] = 5
-? Elements[5] -> 4
Время работы линейно($\BigO(n)$) от длины массива входных данных — быстрее сделать невозможно, потому что нам все равно придется все числа считать.
Раcход памяти псевдоконстанта — \BigO(k) где k = max(a_i)
Время на один запрос константна от длины входных данных
4 1
2
3
5
1
5
Elements[2] = 2
Elements[3] = 3
Elements[5] = 4
Elements[1] = 5
-? Elements[5] -> 4
Время работы линейно($\BigO(n)$) от длины массива входных данных — быстрее сделать невозможно, потому что нам все равно придется все числа считать.
Раcход памяти псевдоконстанта — \BigO(k) где k = max(a_i)
Время на один запрос константна от длины входных данных
пугает серьёзность, с которой разбирается столь элементарная задача.
Нагуглил конкурентов. Выгодно отличается от данной системы наличием нескольких десятков языков, включая, например, D, Erlang, Go, Whitespace, Brainf***, PDF и bash. :)
www.spoj.pl
www.spoj.pl
> acm.sgu.ru
Delphi, MSVC, gcc, g++
:S
> acm.timus.ru
Java, C, C++, Pascal, C#
:S
> spoj.pl
ADA 95, Assembler, Bash, Brainf**k, C, C#, C++, C99 strict, Clips, Clojure, Common Lisp, D, Erlang, F#, Fortran 95, Go, Haskell, Icon, Intercal, JAR, Java, JavaScript, Lua, Nemerle, Nice, Ocaml, Pascal, PDF, Perl, Perl 6, PHP, Pike, PostScript, Prolog, Python, Python 3, Ruby, Scala, Scheme, Smalltalk, Tcl, TECS, Whitespace
WIN :P
Недостатка перед остальными не вижу. Аудитория — десятки решений в минуту, задач — тысячи.
Delphi, MSVC, gcc, g++
:S
> acm.timus.ru
Java, C, C++, Pascal, C#
:S
> spoj.pl
ADA 95, Assembler, Bash, Brainf**k, C, C#, C++, C99 strict, Clips, Clojure, Common Lisp, D, Erlang, F#, Fortran 95, Go, Haskell, Icon, Intercal, JAR, Java, JavaScript, Lua, Nemerle, Nice, Ocaml, Pascal, PDF, Perl, Perl 6, PHP, Pike, PostScript, Prolog, Python, Python 3, Ruby, Scala, Scheme, Smalltalk, Tcl, TECS, Whitespace
WIN :P
Недостатка перед остальными не вижу. Аудитория — десятки решений в минуту, задач — тысячи.
На большинстве используемых языков никто не решает олимпиадные задачи, потому у нас никто и не реализует их поддержку. (ну разве что плохо, что Python нет)
Зато для многих задач есть и русские условия.
Зато для многих задач есть и русские условия.
Да, для решения олимпиадных задач почему-то часто только системные ЯП допускаются. Извините, но отсутствие таких штук как Scheme непростительно. Мы же не драйвера пишем и не системные утилиты.
> ну разве что плохо, что Python нет
Чем он такой особенный? Будете делать Python, всё-равно скриптовый язык появится, можно поддержать и Ruby с Tcl. Но больше всего для некоторых задач не хватает Haskell и Scheme.
> ну разве что плохо, что Python нет
Чем он такой особенный? Будете делать Python, всё-равно скриптовый язык появится, можно поддержать и Ruby с Tcl. Но больше всего для некоторых задач не хватает Haskell и Scheme.
На spoj'e не делают разницы между языками и временем исполнения в отличие от acm.mipt.ru
> acm.mipt.ru
С/С++ (видимо, они считают это одним языком), Pascal, Perl, Python, Java
Похоже, в Российских онлайн-судьях допустимые языки определяются по их позиции на TPCI. На spoj.pl ограничения по времени выполенения не очень строгие и можно любую задачу решать на подходящем языке, а не на аком-либо из популярных, или на PostScript'е с брейнфаком, если делать нечего. :) Если же вы приучены забивать гвозди микроскопом, то, да, можно и на acm.*.ru
С/С++ (видимо, они считают это одним языком), Pascal, Perl, Python, Java
Похоже, в Российских онлайн-судьях допустимые языки определяются по их позиции на TPCI. На spoj.pl ограничения по времени выполенения не очень строгие и можно любую задачу решать на подходящем языке, а не на аком-либо из популярных, или на PostScript'е с брейнфаком, если делать нечего. :) Если же вы приучены забивать гвозди микроскопом, то, да, можно и на acm.*.ru
С чего это вы взяли? А по поводу временных ограничений на споже то, видимо, мало вы там что решали. Есть задачи, на которых в принципе не сможете пройти временные лимиты на интерпретируемых языках.
Кстати, разделение таки есть. Разве что лимит один на всех.
www.spoj.pl/ranks/FASHION/lang=JAVA
Там для некоторых задач уже есть ограничение на языки, можно предложить разработчикам ослабить таймлимит (на коэффициент) для нектороых языков. А вообще, если задача требовательна к процессору и на неё стоит строгий лимит — значит нужно выбрать язык, реализация вашего алгоритма на котором справится за установленное время. Не писать же числодробилки на Tcl, например, даже если вы всё остальное решаете на нём.
www.spoj.pl/ranks/FASHION/lang=JAVA
Там для некоторых задач уже есть ограничение на языки, можно предложить разработчикам ослабить таймлимит (на коэффициент) для нектороых языков. А вообще, если задача требовательна к процессору и на неё стоит строгий лимит — значит нужно выбрать язык, реализация вашего алгоритма на котором справится за установленное время. Не писать же числодробилки на Tcl, например, даже если вы всё остальное решаете на нём.
Кстати, проблема с браузером у меня возникала также! Нужно кукис почистить и все дальше отлично работать будет ;)
У меня не заходит в хроме. Выдаётся сообщение, что слишком много переадресаций.
Видимо, надо почистить куки и зайти как незнакомый пользователь.
Видимо, надо почистить куки и зайти как незнакомый пользователь.
Сортировка подсчетом — Accepted (0.100).
Автору большое спасибо за задачки, и есть одна небольшая просьба — выкладывать решение не на dropbox.com, а например на pastebin.com.
Автору большое спасибо за задачки, и есть одна небольшая просьба — выкладывать решение не на dropbox.com, а например на pastebin.com.
За идею с задачками респект. Отличная мысль. Возьму на вооружение.
Алексею, читателю хабры, удалось получить лучшее время (0.052) среди всех пользователей сайта uva.onlinejudge.org. Вот его решение. Мои поздравления!
Он также написал генератор тестов, возможно кому-нибудь понадобится.
Он также написал генератор тестов, возможно кому-нибудь понадобится.
Алексей молодец.
p.s. нужно попробовать искать не только максимум но и минимум.
Сейчас хотел попробовать, но uva.onlinejudge.org не работает…
p.s. нужно попробовать искать не только максимум но и минимум.
Сейчас хотел попробовать, но uva.onlinejudge.org не работает…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Олимпиадное хобби. Разделяй и властвуй