Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By ruzana.miniakhmetova, 7 years ago, In Russian,

Друзья, недавно в нашем Хаброблоге мы опубликовали пост о том, что же вообще представляет из себя задача спортивного программирования. Изначально пост предполагал сравнение олимпиадных задач с задачами реальной разработки. Однако в финальном варианте мы решили исключить аналогии с промышленным программированием. Будет интересно почитать в комментариях примеры ваших подобных сравнений :)

"Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог ABBYY, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с олимпиадной задачи.

Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной. Например, в USACO героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи.

Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно, вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи :) Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно, чем на других.

Вернемся к обсуждению условия. Олимпиадные задачи очень формализованы:

  • строгий формат ввода/вывода, иногда даже с точностью до пробелов и переводов строк;
  • условия, как правило, имеют строгую однозначную трактовку. Вот уж где можно поучиться заказчикам в написании ТЗ!
  • строгие ограничения по времени выполнения и используемой памяти. В реальной разработке вам скорее скажут что-то в стиле «хотим, чтобы работало на таком-то железе и на такой-то ОС» или «слушай, твоя программа ест слишком много памяти». Куда реже можно услышать фразы типа «твоя программа должна работать не более 1,5 секунд» или «не смей использовать более 64 мегабайт памяти»;
  • все исходные величины строго ограничены.
  • Такая строгая формализация является оправданной. Все решения участников соревнований проверяются на некотором наборе тестов, который готовится жюри олимпиады и обычно заранее не известен участникам.

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

    Вообще существует два типа олимпиадных задач: «классические» и «эвристические». Классические задачи предполагают наличие точного строго доказанного решения. При решении эвристических задач участники соревнуются между собой, кто сможет получить лучшие ответы. Например, чье решение правильно распознает большее количество символов. Эвристические задачи обычно не имеют точных решений. Здесь они более всего близки к реальной разработке. Например, распознавание символов – вполне себе «эвристическая» задача.

    Существует немало способов оценки решений для «классических» задач:

  • задача считается решенной, если решение участника правильно сработало на всех тестах. Такая система оценки используется на ACM-соревнованиях.
  • за решение начисляются баллы, которые зависят от количества тестов, успешно пройденных программой. Такой подход часто используется на школьных олимпиадах: никто не уйдет обиженным с соревнования и получит хотя бы свои 0,5 балла.
  • тесты объединены в группы, за каждую из которых начисляется определенное количество баллов. Нужно заметить, что баллы за группу начисляются, только если решение правильно сработало на всех тестах из группы. Это разумный компромисс между справедливостью и удовлетворением участников. ABBYY Cup исповедует именно такую форму оценки решений;
  • иногда число баллов, полученных участником, зависит от времени, которое было затрачено на решение задачи. Например, такая система используется на Codeforces и Topcoder.
  • Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче, которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.

    Конечно, говорить об особенностях олимпиадных задач можно бесконечно. Мы осветили лишь самые главные моменты. Если у вас есть вопросы или комментарии – добро пожаловать в комментарии..."

     
     
     
     
    • Vote: I like it
    • +36
    • Vote: I do not like it