Форум Всеукраїнської інтернет-олімпіади NetOI

Журі NetOI-2005 - Пасіхов · 2005-12-22 21:03:35

ЖЮРИ ПРИНОСИТ СВОИ ИЗВИНЕНИЯ. В проверяющем модуле к задаче PRIMENUM обнаружена ошибка, которая привела к искажению результатов пакетной проверки. Спасибо тем участникам, которые в КОРРЕКТНОЙ форме указали на возможную ошибку. Ошибка исправлена, теперь результаты пакетной проверки правильно экспортируются. ЕЩЕ РАЗ ПРИНОСИМ СВОИ ИЗВИНЕНИЯ. Смотрите уточненные результаты на сервере.

Ivan · 2005-12-22 23:30:00

Cпасибо. Если честно, не ожидал такой реакции жюри :-), думал что будет как обычно :-(

Трегубенко Антон · 2005-12-23 20:04:04

Я хотів запитати, яка часова складність задач у розвязках жюрі.
У мене, наприклад, складність така:
wood О(N)
dsp O(M*N)
building O(M*N)
primenum O(MaxL)
country O(N)

але повний бал можна набрати розв'язавши dsp за O(M*N*(M+N)) та building за O(M*N*MIN(M,N)).

Різниця складностей досить велика, тому я хотів би, щоб переглянули задачі dsp та building

Raziel Redstone · 2005-12-24 07:56:27

Если уж на то пошло, то сложность решения задачи wood (без учета времени считывания) будет O(log(N)*log(maxh)). Почему это имеет значение: считывание происходит не просто за O(N), а за N операций. Константа при решении около 2. Таким образом, при хорошей реализации в худшем случае количество операций, которые машине необходимо совершить для нахождения ответа будет на сотню-другую меньше...

Но вопрос: стоит ли настолько придираться к решению, если оно работает на тысячную долю секунды дольше, чем самое оптимальное..? Особенно если учесть, что эту долю не так уж и просто отследить, и еще то, что времени дается в два раза больше, чем требует авторская прога, то возникают подозрения, что разница сложностей не такая уж и большая. Хотя, это всего лишь ИМХО...

Другое дело - четкость доказательства и красота решения. Просто не все от этого получают удовольствие...

Ivan · 2005-12-24 19:10:26

В случае билдинг и ДСП разница не так мала, как ты сказал
Быстрее O(N) wood не сделаешь именно из за считывания.

Трегубенко Антон · 2005-12-25 12:40:35

Иван прав. А к wood я не придираюсь, хотя у меня Всего 3 прохода по масиву и всё

Форум Всеукраїнської інтернет-олімпіади NetOI

#1 2005-12-22 21:03:35

УТОЧНЕНИЕ РЕЗУЛЬТАТОВ 2-го тура

#2 2005-12-22 23:30:00

Re: УТОЧНЕНИЕ РЕЗУЛЬТАТОВ 2-го тура

#3 2005-12-23 20:04:04

Re: УТОЧНЕНИЕ РЕЗУЛЬТАТОВ 2-го тура

#4 2005-12-24 07:56:27

Re: УТОЧНЕНИЕ РЕЗУЛЬТАТОВ 2-го тура

#5 2005-12-24 19:10:26

Re: УТОЧНЕНИЕ РЕЗУЛЬТАТОВ 2-го тура

#6 2005-12-25 12:40:35

Re: УТОЧНЕНИЕ РЕЗУЛЬТАТОВ 2-го тура

Нижній колонтитул