Pull to refresh

Олимпиады по программированию, взгляд из НГУ. Статья 5 — как играет команда

Reading time 6 min
Views 2.4K
Во время своих предыдущих статей я уже более-менее описал то, как проходит типичный тур обычной олимпиады по программированию изнутри. Кого-то заинтересовала эта внутренняя механика, а кто-то хотел услышать больше о непосредственно кодинге. В сегодняшней статье я расскажу о том, чем именно занимается команда во время тура, как и что делает, какие ухищрения применяет и что из этого выходит. О тренировках и о личных контестах я, пожалуй, расскажу попозже, хотя после этой статьи там и рассказывать будет почти не о чем.

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

Первая статья — про составление задач.
Вторая статья — про тестирующие системы.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.


Состав команды


Команда — это три человека. Больше — никак, меньше (по текущим правилам) — тоже. Нам с Мишей в прошлом сезоне ультимативно поставили просьбу искать третьего или никто никуда не идёт. Благо, Коля Orfest был свободен и мы устремились. Сыграться на уровень первых 3 команд нашего университета мы, увы, не успели, потому и не прошли в полуфинал в очередной раз. В этом году попытаемся починить взаимодействие в команде.

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

Обычно в команде можно выделить 3 роли — кодер, математик и алгоритмист. Каждый из участников должен исполнять хотя бы 2 из них, а в идеале — все 3. Но не все случаи идеальны, поэтому иногда некоторые участники за тур не пишут ни одной строчки кода, а другие — не читают половину задач, в то время как команда достигает неплохого результата. Злоупотреблять этим не стоит, лучше уж пусть все знают всё =)

Начало тура


Минут за 10 до начала команду допускают к компьютеру. За машину садится самый быстрый кодер команды и набивает шаблоны на языках, на которых предполагается письмо, подстраивает IDE (настройка любимой перспективы в Eclipse с нуля уже настолько отработана, что доходит почти до автоматизма). Остальные подготавливают рабочее место — ручки, блокноты, нервы.

Появляются задачи, обычно в бумажном варианте. В идеале — 3 экземпяра, по одному на участника, но может быть и меньше. Две — минимум для удобной работы. Дальше задания жадно расхватывают два участника команды, не обременённые в данный момент клавиатурой и начинают искать «утешалку». В 90% туров, которые я писал, есть хотя бы одна задача, которую надо решать сразу, быстро, без вариантов и с первой попытки. После нахождения её (минуты за 2) алгоритмист садится к кодеру и в общих словах знакомит его с задачей, с сутью — чтобы тот не сильно утруждал себя чтением и переводом текста (на большинстве олимпиад текст на английском языке, потому лучше избежать лишних затыков). Далее кодер остаётся один на один с клавиатурой и условием данной задачи, а остальные двое устремляются разбирать весь тур.

Ребята прочитывают весь тур и ищут задачу, которую будут писать следующей. Далее, пока клавиатура занята, код аккуратно пишется в блокноте. Не схематично, а именно готовый для переноса код. Тогда, как только быстрый и грязный кодер справится с 1 задачей (предполагается, что он сумеет это сделать без внешнего вмешательства), кто-то из оставшейся двойки садится на его место, кодер идёт вдумчиво читать тур. Третий участник в этот момент отряжается наблюдать за написанием кода — парный кодинг в спортивном программировании очень полезен. Заодно этот участник составляет тесты на текущую задачу.

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

Середина тура


Пока есть, что решать, решают именно то, что есть :) Обычно это происходит по следующей системе — один человек пишет, второй наблюдает, третий думает о другой задаче. + второй и третий составляют тесты для задачи первого, вручную просчитывая результат. Если всё плохо и все решаемые задачи закончились, то команда садится штурмовать. Технология мозгового штурма всем и так знакома, так что тут уточнять не буду.

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

Конец тура


Конец тура проходит 3 разными способами. Первый, самый красивый вариант — это часа за полтора-два до 5часовой отсечки, со всеми плюсами в рейтинге и гордо поднятой головой. Такое у нас было только на паре-тройке тренировок. А среди московских и питерских команд такое практикуется и на четвертьфиналах =)

Второй вариант — это в том случае, если писанина ещё есть и много, а времени нет и мало. Тогда голосованием по команде (примерно за час до конца тура) решается, какие задачи писать, в зависимости от уверенности в них и в вероятной скорости написания.

И третий путь — это «балет». Когда идей уже нет, а что-нибудь сделать хочется. Тогда начинают писать разные грязные лобовые решения, в надежде на то, что тайм-лимит обойдёт нас стороной. Может быть вообще цирк.
Так единожды на туре CBOSS мы решали задачу бинарным поиском в тестирующей системе. Задачу мы написали, причём довольно тупо и в лоб. В ней по эмпирическим соображениям было предположено, что если на первых ~2 миллионах у нас ничего не зациклится, то и далее ничего не сломается. Сломалось ограничение по времени. Поставили ограничение на полмиллиона — валится по точности. Делать было нечего, поэтому мы последовательными приближениями добрались до решения. Сдали попытки с 30-й

Ужимки и прыжки


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

Хитрый прекальк

Многие задачи кошерно решать предварительным просчётом. Как я уже писал раньше, 5 минут работы компьютера команды позволят решить задачу методом
read(a); write (res[a]);
Но зачастую задача вроде бы и считается прекальком или тупо в лоб, но для первого не хватает места в коде, а для другого — таймлимита. Тогда можно применить грязный хак номер один.

Вот пример задачи, решающейся именно таким способом. Мы с Колей начали решать её одновременно, он пошёл путём матана, сгенерировал хитрую табличку и как-то из неё вычислял решение в произвольной точке. Я же поступил прямолинейней, но не менее творчески. Цикл длиной 100000 за допустимое время выполняется, а 1000 предварительно просчитанных значений в код входит. Таким образом была просчитана сетка решений, а дальше считалось в лоб от ближайшего значения. Справился я быстрее, правда подход куда как менее научный и масштабируемый.

Генератор добра

Методика, которую в нашу команду принёс Дима Ковчин. Применяется в основном на целочисленных задачах. Быстро, минут за 10 пишется генератор, который нагло просчитывает первые значений 20 целевой функции. Дальше лучшие умы команды садятся и методом глазуального анализа пытаются выявить общую закономерность. Зачастую закономерность по первым 2-3 значениям может быть ошибочной, значений 20 уже позволяют достаточно достоверно верить гипотезе. Просчёт руками по бумаге занимает куда больше времени. Стоит заметить, что методом Ньютона можно построить кривую хорошего порядка через любое количество точек, так что злоупотреблять методом не стоит.

Excel — лучший друг программиста

Не знаю, как у команд других университетов, но у нас это уже пословица. Разные подлые и гадостные тесты мы всегда пишем в экселе (точнее в OpenOffice Calc). Эксель помогает нам в графическом анализе входных данных. А у весёлых ребят из СибГУТИ, с которыми наша команда постоянно делила 1 место среди лучших команд КВН в ACM =), даже какое-то время ходил слух, что NSU MOM и NSU NAN задачи в экселе решают и отсылают в тестирующую систему xls-файлы. Это, конечно, не так, но лучше, чем в экселе, строить макстесты для издевательств над задачей просто негде.

Фигурный гуглинг

По намёку Orfest вспомнил и о том, что без гугла бывает сложновато. На крупных турнирах по типу Всесибирской олимпиады такую роскошь, конечно, в руки нам никто не даст, но на том же CBOSS воспользоваться этим можно невозбранно. В гугле и википедии можно освежить математические познания, дабы не возиться с выводом чего-то, невспоминаемого навскидку, а если уж очень хочется — дорваться и до готового алгоритма. Не стоит считать это панацеей от всех болезней, на многих турнирах внешний интернет запрещён как таковой, но иногда услуги веб-сервисов бывают полезными. Хотя бы даже для перевода непонятных слов, которые могут быть существенными при решении задачи. А на стадии «балета» это может свестись к очередному шоу.
Года 3 назад наша команда решала какую-то задачу про рассадку эльфов в упряжке Санта Клауса. Дело было уже под конец тура, градус кипения мозга был достигнут ещё раньше. Шоу началось с того, что переменные для массива оленей были именованы «loses» с комментарием «Лоси — они и в Лапландии лоси». Когда же было принято решение поискать в Яндексе алгоритм, коллективный разум родил лишь такой запрос: «эльфы олени рассадить». Тур на этом запросе был закончен, а в послужной список нашей команды добавился ещё один весёлый момент.

Пока, увы, темы про спортивное программирование у меня иссякли. Если кто подкинет идею, о чём можно написать ещё, буду очень признателен.
Tags:
Hubs:
+3
Comments 16
Comments Comments 16

Articles