На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Цього туру обмеження за часом було перевірено неправильно. Наприклад, я написав рішення у задачі Brackets2019 за O(N), але здобув не усі бали через TL. Мабуть, причиною цього стало те, що програма при кількох запусках не може працювати за абсолютно однаковий час. (напр. 0.04с +- 0.01с). Більше того, порівнювати відношенням час роботи авторського рішення та рішення учасника, коли обидві програми працюють у межі похибки за часом є НЕкоректним. Тому, вважаю, що треба негайно перетестувати усі рішення другого туру через цю помилку у організації.
Відредаговано chopikus (2019-12-30 19:27:18)
Поза форумом
Час, відведений на 1 тест чи блок при офіційній перевірці - це подвоєний час найшвидшого розв'язку, який є в розпорядженні журі. Можливі незначні відхилення часу при он-лайн перевірках через нерівномірність навантаження на сервер (одночасно може тестуватися різна кількість задач)
Поза форумом
Виходить, що тестування не є об'єктивним. У підтвердження, одне й те саме рішення, відправляючи декілька разів, отримує дуже різні бали через TL. Ось у чому проблема.
Відредаговано chopikus (2019-12-30 22:54:20)
Поза форумом
Конкретно в случае с задачами на этом туре получилась неадекватная ситуация с ограничениями по времени. Решения, одинаковые по асимптотике и различающиеся лишь использованием префиксного или постфиксного инкремента в цикле, получают сильно разное количество баллов, хотя оба решения являются правильными.
Также нельзя признавать решение неправильным просто из-за того, что из-за загруженности сервера оно работало дольше, чем должно было. Это уже проблемы организаторов и никак не участников.
Відредаговано S1eap (2019-12-30 23:02:48)
Поза форумом
chopikus написав:
Виходить, що тестування за лімітом часу не є об'єктивним. У підтвердження, одне й те саме рішення, відправляючи декілька разів, отримує дуже різні бали. Ось у чому проблема.
При онлайн-тестуванні паралельно з перевіркою вашого рішення, тестувальна система може бути зайнятою ще й іншими речами. Наприклад, перевіркою інших рішень. Тому і скаче час виконання. Під час офіційної перевірки (в усякому разі, якщо вірити організаторам) система відключена від мережі, працює при стабільному навантаженні і відповідно, час виконання програм учасників більш стабільний.
Так, ТЛ-и тут доволі низькі, але 60-110 мс - це все таки не в межах похибки. Ймовірніше за все, ваше рішення влазить в ТЛ "на межі".
O(N) може бути дуже різним (спробуйте порахувати суму елементів у масиві і у зв'язному списку. І те і інше - О(N)). Тут доволі жорсткі часові обмеження і прихована в О-нотації константа теж має велике значення.
Відредаговано Dim_ov (2019-12-30 23:10:01)
Поза форумом
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)
Поза форумом
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), що працює за час у межах похибки - більше шансів, що організатори збільшать ТЛ-и і перетестують заново.
Поза форумом
Проведено повторне тестування розв'язків задачі bracket2019. Час на 1 тест подвоєно, тобто він тепер в 4 рази більший, ніж у найшвидшого розв'язку. О(N) дійсно буває різним...Автори "правильного", але "брудного" коду повинні бути задоволені. Система корректно вимірює час з точністю +-0.01 с. На жаль, всі звикли до фрази " Обмеження часу - 1 с"
Поза форумом