featured for Як E-Olymp тестує розв'язки

Як E-Olymp тестує розв'язки

Mar 30, 2021

Сьогодні ми розберемось з тим, як E-Olymp тестує та оцінює розв’язки: що відбувається після того, як ви відправляєте розв’язок, як він запускається, як відбувається перевірка результатів та які вони бувають. Сподіваюсь, ця стаття допоможе вам краще зрозуміти, як працює система та спростить роботу з нею.

Ми також розглянемо, як працюють деякі нові функції на сайті, а саме набори тестів та інтерактивні задачі.


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

Коли ви натискаєте кнопку “Відправити” на сайті, ваш розв’язок зберігається у чергу тестування, звідки його отримує тестуюча система і починає тестування.

Черга тестування

Черга це такий додатковий буфер між сайтом та тестуючою системою. Завдяки йому, навіть якщо тестуюча система не встигає опрацьовувати всі розв’язки, сайт все одно може продовжувати працювати та приймати нові розв’язки. Черга буде зберігати їх, допоки одна з тестуючих систем не звільниться.

На E-Olymp постійно працюють декілька тестуючих систем, які постійно перевіряють чергу та отримують розв’язки для тестування.

Кожна тестуюча система має окремий виділений сервер та у кожен момент часу перевіряє тільки один розв’язок. Розв’язки ніколи не перевіряються паралельно на тому самому сервері, тому що це може вплинути на результат перевірки.

Зазвичай розв’язки не затримуються у черзі на довго, але іноді вони можуть зберігатись у черзі певний час. Коли розв’язків забагато, вони починають накопичуватись у черзі і ви можете бачити, що ваш розв’язок залишається у статусі “Очікує” певний час.

Підготовка та компіляція

Коли тестуюча система отримує розв’язок з черги, починається процедура підготовки та компіляції. На цьому кроці тестуюча система готує все необхідне для запуску та подальшого тестування.

Перш за все, тестуюча система створює пусту робочу теку та нове ізольоване середовище, де буде запускатись ваша програма. Далі, система створює файл з вихідним кодом програми та запускає команду компіляції. Наприклад, для C++ система створить файл source.cpp та виконає команду g++ source.cpp -o a.exe.

Цікаво, що для мови програмування C++ команда компіляції включає константи EOLYMP та ONLINE_JUDGE. Ви можете використовувати команду препроцесора #ifdef EOLYMP, щоб керувати тим, як один і той самий код буде компілюватись на вашому комп’ютері та у тестуючій системі.

Для інших мов програмування можна використовувати змінну середовища (environment variable) яка називається EOLYMP.

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

В залежності від мови програмування команда компіляції буде відрізнятись. Для мов програмування, які потребують компіляції у машинний код (чи байт код), команда компіляції створить відповідний бінарний файл. Для мов програмування, які не потребують компіляції, команда компіляції не виконується або просто виконує просту перевірку на синтаксичні помилки, наприклад, якщо ви забули поставити “;”.

Якщо файл з вихідним кодом не потрібен для запуску, він видаляється.

На цьому кроці, на сервері тестуючої системи є тека, у якій знаходяться тільки файли необхідні для запуску програми. Для C++ це просто бінарний файл a.exe, для PHP це файл source.php, а для Java це буде файл Main.jar.

Якщо компіляція завершилась успішно, система переходить до запуску вашої програми.

Запуск та перевірка результату

Всі задачі на сайті мають один чи декілька тестів. Кожен тест складається з файлу вхідних даних та файлу відповіді. Цей крок запускається для кожного тесту окремо у циклі. Тобто згадані нижче файли input.txt та answer.txt будуть відрізнятись для кожного тесту.

Спершу у робочу теку копіюється файл з вхідними даними input.txt, а потім виконується команда запуску.

Подібно до команди компіляції, команда запуску відрізняється для різних мов програмування. Наприклад, для C++, командою запуску є ім’я бінарного файлу a.exe, а для PHP команда виконання виглядає так php source.php.

Під час запуску тестуюча система спрямовує зміст файлу input.txt у стандартний потік вводу програми (stdin), а стандартний потік виводу (stdout) спрямовується у файл output.txt. Це означає, що замість вводу з клавіатури, ваша програма буде зчитувати дані з файлу input.txt, а все, що надрукує ваша програма, буде автоматично збережено у файл output.txt.

Це аналогічно до того, коли ви запускаєте команду через командний рядок ось так: a.exe < input.txt > output.txt.

Запис a.exe < input.txt > output.txt використовує синтаксис командного рядка. Насправді тестуюча система використовує системні виклики fork, щоб створити новий процес, dup2, щоб спрямувати потоки вводу та виводу і execvp для того, щоб виконати команду запуску.

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

На цьому кроці на сервері тестуючої системи у робочій теці, додатково з’явились файли input.txt та output.txt. Програма-розв’язок завершила виконання або була термінована операційною системою.

Після завершення виконання, тестуюча система отримує дані про використання ресурсів програмою-розв’язком. Ці дані включають код завершення (exit code), обсяг використаної пам’яті та час використання процесору.

З недавнього часу на сайті E-Olymp, ви можете окремо побачити час виконання та час використання процесору. Вони показані на сторінці розв’язку у колонках “Час виконання” та “CPU”.

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

З іншого боку, якщо ваша програма використовує більше одного ядра процесора, час виконання може бути менший за час використання процесору. Наприклад, якщо ваша програма використовувала 2 ядра процесора протягом 1 секунди, буде зараховано 2 секунди процесорного часу.

Тестуюча система обмежує використання процесору до 1 ядра, але деякі мови програмування (наприклад Java, C#) все одно можуть частково використовувати додаткове ядро.

Спробуйте відправити програму з інструкцією sleep та подивіться на час виконання та час використання процесору.

Наступним кроком запускається процес перевірки результату.

Перш за все, перевіряється час виконання програми. Система порівнює час виконання з лімітом і якщо його перевищено, тестуюча система зараховує результат “Вичерпано ліміт часу”.

Наступним перевіряється ліміт використання пам’яті. Якщо обсяг використаної пам’яті перевищує дозволений ліміт, тестуюча система зараховує результат “Вичерпано ліміт пам’яті”.

Далі перевіряється код завершення (exit code). За стандартом, код завершення програми повинен бути 0 у разі успішного виконання, та відмінний від 0 у разі помилки. Наприклад, якщо ваша програма спробує отримати доступ до не коректної області пам’яті, операційна система припинить виконання вашої програми з не нульовим кодом завершення.

Таким чином, якщо ваша програма матиме не нульовий код завершення, тестуюча система зарахує результат “Помилка виконання” та перейде до запуску наступного тесту.

Сама програма також може повернути не нульовий код завершення. Наприклад, якщо ви виконаєте return 1; в функції main на мові C++, ви побачите помилку виконання.

Нижче наведено короткий список типових помилок виконання. Якщо ви бачите результат “Помилка виконання”, перевірте пункти наведені нижче:

  • Программа повертає не нульовий код завершення: переконайтесь, що в функції main стоїть команда return 0;.
  • Программа використовує індекс масиву за межами його розміру: переконайтесь, що масиви правильного розміру та ініціалізовані.
  • Використання не ініціалізованого вказівника.
  • У інтерпритованих мовах програмування (PHP, Python, JavaScript та інші) помилки виконання можуть виникати через помилки у коді, наприклад виклик до не існуючої функції, спроба використовувати не ініціалізовану змінну, використання не існуючої бібліотеки, тощо.

Якщо ж код завершення - нульовий, почнеться процедура порівняння відповіді.

На цьому кроці система копіює файл з правильною відповіддю answer.txt у робочу теку і порівнює його з відповіддю output.txt.

В залежності від задачі, відповідь може перевірятись по різному. До кожної задачі закріплено спеціальну програму, яка виконує порівняння. Ця програма називається “чекер”.

У багатьох задачах відповідь порівнюється посимвольно, тобто кожен байт у файлі output.txt повинен збігатися з відповідним байтом в answer.txt. В таких задачах дуже важливо правильно відформатувати відповідь, додати всі необхідні символи пробілу та переходу на новий рядок.

У деяких задачах значення порівнюються відповідно до їх типу, тобто числа порівнюються як числа, а рядки як рядки. Це дозволяє порівнювати відповіді з певною точністю (наприклад, коли у задачі сказано виведіть число з 5 знаками після коми) або незважаючи на регістр букв у відповіді (наприклад, зараховуються відповіді YES, Yes та yes). В таких задачах, додаткові символи пробілу та переходу на новий рядок не будуть впливати на результат.

У задачах в яких може бути більше однієї правильної відповіді використовуються чекери, які написані спеціально для даної задачі. Чекери такого типу зазвичай вибудовують необхідні структури даних у пам’яті та проводять детальний аналіз відповіді. Наприклад, у задачі пошуку найкоротшого шляху в графі, чекер побудує граф та спробує перейти за маршрутом з відповіді.

В залежності від результату порівняння, перевірка може завершитись з результатом “Зараховано” або “Неправильна відповідь”. У деяких задачах програма перевірки може нараховувати часткові бали за результат “Неправильна відповідь”, але на сьогодні таких задач на сайті не багато.

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

Після запуску кожного тесту система відправляє результати тестування назад на сайт.

Після останнього тесту тестуюча система видаляє робочу теку та оточення і робить запит на отримання наступного розв’язку з черги.

Набори тестів

З недавнього часу, на сайті з’явилась підтримка для наборів тестів. Можливо ви бачили, що замість простого списку, деякі тести тепер об’єднані в набори, які перевіряються окремо.

Набори тестів – це групи тестів об’єднаних разом. Набори задаються автором задачі для того, щоб розділити задачу на декілька підзадач. Кожна з підзадач представляє частковий випадок для задачі. Наприклад, кожна підзадача може мати різні обмеження на значення вхідних даних, перша використовує дані з проміжку 1 до 100, а друга з 101 до 1000. Набір з номером 0 зазвичай представляє тести з умови.

Кожен набір тестів має налаштування оцінки та відображення.

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

Інша функція наборів тестів – приховування результатів тестування. В залежності від налаштувань задачі, тести набору можуть бути видимими або прихованими. Якщо результати тестування приховані, результати набору відображаються наступним чином:

  • Якщо всі тести набору зараховані, відображається результат “Зараховано” і максимальні значення з використання часу та пам’яті поміж тестів набору.
  • Якщо у наборі є тести, які не пройшли, відображається результат першого незарахованого тесту, його час виконання та використання пам’яті.

Додатково набори можуть мати залежності між собою. Автор задачі може налаштувати набори тестів так, що вам необхідно буде пройти всі тести одного набору, щоб почалось тестування іншого. У іншому разі набір буде відображено зі статусом “Заблоковано”.

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

Інтерактивні задачі

Для проведення останнього етапу Всеукраїнської олімпіади з програмування, на сайті також були реалізовані так звані інтерактивні задачі. Це спеціальні задачі в яких замість файлів input.txt та output.txt застосовується спеціальна програма інтерактор.

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

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

Результати тестування залежать від результату, який повертає програма інтерактор. Якщо ви надали правильну відповідь, програма інтерактор передасть сигнал “Зараховано” до тестуючої системи або сигнал “Неправильна відповідь”, якщо відповідь не правильна.

Якщо вам цікаво спробувати розв’язати інтерактивну задачу, ви можете спробувати відправити розв’язок до задачі #10435. Це одна з типових інтерактивних задач. В цій задачі програма інтерактор довільним способом “загадує” число, а ваша програма повинна відгадати його.

Задачі з пошуком відповідді (output only)

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

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

Прикладом такої задачі є задача з спонсорського туру Всеукраїнської олімпіади з програмування 2021. У задачі #10457 вам наданий файл, який описує “зоряне небо”. Вам необхідно знайти сузір’я, які відповідають критеріям, вказаним в умові задачі, і відправити їх координати у відповідному форматі.

Для того щоб відправити відповідь до такого роду задач, вам необхідно відправити розв’язок, вказавши мову програмування “Plain Text”. У такому випадку, під час перевірки, система просто створить файл з відповіддю output.txt.


Я сподіваюсь, вам сподобалася ця стаття і я дуже хотів би поділитись з вами ще чимось. Якщо у вас все ще залишились питання про тестування або вам цікава якась інша тема, Ви можете зв’язатись зі мною через форму зворотного зв’язку.