Олимпиадные задачи по программированию: что за зверь?

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

    ИТ-рестораны


    ограничение по времени на тест: 4 секунды
    ограничение по памяти на тест: 256 мегабайт
    ввод: standard input
    вывод: standard output

    В городе N. очень плохо с дорогами, общепитом и IT-инфраструктурой. Всего в городе n перекрестков, некоторые пары которых соединены двусторонними дорогами. Дорожная сеть состоит из n - 1 дороги, по дорогам можно добраться с любого перекрестка на любой другой. Да, вы правы — дорожная сеть образует неориентированное дерево.

    Недавно мэр города придумал способ, устраняющий проблемы с общепитом и IT-инфраструктурой, причем одновременно! Решено поставить на перекрестках города ресторанчики двух известных сетей кафе для IT-шников: «iMac D0naldz» и «Burger Bing». Так как владельцы сетей не дружат, категорически запрещается размещать рестораны двух разных сетей на соседних перекрестках. Есть и другие требования. Вот полный список:

    • в каждом перекрестке должен находится не более чем один ресторан;
    • каждый ресторан принадлежит либо «iMac D0naldz», либо «Burger Bing»;
    • каждая сеть должна построить не менее одного ресторана;
    • не существует пары перекрестков, которые соединены дорогой и на которых стоят рестораны разных сетей.

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

    Помогите мэру проанализировать ситуацию. Найдите все такие пары (a, b), что a ресторанов может принадлежать «iMac D0naldz», b — «Burger Bing», а сумма a + b максимальна.

    Входные данные

    В первой строке входных данных содержится целое число n (3 ≤ n ≤ 5000) — количество перекрестков в городе. Далее в n - 1 строке перечислены все дороги, по одной дороге в строке. Каждая дорога задана парой чисел xi, yi (1 ≤ xi, yi ≤ n) — номерами соединяемых перекрестков. Считайте, что перекрестки пронумерованы от 1 до n.

    Гарантируется, что заданная дорожная сеть представляет собой неориентированное дерево с n вершинами.

    Выходные данные

    В первую строку выведите целое число z — количество искомых пар. Далее выведите все искомые пары (a, b) в порядке увеличения первой компоненты a.
    Примеры тестов
    Входные данные

    5
    1 2
    2 3
    3 4
    4 5

    Выходные данные

    3
    1 3
    2 2
    3 1

    Входные данные

    10
    1 2
    2 3
    3 4
    5 6
    6 7
    7 4
    8 9
    9 10
    10 4

    Выходные данные

    6
    1 8
    2 7
    3 6
    6 3
    7 2
    8 1


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

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

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

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

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

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

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

    Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче, которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.

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

    Владимир Миняйлов, департамент технологий NLC,
    Рузана Миниахметова, группа образовательных проектов.
    ABBYY
    Решения для интеллектуальной обработки информации

    Комментарии 45

      +4
      В мое время на школьных олимпиадах (начало 90-х) все было куда проще. Ни ограничений (кроме системных), ни тестов, входные и выходные данные в общих чертах описывались, просто ручками проверяли (лишь бы не падала) и код читали.
        +2
        А я помню ещё некоторые олимпиады, где код ручками писали без компьютера.
          0
          А он хоть исполнялся? :)
            0
            Ой, не спрашивайте меня. Его так же проверяли, читая, потом перебивали в ГИВИ-Бейсик и проверяли на «компилябельность». Ну и оттуда со всеми вытекающими результатами, кому последнее место, кому предпоследнее и так далее.
            Трудные времена были… смута :)
              0
              Вспомнил. Все программы сдавались на бумаге, но рекомендовали сохранить файл на рам-диске, а я с одной что-то напутал (привык к магнитофонам), перезаписал кажется, в общем тоже с бумаги её набили и она «нескомпилировалась» — в итоге второе место по практике.
              +1
              В мою бытность в старших классах c БК-0010… Насчет исполнения кода школьников на бейсике из домашнего задания в тетрадке на настоящем компьютере в 98% случаях вопрос даже не стоял — препод просто впол-оборота проглядывал тетрадные листы «исходников» и зачеркивал косяк
              (по-современному — throw Exception красной ручкой).
              Нет, он был не злой человек, он делал и «свободные уроки», когда можно было делать с компом что угодно, хочешь играй, хочешь бейсик мучай. Но педагогическая методика необычная.
                0
                Исполнял в уме? :)
                  0
                  Да там ума много и не надо было… Я за препода проверял. Компы примитивные, бейсик тоже примитивный, я на Роботроне учился задолго до этого по методике «думай как компьютер шаг за шагом строка за строкой исполняй команды в уме».
                  Тогда не было понтов TPL, кучи процессоров, ядер, винды даже не было. Все было просто.
                    0
                    Ну хз. Я бывало в уме исполнял — один результат, а реально запускаю — другой… Неочевидное поведение, отсутствие документации и т. д.
                      0
                      Вы просто ошибались где-то в вычислениях.
                        0
                        Чаще все же неправильно представлял работу той или иной функции или оператора.
                          0
                          Видите, это отличный способ обучения. :)
              +1
              В некоторых регионах России школьный и муниципальный этап Всероссийской олимпиады по информатике до сих пор ручками (тур состоит чисто из теоретических задач, или 50/50) пишут. Ужас, если честно. Я занимаюсь программированием дистанционно с некоторыми школьниками из Астраханской и Архангельской области. Они мне рассказывают, как проходят у них первые два этапа олимпиады. Жаль, что в некоторых регионах так относятся к программированию…
                0
                Ну чисто теоретические и надо по идее руками писать. Тем более олимпиада по информатике != олимпиаде по программированию. У нас помнится два тура было в рамках областной: теоретический и практический. На теоретическом разве что калькулятор нужен был.
            +3
            Если у задачи нет решения на одном из языков программирования — это плохая олимпиадная задача. Обычную олимипиадную задачу можно решить на любом языке из данного набора и уложиться в ограничения. Это работа авторов.
              –2
              Это меня и расстраивает, что нет поправки на язык, далеко не всегда на python можно соревноваться с C в плане скорости выполнения, а на codeforce от этого зависит итоговый бал да и вообще выполнение задачи.
                +8
                С такими поправками не все просто. Появляется много вопросов.

                Какой именно коэффициент между решением на Python и C++? 5 раз? 20 раз? Дело в том, что это совсем не константа и каким бы его не поставили, одна из сторон окажется в преимущественном (возможно, значительно) положении. Как результат, цель достигнута не будет.

                Наличие таких поправок фактически значительно увеличит ограничения по времени во многих задачах, что приведет к увеличению времени тестирования. При большом количестве участников некоторые интересные задачи авторам придется откладывать из-за того, что они будут очень долго тестироваться. Короче, класс используемых задач уменьшится.

                Я легко могу представить в реальной практике требование вида «Ваш компонент должен обрабатывать миллион запросов не более чем за секунду», но поправка к нему вида «Ну ладно, если пишите на Python, то достаточно уложиться в 10 секунд» выглядит смешной.

                Отсутствие поправок обосновывается, что для каждой задачи в программировании важно подбирать правильный инструмент. Глупо реализовывать на языке с динамической типизацией высокоэффективный алгоритм с жесткими требованиями на производительность. Ну не подходят эти языки для таких задач. С другой стороны часто бывают задачи без жестких требований ко времени работы. Самые короткие и элегантные решения часто получаются на Python и Ruby.

                Здесь работает принцип, что выбирая инструмент, ты выбираешь его плюсы и минусы. Например, уровень поддержки сред языка Java значительно выше, чем языка C++. Статический анализ в Java встроенный в IDE позволит избежать некоторых ошибок, а так как код управляемый — любой выход за границу массива породит исключение и вы быстрее найдете ошибку. С другой стороны да, решения на Java обычно работают чуток медленнее.

                На Codeforces обычно ограничения по времени очень лояльны — неасимптотические оптимизации редко нужны, без проблем проходят эффективные решения на С/C++, С#, Java и других языках со схожей производительностью.
                  +1
                  Да это все верно, но все же если в конкурсе предполагается возможность участия на многих языках то хорошо бы иметь возможность пройти задания на каждом из них.

                  Пример:
                  Вчера я решал задачу в одном из ваших соревнований на python, алгоритм проходил тесты хорошо, но когда количество элементов массива выросло со 100 до 15000 и операций по ним с тех же 100 до 4000 моя программа ни как не могла уложиться в 2 сек, а считала около 20 — 30 сек хотя алгоритм работы был правильным, и различные оптимизации приводили лишь к небольшим изменениями времени работы и потребления памяти. Такую пропасть мне преодолеть не удалось. Я не C/C++ разработчик, но мне тоже интересны конкурсы подобные вашим, хорошая разминка для мозгов, но в таких условиях не вижу смысла в них принимать участие.
                    +1
                    Мне понравилось как сделали результаты тестирования в одном из курсов coursera. Там после прогона по всем тестам отдельно идет замер потребления памяти и времени выполнения при различном количестве входных параметров. Несколько прогонов с разным количеством и последующая интерполяция дают приблизительную оценку вашему алгоритму например O(N) или O(log N) и тд.
                    Хорошо бы и в спортивном программировании оценивать не абсолютные показатели время/память а «относительные» через сложность алгоритма. Это немного сгладит разницу между ЯП
                      0
                      да было бы неплохо )
                        0
                        Ну например в курсе по алгоритмам на той-же коурсере, для все заданий требуется уложиться в некоторое время выполнение. И в размер памяти. Таким образом проверяется правильность алгоритма.
                          +1
                          То есть, если я распределю массив на максимальные возможные ограничения, то оценка будет O(1)?
                            –4
                            Не совсем понял что вы собираетесь делать с массивом.
                            Не бывает О(1) есть O( C ) — если время работы не зависит от количества входных параметров. (соответственно и для памяти).
                              +1
                              Если вы посмотрите на определение «О большого», то поймете, что О( С ) и О(1) по смыслу одно и то же. Запись О(С) при этом избыточна, а О(1) намного более широкоупотребима.
                                0
                                Посыпаю голову пеплом. почему то всегда казалось что O( C ) пишется, как в случае со степенной сложностью O(С^n) где С константа
                          +1
                          Я практически уверен, что если требование в 2 секунды, а программа работает 20-30с, то алгоритм не правильный. В смысле, он правильно считает и проходит все функциональный тесты, но не оптимальный (не проходит тесты на производительность). Скорее всего у тебя там O(N*N) ассимптотика, а не O(N) или O(N*LogN).От языка программирования на данных в пределах описанных выше не может быть разница в 10-15 раз.
                            0
                            Быть может Вы и правы, буду пробовать дооптимизировать алгоритм уже вне codeforce, правда с данными я чуть чуть ошибся, сейчас пересмотрел 15000 эелементов массива 30000 операций 4000 запросов которые могут применить от 1 до 30000 операций над массивом, каждая операций может увеличить на n от 1 до 15000 элементов массива
                              0
                              В данном случае вы можете просто опубликовать ссылку на свое решение, а мы все вместе на него посмотрим и поймем в чем дело. Но повторюсь, эквивалентная реализация на Python вполне может отставать от С++ в 5-20 раз.
                                0
                                вот мое решение pastebin.com/FNByrpPU
                                  0
                                  Дайте ссылку вида codeforces.ru/contest/71/submission/3516879 (нажмите в решеточку на попапе с исходником) А сейчас еще надо догадаться, что за задача, и на каком тесте возникают проблемы.
                                      +3
                                      Я могу ошибаться, задачу я не решал. Но твое решение в лоб применяет запросы и для каждого запроса выполняет все отдельные операции над каждым елементом оригинального массива. Очевидно ассимптотика O(K*M*N).

                                      Так как задача олимпиадная, надо сделать что-нибудь другое :) Например просчитать массив сумм операций (Msum[0:m][0:n]. То есть для применения операций с m[i]->m[k] (как раз один запрос) надо прибавить к оригинальному массиву елементы массива Msum[k] и вычесть елементы массива Msum[i-1].
                                      Получается что-то типа O(M*N+2*K*N)

                                      C индексами и ассимтотикой я мог напутать, но что-то в этом виде наверно требовалось.
                                        0
                                        Ясно, спасибо, понял в каком направлении думать
                                          0
                                          Все равно слишком медленно. Там ограничения — N,M,K до 100.000, может не влезть в 2 секунды. У этой задачи есть решение за O(N + M + K).
                                            0
                                            Может быть, я не решал задачу, просто указал, что возможно предложеное решение правильно считает, но делает это медленно не из-за языка программирования который был использован.
                                          0
                                          Даже если перепишите на C++ — все-равно решение не пройдет временные ограничения.
                                            0
                                            да я уже понял что решение в лоб неправильное, спасибо
                          0
                          Составители задач не могут решать её на 20 языках. А лучше большой выбор языков, чем 100% гарантия наличия решения. Есть вроде стандартный набор языков, на которых проверяют решаемость — паскаль (самый популярный), c++ (классика), java (jvm иногда может выдать сюрпризы в плане производительности — как приятные, так и не очень) и python (очень тормозной)
                          0
                          ну. пример задачи решается вроде-бы просто
                          раскрасить вершины графа тремя цветами синий, красный и нейтральный, чтобы нейтрального было поменьше, а синий и красный не встречались на одном ребре
                          вырожденное решение (все вершины одного цвета) запрещено
                          значит берем один лист (или как там называется вершина с одним ребром из нее) дерева, красим в синий цвет
                          ее партнера оставляем «нейтральным»
                          все остальное дерево делаем красным. итак, а+b=n-1, а количество перекрестков в городе без ресторана (нейтральный цвет) равно одному
                          так как в дереве любая «нелистовая» вершина делит граф на две половинки, то решением будет количество нелистовых вершин
                          ну найти такие «внутренние вершины» в заданном графе
                            0
                            простите, все оказалось сложнее (выдергивание одной вершины делит дерево на несколько частей по кратности этой вершины — это не меняет ничего, но может усложнить), да и самая суть олимпиадной задачи — эффективно посчитать за 4 секунды.
                              0
                              Да, конечно. Наличие внутренних вершин степени более 2 делает задачу значительно содержательнее. Полагаю, без динамического программирования здесь не обойтись.
                                0
                                Для каждой внутренней вершины степени (или кратности? — я не помню теорию графов) N надо быстро посчитать {X1, X2… Xn} — количества вершин в графах, которые получатся после ее удаления. Потом cкомбинировать все возможные варианты Xi в две суммы — неоправданный геморрой.
                                Например, у нас в городе 5000 перекрестков. Один должен остаться без ресторана. В самом предельном случае решением будет
                                {1, 4998}; {2, 4997};… {4998,1} — это в том редком случае, когда город расположен вдоль Пан-Американского шоссе. С другой стороны, если город представляет из себя 4999-конечную снежинку — то ответ тоже такой же.

                            +2
                            Ссылка на ACM-соревнования никуда не ведёт.
                              0
                              Спасибо, fixed.
                              –4
                              Ага, а потом засудят за что-нибудь. Мы помним все, адоб.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое