Высокий старт. Олимпиада по программированию: от теории к практике

Как форма усиленного и интенсивного обучения информатике и программированию, олимпиады привлекают лучших студентов к высококвалифицированной работе в научных школах, к наукоемким задачам ИТ-индустрии. Помимо этого они позволяют выявлять и поддерживать развитие одаренной молодежи на разных уровнях обучения (школа, колледж, вуз). Наконец олимпиады – это учебно-экспериментальный полигон в области особо сложных разделов программирования и использования активных форм обучения, что ведет к повышению качества образования.

Открытая Всесибирская олимпиада имени И.В.Поттосина

Проводится Новосибирским государственным университетом, Сибирским отделением РАН и Институтом систем информатики СО РАН с 2000 года. Это один из наиболее эффективных инструментов выявления и подготовки одаренных молодых людей, вносящих затем существенный вклад в развитие отечественных современных компьютерных технологий.

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

Структура

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

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

Второй отборочный интернет-тур проводится по традиционным правилам международного студенческого чемпионата АСМ. Особое внимание при его проведении уделяется решению задач в крайне ограниченное и строго определенное время, что среди прочего способствует совершенствованию владения языками и техникой программирования.

Очный тур нацелен на искусство постановки задач и выбора методов решения. Здесь оценивается умение корректно поставить задачу на основании формулировки проблемы и ее контекста; умение проанализировать множество вариантов решений и, исходя из различных критериев эффективности, выбрать самый оптимальный. В рамках очного тура проводится две номинации. Первая – по стилю первого интернет-тура, вторая – по правилам АСМ ICPC.

В разные годы победителями олимпиады становились команды Московского, Новосибирского и Санкт-Петербургского государственных университетов.

В последней, VII олимпиаде приняли участие более 250 команд студентов ведущих вузов России и девяти стран ближнего зарубежья. Из них примерно половина – команды вузов Сибири и Дальнего Востока. Для участия в очном туре были приглашены победители первых двух туров. Ими стали представители университетов Москвы, Санкт-Петербурга, Петрозаводска, Ярославля, Екатеринбурга, Уфы, Томска, Тюмени, Абакана, Барнаула, Новокузнецка, Челябинска, Новосибирска – всего 42 команды.

Обзор задач

Олимпиады по программированию, в отличие от аналогичных мероприятий по многим другим предметам, развивают действительно необходимые для практической работы качества. Ведь любой программист часто оказывается в ситуации, когда необходимо выдать решение в крайне ограниченное и строго определенное время. Но, как правило, в реальности сама задача определена отнюдь не строго, а порою даже ошибочно, и ее нужно корректировать, исходя из контекста. Поэтому мы стараемся предлагать задачи разных стилей, в том числе отличающиеся от стиля задач олимпиады ICPC.

Задачи первого отборочного тура

Часть задач первого отборочного тура олимпиад с 2000 по 2005 годы состояли в разработке и реализации некоторой стратегии. Например, в 2000 году жюри предложило участникам написать программы, взаимодействующие в не известном им и меняющемся окружении. Были даны две игровые задачи, в которых правила для двух игроков отличаются: упрощенное рэндзю и задача преследования на двумерном многообразии с разными понятиями расстояния для охотника и жертвы. Временные ограничения на ход были чрезвычайно жесткими, чтобы исключить попытки действий переборными алгоритмами. Представленные участниками решения независимо компилировались и запускались на игру под управлением программы-арбитра. Итоги подводились по результатам турнира.

Правила игры рэндзю были упрощены таким образом, чтобы можно было почти всегда пользоваться методом потенциальных полей. В этой задаче требовалось переходить к перебору только в критической ситуации, поскольку давалось 0,01 секунды на ход и 30 секунд на размышление в критической ситуации.

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

В 2005 году была предложена задача, цель которой состояла в разработке стратегии управления беспилотными летательными аппаратами (БПЛА) в гонках. По ее условию каждая команда имеет десять БПЛА, а соревнования проводятся на трассе, представляющей собой бесконечную полосу. Цель – пролететь как можно дальше одним из аппаратов. На старте каждый из них имеет фиксированный запас горючего, расходуемого в процессе соревнований. Расход горючего на единицу пройденного расстояния различен на разных скоростях. Особенность задачи состояла в том, что требовалось разработать групповую стратегию, поскольку из-за аэродинамического взаимодействия при определенном взаимном расположении БПЛА получают возможность значительно экономить топливо. Поддержание оптимального взаимного расположения усложняется тем фактом, что при столкновениях БПЛА могут выйти из строя и прекратить участие в гонке.

Моделирование гонки происходит по ходам. В начале каждого хода программе игрока доступны координаты и скорости всех БПЛА, при этом она может задать расход топлива и ускорение для всех своих кораблей. Те же данные для БПЛА другой команды неизвестны. Затем программа жюри просчитывает движение всех аппаратов за один ход. С гонки снимаются медленно движущиеся корабли, рассчитываются ускорения, новые скорости и координаты остальных БПЛА.

Гонка заканчивается, когда не остается ни одного управляемого БПЛА. Для определения победителя и призовых мест между стратегиями команд проводился турнир, состоящий из серии матчей.

На стратегию налагались ограничения на максимальное время инициализации, время вычисления новых ускорений и размер используемой оперативной памяти. Для написания стратегий разрешалось использование языков C++, Java, Pascal и Modula 2.

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

Команды-участницы реализовывали различные стратегии. В простейших стратегиях каждый БПЛА летел сам по себе, не пытаясь взаимодействовать с другими кораблями команды. В других решениях учитывались аэродинамические воздействия, и аппараты выстраивались клином, чтобы попадать в положительные спутниковые вихри, таким образом экономя топливо. Корабли некоторых команд пытались подстраиваться в хвост клина соперника.

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

На VII олимпиаде в 2006 году темы задач первого отборочного тура были приближены к реальным проблемам, решаемым на практике. Идеи задач предложили компании Шлюмберже, СВсофт, Самсунг. В одной из задач, про определитель номера, требовалось по последовательности нулей и единиц с выхода компаратора распознать номер телефона. В другой нужно было представить картинку в виде набора символов заданного шрифта.

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

Решение задачи состоит в последовательном выделении самого раннего по времени импульса. Для этого сначала вычисляется уровень шума, затем находится самое раннее по времени возмущение, вычисляется импульс, соответствующий этому возмущению. После этого найденный импульс вычитается из сигналов всех датчиков, и для них находятся времена следующих возмущений.

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

Задачи второго отборочного тура и второй номинации очного тура

Задачи второго отборочного интернет-тура составлены в стиле АСМ ICPC. Они отличаются между собой по сложности и тематике. Жюри старается давать такие задачи, для решения которых необходимы знания из различных разделов математики (геометрия, теория чисел, анализ, теория вероятностей и так далее), применения методов динамического программирования или написания технически сложного кода. При их решении участники должны уметь использовать как классические алгоритмы, так и разрабатывать оригинальные, продумывать наиболее подходящие структуры данных.

Рассмотрим несколько различных вариантов.

В качестве примера задач на динамику и применение физических формул можно привести «Стритрейсинг», предложенный на интернет-тур V олимпиады в 2004 году: вдоль гоночной трассы расставлены знаки ограничения скорости, требуется рассчитать, за какое минимальное время машина с заданными показателями ускорения и торможения может преодолеть трассу. Алгоритм решения состоит из двух шагов. На первом шаге осуществляется проход с финиша трассы к старту, и для каждого знака вычисляется, с какой максимальной скоростью можно к нему подъехать. А потом, вторым проходом от старта к финишу, вычисляются оптимальные стратегии проезда интервалов между знаками и затрачиваемое время.

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

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

Другая задача – «Бильярд», использующая знания из теории чисел, была предложена жюри на очном туре III Всесибирской олимпиады. В ней заданы размеры бильярдного поля, в углах которого расположены лузы. Необходимо по заданному положению шара на этом поле и направлению удара определить, попадет ли шар в лузу и сколько раз перед этим он ударится о стенку. Все данные – целые. Удар о стенку поля считается абсолютно упругим, а скорость движения шара – постоянной. Решение этой задачи сводится к решению диафантовых уравнений. Дополнительную сложность здесь представляли ограничения на размер входных данных, с которыми нужно было работать, либо используя специальные типы данных, либо длинную арифметику.

На II интернет-туре VII олимпиады в качестве геометрической предлагалась задача «Алмаз». Суть ее в том, чтобы по координатам вершин найти объем выпуклого многогранника, у которого все грани треугольные. Для этого многогранник разбивается на тетраэдры, объемы которых находятся с помощью смешанного произведения. Из всех участников этого тура 14 команд пытались ее решить, но это удалось только 6 самым опытным командам.

Самой трудной с технической точки зрения стала задача «Добыча энергоресурсов», в основу которой были положены операции пересечения, объединения и дополнения многоугольников произвольной формы. Лишь одна команда из трех, пытавшихся решить эту задачу, смогла достичь успеха.

А вот самой популярной была признана задача про начисление штрафов, которая сводилась к выведению формулы суммы произведений по модулю. Ее решили 97 команд.

Среди задач, для решения которых требовалось знание классических алгоритмов из теории графов, была «СМС счастья». Идея ее состояла в том, чтобы найти гамильтонов цикл в специальном графе.

Традиционно задачи интернет-туров включаются в список олимпиадных тренировок в круглосуточной тестирующей системе.

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

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

Задачи первой номинации очного тура

Их темы связаны с распознаванием образов, архивацией, теорией расписаний, определением стратегии.

Например, девиз первой номинации первой олимпиады звучал так – «Точность и классика». Для решения была представлена задача коммивояжера на произвольном графе. Время на решение было ограничено 0.02n2 секунд, где n – количество вершин графа. Максимальные графы имели 400 вершин, при этом известно, что большинство расстояний связано неравенством треугольника.

Решающие тесты подбирались таким образом, чтобы заставить «провалиться» известные и описанные в доступной литературе приближенные алгоритмы. В частности, профессор Эдуард Гимади, автор ряда лучших приближенных алгоритмов, создал программу, генерировавшую теоретически наихудшие тесты. С ними справились лишь два первых призера. Но не менее трудными оказались контрпримеры, придуманные «вручную» членами жюри и привлеченными для данной работы студентами.

Девиз второй номинации был «Не точность и не классика». Задача, поставленная на второй день, не имела не только точного решения, но и точной постановки. По условию задачи требуется навести порядок в архиве ftp-сайта, в котором хранились картинки в формате JPG. Архив состоит из изображений реальных сцен – пейзажей, животных, людей, репродукций картин. Изображения были получены разными способами: цифровой фотографией, сканированием обычных снимков, оцифровкой видео- и кинокадров. Среди них много дубликатов – изображений одной и той же сцены с одного и того же ракурса или просто копий одного и того же кадра.

Основная же проблема при решении этой задачи состоит в том, что копии подвергались различной обработке: упаковке алгоритмом JFIF с различными параметрами, масштабированию, цифровому ретушированию и цветокоррекции, добавлению различных логотипов и рамок, обрезанию краев, преобразованию в 256 цветов с диффузией ошибки и без нее и повторному сжатию. Кроме того, оцифрованные кадры могли сканироваться с оригиналов различного качества в различном разрешении и с различными настройками сканера по яркости, контрастности и цветопередаче. Все это приводит к тому, что бинарное сравнение изображений (как упакованных, так и распакованных) ни в коем случае не может служить критерием их одинаковости.

Командам была дана случайная выборка изображений из архива (до 30 процентов его объема) и предстояло написать программу, которая просматривает весь архив и выдает список файлов, которые она сочтет дубликатами. Участникам предоставлялась библиотека libjpeg (распаковки, упаковки и других преобразований) для работы с изображениями формата JPG с полной документацией. Кроме того, можно было пользоваться программами Adobe Photoshop и ACDSee для просмотра и редактирования изображений.

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

Команда победителей решала задачу следующим образом: все изображения масштабировались до иконок 16х16 с градациями серого, яркость иконок нормализовалась. Затем все иконки попарно сравнивались. Вычислялась среднеквадратичная дисперсия результата вычитания двух картинок. Если дисперсия была ниже некоторого эмпирически определенного порога, значения, картинки признавались одинаковыми. Основное отличие между командами, занявшими первые три места, заключалось в сбалансированности подбора порогового значения.

В 2006 году участникам очного тура было предложено написать адаптивную игровую стратегию. Каждая команда пишет произвольное натуральное число. Затем числа всех команд открываются, и одинаковые числа вычеркиваются. Тот, у кого осталось наименьшее число, получает один балл. В случае ничьей все участники получают по одному баллу. Так один за другим проводятся раунды, пока какой-нибудь участник не наберет определенное количество очков. Он выбывает из игры и получает свое место в рейтинге, но игра продолжается. Остальные участники разыгрывают очередные места.

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

Заключение

Высокий научно-методический уровень олимпиады обеспечивается участием ведущих научных школ по информатике академических институтов РАН, в первую очередь Института систем информатики имени

А.П.Ершова СО РАН. В жюри и оргкомитете олимпиады принимают участие также и представители других вузов России, занимающих призовые места на олимпиадах по программированию: Московского, Санкт-Петербургского, Саратовского госуниверситетов, Санкт-Петербургского госуниверситета информационных технологий, механики и оптики.

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

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

Получив соответствующую подготовку, студенты поступают в магистратуру НГУ и аспирантуру НГУ и СО РАН, что позволяет удержать наиболее талантливую молодежь в научной сфере. В аспирантуре они уже развивают ИТ-технологии и одновременно начинают готовить себе смену. Так, например, победители старых олимпиад стали костяком тренерской команды по подготовке новых школьных и студенческих команд.

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

Татьяна ЧУРИНА, доцент НГУ, старший научный сотрудник ИСИ СО РАН; Елена БОЖЕНКОВА, старший научный сотрудник ИСИ СО РАН; Татьяна НЕСТЕРЕНКО, научный сотрудник ИСИ СО РАН, старший преподаватель НГУ, Новосибирск,