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


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

Ви не зайшли.

#1 2019-12-30 17:23:38

chopikus
Олімпієць
Зареєстрований: 2017-11-10
Повідомлень: 27

Дуже цікава перевірка часу

Цього туру обмеження за часом було перевірено неправильно. Наприклад, я написав рішення у задачі Brackets2019 за O(N), але здобув не усі бали через TL. Мабуть, причиною цього стало те, що програма при кількох запусках не може працювати за абсолютно однаковий час. (напр. 0.04с +- 0.01с). Більше того, порівнювати відношенням час роботи авторського рішення та рішення учасника, коли обидві програми працюють у межі похибки за часом є НЕкоректним. Тому, вважаю, що треба негайно перетестувати усі рішення другого туру через цю помилку у організації.

Відредаговано chopikus (2019-12-30 19:27:18)

Поза форумом

 

#2 2019-12-30 22:35:58

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Дуже цікава перевірка часу

Час, відведений на 1 тест чи блок при офіційній перевірці  - це подвоєний час найшвидшого розв'язку, який є в розпорядженні журі. Можливі незначні відхилення часу при он-лайн перевірках через нерівномірність навантаження на сервер (одночасно може тестуватися різна кількість задач)

Поза форумом

 

#3 2019-12-30 22:51:26

chopikus
Олімпієць
Зареєстрований: 2017-11-10
Повідомлень: 27

Re: Дуже цікава перевірка часу

Виходить, що тестування не є об'єктивним. У підтвердження, одне й те саме рішення, відправляючи декілька разів, отримує дуже різні бали через TL. Ось у чому проблема.

Відредаговано chopikus (2019-12-30 22:54:20)

Поза форумом

 

#4 2019-12-30 23:02:03

S1eap
Олімпієць
Звідки: Харьков
Зареєстрований: 2017-10-28
Повідомлень: 7

Re: Дуже цікава перевірка часу

Конкретно в случае с задачами на этом туре получилась неадекватная ситуация с ограничениями по времени. Решения, одинаковые по асимптотике и различающиеся лишь использованием префиксного или постфиксного инкремента в цикле, получают сильно разное количество баллов, хотя оба решения являются правильными.

Также нельзя признавать решение неправильным просто из-за того, что из-за загруженности сервера оно работало дольше, чем должно было. Это уже проблемы организаторов и никак не участников.

Відредаговано S1eap (2019-12-30 23:02:48)

Поза форумом

 

#5 2019-12-30 23:07:36

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Дуже цікава перевірка часу

chopikus написав:

Виходить, що тестування за лімітом часу не є об'єктивним. У підтвердження, одне й те саме рішення, відправляючи декілька разів, отримує дуже різні бали. Ось у чому проблема.

При онлайн-тестуванні паралельно з перевіркою вашого рішення, тестувальна система може бути зайнятою ще й іншими речами. Наприклад, перевіркою інших рішень. Тому і скаче час виконання. Під час офіційної перевірки (в усякому разі, якщо вірити організаторам) система відключена від мережі, працює при стабільному навантаженні і відповідно, час виконання програм учасників більш стабільний.

Так, ТЛ-и тут доволі низькі, але 60-110 мс - це все таки не в межах похибки. Ймовірніше за все, ваше рішення влазить в ТЛ "на межі".
O(N) може бути дуже різним (спробуйте порахувати суму елементів у масиві і у зв'язному списку. І те і інше - О(N)). Тут доволі жорсткі часові обмеження і прихована в О-нотації константа теж має велике значення.

Відредаговано Dim_ov (2019-12-30 23:10:01)

Поза форумом

 

#6 2019-12-30 23:14:32

S1eap
Олімпієць
Звідки: Харьков
Зареєстрований: 2017-10-28
Повідомлень: 7

Re: Дуже цікава перевірка часу

Dim_ov написав:

При онлайн-тестуванні паралельно з перевіркою вашого рішення, тестувальна система може бути зайнятою ще й іншими речами. Наприклад, перевіркою інших рішень. Тому і скаче час виконання. Під час офіційної перевірки (в усякому разі, якщо вірити організаторам) система відключена від мережі, працює при стабільному навантаженні і відповідно, час виконання програм учасників більш стабільний.

Это как раз противоречит тому, что при проверке онлайн решение набирает больший балл.

Dim_ov написав:

Так, ТЛ-и тут доволі низькі, але 60-110 мс - це все таки не в межах похибки.

Да, 60-110 мс – не погрешность, однако мы говорим про 10-20 мс.

Dim_ov написав:

O(N) може бути дуже різним (спробуйте порахувати суму елементів у масиві і у зв'язному списку. І те і інше - О(N)).

В задаче про скобки хватает одного прохода по массиву, и мне кажется что почти у всех, у кого 32-40 баллов, именно такое решение. Поэтому фраза "О(n) может быть разным" здесь, увы, никак не работает.

Відредаговано S1eap (2019-12-30 23:24:21)

Поза форумом

 

#7 2019-12-30 23:39:43

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Дуже цікава перевірка часу

S1eap написав:

Это как раз противоречит тому, что при проверке онлайн решение набирает больший балл.

В онлайн-перевірці ТЛ-и ставлять трохи вищі, ніж в офіційній.

S1eap написав:

Да, 60-110 мс – не погрешность, однако мы говорим про 10-20 мс.

Зараз у мене в онлайн-перевірці всі тести з ТЛ 110 мс., хоча кілька хвилин тому були 60-110 в залежності від тесту. Можливо проблема з ТЛ таки була і організатори зараз якраз в процесі їх підкручування)

S1eap написав:

В задаче про скобки хватает одного прохода по массиву, и мне кажется что почти у всех, у кого 32-40 баллов именно такое решение. Поэтому фраза "О(n) может быть разным" здесь, увы, никак не работает.

Ну, під час одного проходу теж можна різними речами займатися і по-різному прохід організовувати. Плюс ще є введення. Якщо вводити рядок посимвольно (наприклад, cin-ом без ios_base::sync_with_stdio(false)), то запросто можна отримати час виконання у 2-3 рази більший, ніж з використанням якогось gets.

Я не стверджую, що у вас 100% є якісь проблеми з розв'язками, а організатори святі й безгрішні. Просто раджу розглянути і цей варіант теж.

Можете викласти своє рішення тут, тур уже закінчився. Якщо там дійсно оптимальний O(N), що працює за час у межах похибки - більше шансів, що організатори збільшать ТЛ-и і перетестують заново.

Поза форумом

 

#8 2019-12-30 23:41:39

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Дуже цікава перевірка часу

Проведено повторне тестування розв'язків задачі bracket2019. Час на 1 тест подвоєно, тобто він тепер в 4 рази більший, ніж у найшвидшого розв'язку. О(N) дійсно буває різним...Автори "правильного",  але "брудного" коду повинні бути задоволені. Система корректно вимірює час з точністю +-0.01 с. На жаль, всі звикли до фрази " Обмеження часу - 1 с"

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt