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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

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

Журі NetOI-2005 - Пасіхов
Адміністратор
Зареєстрований: 2005-10-01
Повідомлень: 74

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

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

Поза форумом

 

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

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

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

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


ICQ 233-416-344

Поза форумом

 

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

Трегубенко Антон
Новий користувач
Зареєстрований: 2005-12-23
Повідомлень: 7

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

Я хотів запитати, яка часова складність задач у розвязках жюрі.
У мене, наприклад, складність така:
  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

Поза форумом

 

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

Raziel Redstone
Олімпієць
Звідки: Hell
Зареєстрований: 2005-11-19
Повідомлень: 55

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

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

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

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

Поза форумом

 

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

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

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

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


ICQ 233-416-344

Поза форумом

 

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

Трегубенко Антон
Новий користувач
Зареєстрований: 2005-12-23
Повідомлень: 7

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

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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt