3.1. Практические задания с автоматической проверкой

Авторы: Алексей Толстиков, Александр Куликов

В этой статье вы познакомитесь с процессом решения задач по программированию: от понимания условия и проектирования алгоритма до реализации, тестирования и анализа результатов.

Ключевые вопросы статьи

• Какие шаги проходит программист при решении алгоритмической задачи?
• Как проверить корректность и эффективность своего решения до его сдачи?

Пять простых шагов для решения задачи по программированиюПять простых шагов для решения задачи по программированию

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

Итак, решение задач по программированию состоит из пяти шагов:

• Разбор условия задачи. Формулировка задачи указывает формат ввода и вывода, ограничения для данных ввода и использования памяти. От вас требуется написать быструю программу, которая уложится в ограничения по времени и использованию памяти.

• Проектирование алгоритма. Когда вы поняли, в чём состоит задача, начинайте проектировать алгоритм. Не забудьте доказать, что он работает правильно.

• Реализация алгоритма. Когда алгоритм спроектирован, его можно реализовать в вашем языке программирования.

• Тестирование и отладка. Тестирование — это искусство поиска багов. Отладка — это искусство устранения багов. Когда программа готова, приступайте к тестированию! А если обнаружите баг — исправьте его и протестируйте программу снова.

• Отправка программы на оценку. Когда программа протестирована, сдайте её системе оценки. Если вы увидите сообщение OK, значит всё в порядке. Если нет — возвращайтесь к предыдущим шагам.

Разбор условий задачиРазбор условий задачи

Для начала прочтите формулировку задачи. В неё входят описание вычислительной части, ограничения по времени и использованию памяти и несколько демонстрационных тестов. Убедитесь, что вы понимаете, как вывод соотносится с вводом в каждом из демонстрационных примеров.

Если ограничения по времени и памяти не указаны прямо в формулировке задачи, используются следующие значения по умолчанию.

• Ограничение по времени (с): 1
• Ограничение памяти: 512 Mb

Проектирование алгоритмаПроектирование алгоритма

Когда вы разработали алгоритм, докажите, что он работает верно, и попробуйте оценить время выполнения с помощью самых сложных вводных данных, указанных в секции об ограничениях.

Если ваш ноутбук выполняет около – операций в секунду, и максимальный размер набора данных в описании задачи , тогда алгоритм с квадратичным временем выполнения вряд ли уложится в ограничение по времени (так как ), в то время как решение с временем выполнения сможет это сделать. Тем не менее решение с  подойдёт, если и если .

Сработать могут даже решения с . Хотя для некоторых трудных задач в книге полиномиальные алгоритмы и остаются неизвестными, решение с временем выполнения может уложиться в ограничение по времени при  ниже .

Реализация алгоритмаРеализация алгоритма

Начните реализацию алгоритма на одном из языков программирования, которые поддерживаются нашей системой автоматической оценки. Напоминаем, это: C++, Java, Python3.

Для C++, Java, и Python3 есть примеры (авторские решения) с правильным решением задачи, учитывающие ее ограничения. Они тратят максимум 1/3 заданного лимита по времени и максимум 1/2 по памяти.

Тестирование и отладкаТестирование и отладка

Сдавать вашу реализацию на оценку, не проверив её, — это плохая идея!

• Начните с маленьких наборов данных и убедитесь, что ваша программа выдаёт верный результат со всеми предложенными наборами данных.
• Затем проверьте, сколько времени занимает обработка большого набора данных.

Оценка времениОценка времени

Для оценки времени выполнения имеет смысл реализовать ваш алгоритм как функцию — например, solve(dataset) — и потом реализовать дополнительную процедуру generate(), которая выдаст большой набор данных.

Например, если ввод задачи — это последовательность целых чисел длиной , тогда сгенерируйте последовательность длиной , передайте её функции solve() и убедитесь, что программа выдаёт правильный результат.

Проверка ограничивающих значений и экстремальных случаевПроверка ограничивающих значений и экстремальных случаев

Проверьте ограничивающие значения, чтобы можно было гарантировать, что программа правильно обрабатывает и короткие (например, из 2 элементов), и длинные последовательности (например, из 105105 элементов).

Если последовательность целых чисел от 00 до 106106 даётся в качестве ввода — проверьте, как ваша программа ведёт себя с последовательностью 0,0,…,00,0,…,0 или с 106,106,…,106106,106,…,106. После этого проверьте программу на случайном наборе данных.

Дополнительно советуем проверить экстремальные случаи: пустой набор данных, три точки на одной строке, дерево из одного узла и так далее.

Стресс-тестированиеСтресс-тестирование

Убедившись, что ваша программа выполняет все эти тесты, переходите к стресс-тестированию.

1. Реализуйте медленный, но простой и верный алгоритм.
2. Проверьте, выдают ли две программы одинаковый результат, — однако обратите внимание, что это не применимо к задачам, в которых вывод не уникален.
3. Сгенерируйте случайные тестовые сценарии, а также тесты с изменением параметров — например, с использованием только маленького диапазона больших чисел, строки с одной буквой a или только двумя разными буквами (вместо строк, использующих все буквы латинского алфавита) и так далее.
4. Подумайте, какие ещё тесты могут быть в каком-то смысле необычными.

Например, если вы генерируете графы, попробуйте генерировать древовидные, несвязные, полные, двудольные и так далее.

• Если вы генерируете древовидные графы, попробуйте генерировать пути, двоичные деревья, звезды и так далее.
• Если вы генерируете целые числа, попробуйте генерировать и простые, и составные числа.

Использование системы проверкиИспользование системы проверки

Когда вы закончили тестирование, сдавайте вашу программу на проверку.

1. Перейдите на страницу, где сдаются задания, и создайте новое выполненное задание.
2. Загрузите файл с вашей программой (обязательно загрузите исходный файл, а не готовое приложение).
3. После этого система оценки скомпилирует вашу программу и использует набор тщательно продуманных тестов, чтобы убедиться, что программа выдаёт правильный результат для всех тестов и что она укладывается в ограничения по времени и памяти.
4. В большинстве случаев оценка занимает около минуты, но в редких случаях, когда серверы загружены, может потребоваться больше времени. Пожалуйста, наберитесь терпения. После загрузки решения можно спокойно уходить со страницы.
5. В качестве результата вы получите обратную связь от системы оценки. Вам нужно получить вердикт OK — он обозначает, что ваша программа прошла все тесты.

Сообщения Wrong answer, Time limit exceeded, Memory limit exceeded означают, что программа не прошла тест по одной из этих причин.

• Если ваша программа даёт сбой, проходя один из первых двух тестовых сценариев, система оценки скажет вам об этом и покажет тестовый сценарий и вывод вашей программы. Это должно помочь вам использовать правильный формат ввода/вывода.
• В остальных случаях система оценки не будет показывать вам тестовый сценарий, который ваша программа не смогла выполнить.

Что дальшеЧто дальше

Теперь вы понимаете, как проходит полный цикл работы над задачей: от разбора условия до уверенного тестирования решения. Вы научились не только писать алгоритмы, но и проверять их корректность и производительность.

Далее — простейшая задача, с которой удобно начать практику. Вы увидите, как её можно решить на C++, Java и Python 3, и попробуете реализовать свой первый рабочий код.

Ключевые выводы статьи

• Решение задачи по программированию проходит через пять ключевых этапов: разбор условия, проектирование алгоритма, реализация, тестирование и анализ результатов.
• Оценка корректности и эффективности алгоритма помогает убедиться, что решение работает правильно и укладывается в заданные ограничения.
• Хорошее тестирование — это не просто проверка на примерах, а систематический подход: граничные случаи, случайные данные, стресс-тесты.