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

1) Можно ли получить архив со своими исходниками с тура?
2) Планируется ли когда-нибудь замена используемой сейчас устаревшей системы проведения олимпиады? Уже пару лет на 3 и 4 этапах Всеукраинской олимпиады (и, что тоже важно, на межнаре) есть возможность получать свои баллы во время тура . Эта возможность была бы совсем не лишней, учитывая специфику задач, при которой приходится запихивать асимптотически оптимальные решения в неуказанный в задачах тайм-лимит.

Відредаговано Scorpy (2014-02-15 21:13:09)

Scorpy написав:

1) Можно ли получить архив со своими исходниками с тура?
2) Планируется ли когда-нибудь замена используемой сейчас устаревшей системы проведения олимпиады? Уже пару лет на 3 и 4 этапах Всеукраинской олимпиады (и, что тоже важно, на межнаре) есть возможность получать свои баллы во время тура . Эта возможность была бы совсем не лишней, учитывая специфику задач, при которой приходится запихивать асимптотически оптимальные решения в неуказанный в задачах тайм-лимит.

1.  Да, в ПОЛНОМ архиве олимпиады, скоро, впрочем как и решения жюри, все тесты и решения все участников с протоколами проверки.
2. Систему заменять тут не нужно, действующая умеет все, чего вы хотите. Вопрос, скорее, идеологический. По мнению команды NetOI предлагаемый подход неприемлим для заочных туров, а вот финал...дискуссионно. Созреем - внесем изменения в правила. А пока так...

учень1 написав:

А чи не може вельмишановне журі пояснити чому в задачі Sweets присутні тести в яких n значно перевишує значення, що дано в умові, тобто n<=2^17?
Вимагаю перепровірити задачу на тестах, що відповідають умові.
ПРИПИНІТЬ СВАВІЛЛЯ!

Про свавілля - це занадто, шановний. Це помилка авторів тестів. Дійсно, у 2-х тестах мали місце значення, більші за обмеження в умові. Виправлено, проведено повторну перевірку, внесено зміни в таблицю результатів. Приносимо свої вибачення. Просимо бути коректнішим, особливо тоді, коли правдв на вашому боці. Нормальні люди здатні розуміти нормальні аргументи.

Ні, перевірялась мінімум тричі. Технічні протоколи будуть додані до архіва. Назначні розходження (1-2 тести) при таких малих таймлімітах бувають завжди через неоднорідність навантаження на сервер при он-лайн перевірці. Про це вже не раз повідомлялось. Але я все ж радив вам бути толерантнішим. Ваше "ДОБРЕ" сприймається, як імператрська добра воля  про помилування державних злочинців. Все таки варто бути меньш агресивним.

Офіційний результат зараховується лише після того, коли результати всі трьох перевірок співпадають. Якщо ж виявляється на якихось тестах розходження по таймлімітах (в одному випадку проходить, в іншому - ні) час на цей тест збільшується на 0.01 с. і проводиться знову серія перевірок. так поки тричі не співпаде по всім тестам. В он-лайн перевірці МОЖУТЬ бути розходження (раз на раз не приходиться по завантаженню системи), але лише у задачах із малими таймінгами. У бульшості випадків організатори олімпіад виходять із цього полження  так: з самого початку завищують таймінги, наприклад класична ситуація - 0.5 с на кожен із тестів, а вони реально проходять на гарному розв'язку, звичайно, за 0.01 с (швидкі нині процесори...). При цьому відсікти розвязки, наприклад в О(n^2) від більш оптимальних вдається лише на величезних n.

shoa169 написав:

Жюри_Пасихов написав:

При цьому відсікти розвязки, наприклад в О(n^2) від більш оптимальних вдається лише на величезних n.

Неужели, число 100`000 считается в наш компьютерный век "величезним" ? Даже паскалевский long его покрывает со значительным запасом.
В студентческих соревнованиях ACM/ICPC тайм-лимит в 1 секунду фактически является стандартном для всех задач. Свежий пример - задачи сегодняшнего тура Зимней компьютерной школы ХИРЭ: http://ejudge.ws.kh.ua/media/problems/2 … emskyi.pdf
Так вот я сильно сомневаюсь, что какой-то нетривиальный алгоритм О(n^2) для n=10^5 можно "запихнуть" в 1 секунду!
Уверен, что уважаемому жюри NetOI нужно изучить опыт ACM/ICPC в области тайм-лимитов!

Не совсем так. Все зависит от константы. Если константа порядка 0.01, можно, ка Вы пишете, запихнуть.

Жюри_Непомнящий написав:

shoa169 написав:

Так вот я сильно сомневаюсь, что какой-то нетривиальный алгоритм О(n^2) для n=10^5 можно "запихнуть" в 1 секунду!

Не совсем так. Все зависит от константы. Если константа порядка 0.01, можно, ка Вы пишете, запихнуть.

А Вы попробуйте!
(10^5)^2 = 10^10. Какая частота у процессора? 3 ГГерц? Сколько тактов в секунду? 3*10^9.
Как при такой "медлительности" заставить процессор выполнить 10^10 НЕТРИВИАЛЬНЫХ циклов?
Вряд ли даже цикл с пустым телом успеет за 1 секунду добежать до 10^10! Не говоря уже о реализации нетривиального алгоритма.

Відредаговано shoa169 (2014-02-18 17:12:43)

shoa169 написав:

Резюмируя: переход на показ участникам очного тура его текущих баллов по задачам - веление времени! :)

Веление времени есть. А вот верно ли оно - вопрос. Однако в любом случае  не снимается с повестки дня. Аргументы против:
- никогда и нигде  (ну, кроме олимпиад по программированию, и то не всех), при измерениях интеллектуального уровня или уровня знаний (разных там тестирований, ЗНО, етс., котрых в мире полно), испытуемый не получает оценки за свою работу, пока ее не закончит. Хотя при нынешнем развитии компьютерных технологий это не вопрос, можно говорить "верно" - "не верно" после каждого теста). Почему? Да потому, что это неверно с точки зрения психологии, это вам скажет любой специалист.  Несколько "оглашенных" неудач при тестировании одной задачи способны вывести участника из равновесия настолько, что он уже не может решить другую, в обычной ситуации посильную для него задачу. Он-лайн тестирование на авторском тесте неограниченное число раз нужно, дабы избежать крайне обидных ошибок ввода-вывода, формата представления ответа, оно страхует участника от обидных ошибок, внушает некую уверенность, при этом ничего, кроме того, что он "тупо не лопухнулся", не гарантирует. Первое подсознательно укрепляет веру в свои силы, второе - провоцирует сражаться дальше, ничего не обещая;
- НИ ОДНО самое авторитетное жюри не может гарантировать, что в его "авторском" наборе тестов а) нет ошибок б) что он исчерпывающе полон. МНОГОКРАТНО сталкивался  (и что интересно, эти задачи с теми же наборами тестов "мигрируют" из системы в систему, из архива в архив), когда в тестах есть просто ошибка, и не одна, или некий тест авторское решение проходит, а другие ПРАВИЛЬНЫЕ - нет.) Классическая ситуация - в наше простенькой задачке  Sweets было два теста, входные данные которых превышали указанные в задаче ограничения. Авторские решения легко проходили их, ошибка оставалась незамеченной, УВЫ (у меня есть мужество признавать ошибки...). А теперь представьте себе, что весь набор лежал бы изначально в он-лайне! Участники АБСОЛЮТНО ЗРЯ "парились" бы, пытаясь получить полный бал за ПРАВИЛЬНЫЕ решения, пытаясь их улучшить! Сколько времени было бы угроблено, пока ошибка всплыла б? Это означало бы просто сорванную олимпиаду. А так... ошибка обнаружилась после официальной проверки.  Мы извинились, и повторили ее уже на корректном наборе тестов. Никто не пострадал ни раньше, ни позже. А ГАРАНТИРОВАТЬ ОТСУТСТВИЕ ПОДОБНЫХ ОШИБОК НЕВОЗМОЖНО!
(хотя бы из законов Паркенсона :-), в них чаще всего не признаются.... ПОВТОРЮСЬ - ИМЕЮ КОЛЛЕКЦИЮ ИЗ ДОБРОЙ СОТНИ ЗАДАЧ С ОЧЕНЬ АВТОРИТЕТНЫХ ОЛИМПИАД, ГДЕ ОШИБКИ ПОДОБНОГО РОДА НЕ ИСПРАВЛЯЛИСЬ! Я уж не говорю о том, что сдав задачу на полный балл, одна из моих команд еще до конца олимпиады  нашла контрпример к своему решению... Это вообще сплошь и рядом.
Однако, думаем, возможно и внесем изменения в правила real-time тура в будущем году.

Ilya Porublyov написав:

Якщо "учасник повинен зразу бачити все" -- таке вже веління часу, то чому його НЕ дотримуються ні Codeforces, ні Topcoder ? Мабуть, тому, що "учасник повинен зразу бачити все" все ж лише одна з точок зору, і не факт, чи найкраща.

Главный и на самом деле единственный аргумент в пользу предоставления участнику его текущего результата - это то, что следующие две ступени олимпиады школьников  по информатике (как Всеукраинская, так и Международная) проходят именно так!

Ilya Porublyov написав:

Ну і зараз все ще не можна вважати, що інет аж настільки надійний, щоб можна було цілком і повністю знехтувати ймовірністю проблем із ним. Коли в онлайні лише тест з умови -- такою сумною подією як "у деяких з учасників півгодини не було можливості перевіряти" ще можна знехтувати, але не тоді, коли можливість перевірки дає учаснику істотну інформацію. Все-таки у форматі даної олімпіади і площадок надто багато, і в той же час все занадто офіційно й занадто розділяє поняття учасник та місцевий організатор, щоб можна було просто керуватися логікою Codeforces/Topcoder/...

Проблема с интернетом ведь легко решается, если проверка решений будет выполняться локальными серверами, которые бы синхронизировали данные с центральным сервером.
Уверен, что для людей, которые сформировали мнение, что "Вінниця просто центр по програмуванню зараз" - это не будет сложной задачей!

Жюри_Пасихов написав:

никогда и нигде  (ну, кроме олимпиад по программированию, и то не всех), при измерениях интеллектуального уровня или уровня знаний (разных там тестирований, ЗНО, етс., котрых в мире полно), испытуемый не получает оценки за свою работу, пока ее не закончит.  Хотя при нынешнем развитии компьютерных технологий это не вопрос, можно говорить "верно" - "не верно" после каждого теста

Это не делают в большинстве тестирований и на олимпиадах, по всем не компьютерным предметам, потому, что это технически не выполнимо (посадить всех учеников выполнять ЗНО за компьютерами нереально).

Жюри_Пасихов написав:

Почему? Да потому, что это неверно с точки зрения психологии, это вам скажет любой специалист.  Несколько "оглашенных" неудач при тестировании одной задачи способны вывести участника из равновесия настолько, что он уже не может решить другую, в обычной ситуации посильную для него задачу.

Лично меня гораздо больше выводит из равновесия и напрочь лишает желание участвовать в олимпиаде в следующий раз то, что можно правильно решить все задачи и получить половину баллов после конца контеста из-за ошибок в реализации. На кого вообще рассчитана такая позиция? Опытные участники не обращают внимания на количество неудачных попыток перед получением ОК. С другой стороны, опытные участники показывают худшие результаты из-за того, что не могут получить этот самый ОК и сосредоточиться на остальных задачах, а вынуждены долго тестировать свои задачи или надеяться на удачу. Тут следует также вспомнить про то, что не указывается таймлимит в задачах. Поэтому опытный участник может написать асимптотически верное решение, запустить его локально на макстесте, получить 1с выполнения, а дальше теряться в загадках - следует ли оптимизировать ещё или нет? Подобная ситуация регулярно возникает в финалах данного соревнования (две задачи на поиск в ширину с прошлого года, MaxDivs3 этого года (у меня локально на макс. тесте работала 21 с, а зашла на 85 баллов)). Что до неопытных участников, то они, как правило, хуже умеют тестировать программу и оценивать сложность своего алгоритма, а значит для них олимпиада целиком превращается в лотерею.

Жюри_Пасихов написав:

НИ ОДНО самое авторитетное жюри не может гарантировать, что в его "авторском" наборе тестов а) нет ошибок б) что он исчерпывающе полон

Да, но ошибки встречаются примерно в одном из двадцати контестов, которые готовят грамотное жюри. Кроме того, ситуация, когда обнаруживается ошибка, является абсолютно рабочей и быстро исправляется тем же грамотным жюри. Я не могу вспомнить ни одного контеста по сис-ме АСМ из тех, в которых участвовал, в котором бы неверный тест остался до конца контеста или хоть сколько-нибудь серьёзно помешал участником. Мне хочется верить, что жюри данной олимпиады является достаточно компетентным для того, чтобы а) подготовить тестсет с минимальным кол-вом ошибок б) следить за ходом олимпиады и своевременно исправлять все найденные ошибки.