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


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

Ви не зайшли.

#1 2011-11-27 07:36:38

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

SumOfPowers

Я не дуже розбираюсь в тонкощах визначення тайм-лімітів під час тестування задач
http://forum.olymp.vinnica.ua/viewtopic.php?id=575

але в задачі SumOfPowers, наприклад, при тесті:
5 9876 1 2 3 4 5 .......
одне лише виведення результатів займе кілька секунд.

Може це не по суті завдання, але просто цікаво, чи зараховується час виведення даних в тайм-ліміт?

Відредаговано LVV (2011-11-27 07:39:33)


Вік живи - вік навчайся.

Поза форумом

 

#2 2011-11-27 08:48:23

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: SumOfPowers

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

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


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

Поза форумом

 

#3 2011-11-27 08:59:16

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: SumOfPowers

Ну, стосовно "даних" і "результатів", дійсно пардон smile
А стосовно "виведення", то я, по причині безграмотності в цьому питанні, мав на увазі виведення в консольне вікно (ось звідки "кілька секунд"). Буває. smile
Дякую за роз'яснення.

Відредаговано LVV (2011-11-27 09:00:37)


Вік живи - вік навчайся.

Поза форумом

 

#4 2011-11-27 09:00:58

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: SumOfPowers

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

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


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#5 2011-12-18 13:00:14

Scorpy
Новий користувач
Зареєстрований: 2011-11-09
Повідомлень: 9

Re: SumOfPowers

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

Поза форумом

 

#6 2011-12-18 14:08:49

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

Re: SumOfPowers

Scorpy написав:

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

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


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

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

Поза форумом

 

#7 2011-12-18 15:48:31

maxtram
Новий користувач
Зареєстрований: 2007-01-12
Повідомлень: 13

Re: SumOfPowers

Scorpy написав:

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

Поздравляю с гетом: твоё сообщение 7777-ое wink Значит, тебе повезёт и решение не получит 0 баллов.


laptop login: root
Password:
Last login: Thu Jan  1 00:00:00 UTC 1970
root@[laptop:~]# eix-sync && emerge -atuvDN world

Поза форумом

 

#8 2011-12-18 17:10:04

Scorpy
Новий користувач
Зареєстрований: 2011-11-09
Повідомлень: 9

Re: SumOfPowers

Dim_ov написав:

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

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

Поза форумом

 

#9 2011-12-18 18:04:49

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

Re: SumOfPowers

Scorpy написав:

Dim_ov написав:

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

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

Тести з умови ж не оцінюються. Так що на них цілком можна поставити ТЛ-и авторського рішення, навіть якщо у когось буде швидше.

Поза форумом

 

#10 2011-12-20 00:31:41

shoa169
Новий користувач
Зареєстрований: 2010-11-10
Повідомлень: 56

Re: SumOfPowers

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

Поза форумом

 

#11 2011-12-20 07:27:38

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

Re: SumOfPowers

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

Можете відправити щось зациклене як задачу першого туру - час виконання до примсового скиданнябуде різним

Поза форумом

 

#12 2011-12-20 11:33:17

shoa169
Новий користувач
Зареєстрований: 2010-11-10
Повідомлень: 56

Re: SumOfPowers

Dim_ov написав:

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

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

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

Поза форумом

 

#13 2011-12-20 11:42:34

Scorpy
Новий користувач
Зареєстрований: 2011-11-09
Повідомлень: 9

Re: SumOfPowers

Dim_ov написав:

Scorpy написав:

Dim_ov написав:

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

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

Тести з умови ж не оцінюються. Так що на них цілком можна поставити ТЛ-и авторського рішення, навіть якщо у когось буде швидше.

Кроме проблем с тестами из условия могут возникнуть другие проблемы. Например, авторское решение и решения всех участников имеют асимптотику O(n^2). Но какой-то хитрый участник напишет для n = 10^4 просто вывод заранее рассчитанного ответа. Тогда на этом тесте у него будет работать за доли миллисекунд, а у всех остальных за время порядка 0.1 секунды. В этом случае у жюри есть выбор: поставить ТЛ 0,001 секунда и завалить все решения, что не есть хорошо, или поставить нормальный ТЛ и не обращать внимания на самое быстрое решение. Чтобы принять правильное решение нужно посмотреть код самой быстрой программы. Неужели жюри смотрит все коды?

Поза форумом

 

#14 2011-12-20 16:34:03

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

Re: SumOfPowers

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


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

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

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

Поза форумом

 

#15 2011-12-20 18:18:44

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: SumOfPowers

Офіційна (можливо, й не вичерпна, зате правильна) відповідь.

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

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

Випадки, коли журі виставляє тайм-ліміти за найкращою програмою учасника, а не найкращою програмою журі, можливі, але є виключенням, а не правилом. Якщо журі має сумніви щодо правильності швидкої програми учасника -- вона не використовується для визначення тайм-лімітів.


Тепер філософські зауваження щодо філософського питання "а чи це правильно".

Такий підхід сформований давно і є традицією NetOI.

Такий підхід все-таки не є приколом єдино виключно NetOI. Саме така ситуація на одному з найповажніших польських конкурсів алгоритмічного програмування Potyczki Algorytmiczne (принаймні тих серій змагань, які по квітням--травням). Різні тайм-ліміти ІНОДІ використовувалися і на "великому" Всеукрі (абсолютно точно були у 2006-му, відтоді можливо й не було, точно не знаю).

Далеко не на всіх ACM-ках використовується облік часу по кожному тесту окремо. Не далі як на останньому SEERC, на вимогу букурештської сторони, було використано перевіряючу систему PC^2, де неминуче один тестфайл з багатьма тестовими прикладами, і час рахується лише сумарний. Це, звісно, не те саме, що малі тайм-ліміти на малі тести, але теж спонукає робити і оптимізації для найгіршого випадку, і оптимізації у середньому. Буду вдячний тим, хто надасть достовірну інформацію з перших рук, як із цим на фіналі світу ACM ICPC.

Поза форумом

 

#16 2011-12-26 21:54:51

yaa
Новий користувач
Зареєстрований: 2011-12-26
Повідомлень: 4

Re: SumOfPowers

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

Поза форумом

 

#17 2011-12-26 22:06:45

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

Re: SumOfPowers

yaa написав:

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

Відповім завтра перед закінченням строку відправки smile

Поза форумом

 

#18 2011-12-26 23:08:19

kiberok
Новий користувач
Зареєстрований: 2011-10-27
Повідомлень: 23

Re: SumOfPowers

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

Поза форумом

 

#19 2011-12-26 23:17:34

WslF
Новий користувач
Зареєстрований: 2011-10-27
Повідомлень: 19

Re: SumOfPowers

kiberok написав:

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

меня это тоже интересует)
и еще такой вопрос: если задача проходит онлайн проверку это значит, что размер кода, объем использованной памяти ... не превышают разрешенные нормы?

Поза форумом

 

#20 2011-12-26 23:36:31

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

Re: SumOfPowers

kiberok написав:

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

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

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


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

Поза форумом

 

#21 2011-12-27 08:42:57

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: SumOfPowers

Dim_ov написав:

Відповім завтра перед закінченням строку відправки smile

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


yaa написав:

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

Так, є.


Вік живи - вік навчайся.

Поза форумом

 

#22 2011-12-27 09:07:12

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

Re: SumOfPowers

LVV написав:

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

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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt