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

Так, виведення результатів (якщо починати чіплятися до всього підряд, то програма таки вводить дані, а виводить таки результати, чи не так?) -- теж робота програми, тому час виведення теж включається до часу роботи програми.

Але не треба займатися обманом неокрепших умів, заявляючи, ніби виведення результатів займатиме кілька секунд. Розмір результату для вказаного Вами тесту десь 15--25 кілобайтів. Кілька секунд на 15--25 кілобайтів -- це швидкість, малувата навіть для дискети 5,25". Уклінно прошу Вас повірити на слово, що при перевірці задач журі використовує значно більш швидкий носій, ніж дискети 5,25".


А всіх, хто стверджує, ніби включення часу виведення у час роботи програми -- буцімто проблема виключно єдино єретичної перевірялки НетОІ, а інші православні перевірялки цієї проблеми ніби не_мають -- ласкаво запрошую здати на сайті informatics.mccme.ru задачу "85. Все перестановки заданной длины" всіма способами, про які я писав у тамошньому форумі.

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

Відредаговано Присяжнюк А.В. (2011-11-27 09:01:30)

Scorpy написав:

А можно узнать хотя бы примерные тайм лимиты? Дело в том, что моё решение работает примерно одинаковое время на всех тестах и мне не хочется, чтобы оно получило 0 баллов.

Справа в тому, що тут нікому не хочеться, щоб його програма отримала 0 балів
Тайм ліміти тут не повідомляють, по перше, через те, що не знаючи їх учасники оптимізуватимуть задачу "до кінця", а не до того моменту, коли воня як-небуть зі скрипом влізе в ТЛ. А по друге - їх не повідомляють, бо їх напевно ніхто не знає аж до самого моменту перевірки. ТЛ-и встановлюються в кілька разів більші, ніж витрачає найшвидша програма. А найшвидша програма може надійти і від учасника - не обов’язково від Жюрі.


П.С. Якщо Вам це допоможе, то "кілька секунд" для тесту, подібного до тесту в шапці - це дійсно забагато.

Відредаговано Dim_ov (2011-12-18 14:15:24)

Dim_ov написав:

ТЛ-и встановлюються в кілька разів більші, ніж витрачає найшвидша програма. А найшвидша програма може надійти і від учасника - не обов’язково від Жюрі.

То решение может пройти тесты из условия во время online-проверки и не пройти их во время тестирования? Это было бы очень странно.

Ещё вопрос по TL. Его ведь можно вычислять двумя способами:
1) <Общий для всех тестов верхний предел для времени> = <время, затраченное самым быстрым решением на самом "долгом" тесте> * <Коэффициент>.
2) <Для каждого теста - свой TL > = <время, затраченное самым быстрым решением на ЭТОМ тесте> * <Коэффициент>.
  Для тех, кто привык к правилам ACM 1-й вариант привычнее (оценил, что решение проходит по времени на максимально сложном тесте - и сдаешь).
  2-ой вариант кажется слишком вычурным, но у него тоже найдутся приверженцы (оптимизировать до последнего!). Только ведь в реальных задачах программа должна всего лишь укладываться в заданные ограничения по времени при заданных ограничениях по данным (+ другие ограничения)...
  А какой вариант вычисления TL используется на NetOI ?

Dim_ov написав:

ТЛ-и міряються для кожного тесту окремо.

Это забавно.
  В таком случае решение со сложным алгоритмом, обеспечивающим минимальное время расчетов на "больших" тестах вызовет на этих тестах вердикт TL у "простых" решений.
  Но с другой стороны на каких-то простых тестах такой сложный алгоритм может сам получить TL, т.к. простое решение может оказаться быстрее. Например, для какого-то частного случая в простом решении может быть "забито" готовое предпосчитанное решение. Оно будет выполняться много быстрее, чем по любым алгоритмам, и соответственно "завалит" остальные решения на этом тесте.
Это нормально?
PS. Ясное дело, что "В чужой монастырь...". Но может быть, судьи задумаются.

Відредаговано shoa169 (2011-12-20 20:30:41)

як воно там все насправді відбувається я не знаю і знати не можу, тож все далі сказане - лише мої здогадки


по перше, у задачах, де оптимальним є алгоритм з асимптотикою O(n^2) як правило, крім n є ще якісь вхідні дані, і цих додаткових даних, зазвичай, O(n). Тому прорахувати всі відповіді для всих тестів не вийде.
по друге, ніхто не примушує писати один-єдиний загальний алгоритм для всих наборів вхідних даних. І я думаю, програми жюрі іноді так і зроблені. Якщо скажімо, якийсь загальний алгорим працює 100-200 мс для всих n від 0 до 100500, а при n=100501 він працює годину - то цілком можна обробити цей випадок якось окремо, чи навіть захардкодити відповідь, якщо умова дозволяє.
Ну а якщо справді буде ситуація, коли проходить тільки одне рішення, а інші валяться - то на те вони й журі, щоб правильно оцінити таку ситуацію і прийняти міри(до речі, журі взагалі не має права якось оцінювати вихідний код програми, відповідно "смотреть все коды" не має сенсу. Рішення прийматиметься незалежно від того, що той учасник написав).

Хоча насправді така ситуація може відбутися лише на дуже обмеженій кількості тестів до дуже обмеженої кількості задач, тому якось суттєво на результат олімпіади це все одно не вплине. Особливо якщо врахувати, що перед 4 туром всі бали діляться на 10.

Відредаговано Dim_ov (2011-12-20 16:36:52)

Чи є хтось з учасників у кого відповідь на тесті 2 1 987654 отримується швидше за 1 секунду?

Не подскажите наибольший размер исходника, который можно сдать?

kiberok написав:

Не подскажите наибольший размер исходника, который можно сдать?

Журі чомусь не відповідають(хоча як мінімум двоє мали б бачити попереднє повідомлення), мабуть мають якісь на те причини, хоча мені вони й не зрозумілі

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


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

LVV написав:

А хіба це секретна інформація?

Конкуренція
У мене майже миттєво.