Сегодня мы разберемся с тем, как 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#) все равно могут частично использовать дополнительное ядро.

Попробуйте отправить программу 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.

---

Я надеюсь, вам понравилась эта статья и я очень хотел бы поделиться с вами еще чем-то. Если у вас все еще остались вопросы о тестировании или вам интересна какая-то другая тема, Вы можете связаться со мной через форму обратной связи.