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


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

Ви не зайшли.

#1 2018-12-17 19:27:03

dalgerok
Олімпієць
Зареєстрований: 2018-12-11
Повідомлень: 4

Запитання по задачі Minbus

В умові написано таке:
"Кожен i-й рядок з наступних N рядків містить ціле число - час руху від зупинки і до зупинки i + 1 (N + 1 -а зупинка - завод), кількість робітників K, які прийдуть на i-ую зупинку, і час приходу кожного робітника на цю зупинку в порядку приходу (1≤M≤2000, 1≤N, K≤200000)."
З цього випливає, що у вхідних даних N може дорівнювати 200000. Тобто 200000 рядків. В кожному з цих рядків нам дається число К та К чисел. К може дорівнювати 200000. Виходить, що у вхідних даних може бути 200000*200000=40000000000=4*10^10 чисел. Ви впевнені в тому, що авторське рішення спроможне хоча б зчитати таку кількість чисел (не говорячи вже й про пам'ять)?

Поза форумом

 

#2 2018-12-18 13:09:58

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

Re: Запитання по задачі Minbus

Так, обмеження, очевидно, або неповні, або неадекватні. Схиляюся до першого варіанту smile

Як я вже писав у сусідній темі, для максимальних значень N та K і 9-значних значень часу приходу пасажирів на зупинку, вхідний файл буде майже 400 Гб. Навіть просто читання такого об'єму даних (без жодного аналізу) з RAM займе щонайменше секунд 10 на доволі швидкій системі (теоретична пропускна здатність DDR4-2666 в 2-канальному режимі якраз трохи менше 40 Гб/с).
Тобто швидше, ніж за 10 сек прочитати вхідні дані неможливо фізично.
Якщо ще врахувати, що читати, скоріш за все, доведеться не з RAM, а в кращому випадку з SSD, то отримуємо теоретичний мінімум уже не 10 сек, а бл. 7 хвилин. І знову таки, це для доволі швидкого SSD.
А якщо згадати, що нам треба не просто прочитати дані, а ще й проводити хоча б мінімальний аналіз (як мінімум - знаходити переводи рядків і/або парсити хоча б частину чисел), то реальний час на опрацювання макс. вхідного файлу буде близько години. Я дуже здивуюся, якщо авторське рішення зможе опрацювати макс. тест швидше, ніж за 30 хв.

Якщо значення часу (на які, до речі, обмеження теж не вказано) будуть не 9-розрядними, а 18-розрядними, то всі оцінки вище треба ще на 2 помножити.



Дуже дивує, що журі з якоїсь причини вважає, що обмеження правильні і повні.

Поза форумом

 

#3 2018-12-18 16:14:07

monx94
Олімпієць
Зареєстрований: 2018-10-10
Повідомлень: 16

Re: Запитання по задачі Minbus

Поддерживаю, хотелось бы увидеть реакцию жюри.

Поза форумом

 

#4 2018-12-21 18:43:47

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

Re: Запитання по задачі Minbus

Учасникам олімпіади запропоновано задачу. Виникли питання щодо обмежень - учасники отримали чітку відповідь. Тобто - розв'язується запропонована задача - повністю, або частково, відповідно підготовки учасника. В будь-якому випадку правило залишається незмінним - час на виконання теста =-2,5 часу від найшвидшого розв'язку, яке є  розпорядженні журі. Все. І прошу врахувати - олімпіада дистанційна з довготривалим туром.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt