Во время своих предыдущих статей я уже более-менее описал то, как проходит типичный тур обычной олимпиады по программированию изнутри. Кого-то заинтересовала эта внутренняя механика, а кто-то хотел услышать больше о непосредственно кодинге. В сегодняшней статье я расскажу о том, чем именно занимается команда во время тура, как и что делает, какие ухищрения применяет и что из этого выходит. О тренировках и о личных контестах я, пожалуй, расскажу попозже, хотя после этой статьи там и рассказывать будет почти не о чем.
Жду комментарии от действующих и бывших ACM-овцев, может почерпну какие новые тонкости и методы, ведь скоро мой последний сезон и хочется провести его крайне ударно.
Первая статья — про составление задач.
Вторая статья — про тестирующие системы.
Третья статья — про работу оргкомитета.
Четвёртая статья — про тур непосредственно.
Команда — это три человека. Больше — никак, меньше (по текущим правилам) — тоже. Нам с Мишей в прошлом сезоне ультимативно поставили просьбу искать третьего или никто никуда не идёт. Благо, Коля Orfest был свободен и мы устремились. Сыграться на уровень первых 3 команд нашего университета мы, увы, не успели, потому и не прошли в полуфинал в очередной раз. В этом году попытаемся починить взаимодействие в команде.
В лучших командах каждый участник в отдельности может взять весь тур (ну или большинство задач из него). В командах уровнем пониже зачастую отдельные участники специализируются на отдельных темах. Так у нас почти вся геометрия ложится на плечи Миши, а решать теорию чисел или какие комбинаторные измышления никто вперёд меня не лезет. Так, за счёт специализации на разных темах, можно получить команду, обладающую суммарно знаниями на уровне более сильных в персоналиях сборных.
Обычно в команде можно выделить 3 роли — кодер, математик и алгоритмист. Каждый из участников должен исполнять хотя бы 2 из них, а в идеале — все 3. Но не все случаи идеальны, поэтому иногда некоторые участники за тур не пишут ни одной строчки кода, а другие — не читают половину задач, в то время как команда достигает неплохого результата. Злоупотреблять этим не стоит, лучше уж пусть все знают всё =)
Минут за 10 до начала команду допускают к компьютеру. За машину садится самый быстрый кодер команды и набивает шаблоны на языках, на которых предполагается письмо, подстраивает IDE (настройка любимой перспективы в Eclipse с нуля уже настолько отработана, что доходит почти до автоматизма). Остальные подготавливают рабочее место — ручки, блокноты, нервы.
Появляются задачи, обычно в бумажном варианте. В идеале — 3 экземпяра, по одному на участника, но может быть и меньше. Две — минимум для удобной работы. Дальше задания жадно расхватывают два участника команды, не обременённые в данный момент клавиатурой и начинают искать «утешалку». В 90% туров, которые я писал, есть хотя бы одна задача, которую надо решать сразу, быстро, без вариантов и с первой попытки. После нахождения её (минуты за 2) алгоритмист садится к кодеру и в общих словах знакомит его с задачей, с сутью — чтобы тот не сильно утруждал себя чтением и переводом текста (на большинстве олимпиад текст на английском языке, потому лучше избежать лишних затыков). Далее кодер остаётся один на один с клавиатурой и условием данной задачи, а остальные двое устремляются разбирать весь тур.
Ребята прочитывают весь тур и ищут задачу, которую будут писать следующей. Далее, пока клавиатура занята, код аккуратно пишется в блокноте. Не схематично, а именно готовый для переноса код. Тогда, как только быстрый и грязный кодер справится с 1 задачей (предполагается, что он сумеет это сделать без внешнего вмешательства), кто-то из оставшейся двойки садится на его место, кодер идёт вдумчиво читать тур. Третий участник в этот момент отряжается наблюдать за написанием кода — парный кодинг в спортивном программировании очень полезен. Заодно этот участник составляет тесты на текущую задачу.
Да, чуть не забыл сказать. Примерно во время написания первой-второй задачи периодически мониторится состояние турнира, чтобы знать, что решают люди, дабы не уйти не в ту степь. Заодно составляется персональная очередь написания задач в команде, исходя из сложности/познаний/пожеланий.
Пока есть, что решать, решают именно то, что есть :) Обычно это происходит по следующей системе — один человек пишет, второй наблюдает, третий думает о другой задаче. + второй и третий составляют тесты для задачи первого, вручную просчитывая результат. Если всё плохо и все решаемые задачи закончились, то команда садится штурмовать. Технология мозгового штурма всем и так знакома, так что тут уточнять не буду.
При поступлении задач в «очередь написания» очень полезна следующая технология из командных математических турниров. Когда у кого-то в голове рождается разумеется правильное и самое хорошее решение, то он направляется к тому человеку, который над этой задачей не думал и объясняет ему решение задачи. Очень помогает при отсеве бреда и лажи.
Конец тура проходит 3 разными способами. Первый, самый красивый вариант — это часа за полтора-два до 5часовой отсечки, со всеми плюсами в рейтинге и гордо поднятой головой. Такое у нас было только на паре-тройке тренировок. А среди московских и питерских команд такое практикуется и на четвертьфиналах =)
Второй вариант — это в том случае, если писанина ещё есть и много, а времени нет и мало. Тогда голосованием по команде (примерно за час до конца тура) решается, какие задачи писать, в зависимости от уверенности в них и в вероятной скорости написания.
И третий путь — это «балет». Когда идей уже нет, а что-нибудь сделать хочется. Тогда начинают писать разные грязные лобовые решения, в надежде на то, что тайм-лимит обойдёт нас стороной. Может быть вообще цирк.
Так единожды на туре CBOSS мы решали задачу бинарным поиском в тестирующей системе. Задачу мы написали, причём довольно тупо и в лоб. В ней по эмпирическим соображениям было предположено, что если на первых ~2 миллионах у нас ничего не зациклится, то и далее ничего не сломается. Сломалось ограничение по времени. Поставили ограничение на полмиллиона — валится по точности. Делать было нечего, поэтому мы последовательными приближениями добрались до решения. Сдали попытки с 30-й
Во время написания туров часто применяются разные интересные и полезные трюки. Зачастую они выглядят удивительно для неопытных команд, но полезны всем.
Многие задачи кошерно решать предварительным просчётом. Как я уже писал раньше, 5 минут работы компьютера команды позволят решить задачу методом
Но зачастую задача вроде бы и считается прекальком или тупо в лоб, но для первого не хватает места в коде, а для другого — таймлимита. Тогда можно применить грязный хак номер один.
Вот пример задачи, решающейся именно таким способом. Мы с Колей начали решать её одновременно, он пошёл путём матана, сгенерировал хитрую табличку и как-то из неё вычислял решение в произвольной точке. Я же поступил прямолинейней, но не менее творчески. Цикл длиной 100000 за допустимое время выполняется, а 1000 предварительно просчитанных значений в код входит. Таким образом была просчитана сетка решений, а дальше считалось в лоб от ближайшего значения. Справился я быстрее, правда подход куда как менее научный и масштабируемый.
Методика, которую в нашу команду принёс Дима Ковчин. Применяется в основном на целочисленных задачах. Быстро, минут за 10 пишется генератор, который нагло просчитывает первые значений 20 целевой функции. Дальше лучшие умы команды садятся и методом глазуального анализа пытаются выявить общую закономерность. Зачастую закономерность по первым 2-3 значениям может быть ошибочной, значений 20 уже позволяют достаточно достоверно верить гипотезе. Просчёт руками по бумаге занимает куда больш�� времени. Стоит заметить, что методом Ньютона можно построить кривую хорошего порядка через любое количество точек, так что злоупотреблять методом не стоит.
Не знаю, как у команд других университетов, но у нас это уже пословица. Разные подлые и гадостные тесты мы всегда пишем в экселе (точнее в OpenOffice Calc). Эксель помогает нам в графическом анализе входных данных. А у весёлых ребят из СибГУТИ, с которыми наша команда постоянно делила 1 место среди лучших команд КВН в ACM =), даже какое-то время ходил слух, что NSU MOM и NSU NAN задачи в экселе решают и отсылают в тестирующую систему xls-файлы. Это, конечно, не так, но лучше, чем в экселе, строить макстесты для издевательств над задачей просто негде.
По намёку Orfest вспомнил и о том, что без гугла бывает сложновато. На крупных турнирах по типу Всесибирской олимпиады такую роскошь, конечно, в руки нам никто не даст, но на том же CBOSS воспользоваться этим можно невозбранно. В гугле и википедии можно освежить математические познания, дабы не возиться с выводом чего-то, невспоминаемого навскидку, а если уж очень хочется — дорваться и до готового алгоритма. Не стоит считать это панацеей от всех болезней, на многих турнирах внешний интернет запрещён как таковой, но иногда услуги веб-сервисов бывают полезными. Хотя бы даже для перевода непонятных слов, которые могут быть существенными при решении задачи. А на стадии «балета» это может свестись к очередному шоу.
Года 3 назад наша команда решала какую-то задачу про рассадку эльфов в упряжке Санта Клауса. Дело было уже под конец тура, градус кипения мозга был достигнут ещё раньше. Шоу началось с того, что переменные для массива оленей были именованы «loses» с комментарием «Лоси — они и в Лапландии лоси». Когда же было принято решение поискать в Яндексе алгоритм, коллективный разум родил лишь такой запрос: «эльфы олени рассадить». Тур на этом запросе был закончен, а в послужной список нашей команды добавился ещё один весёлый момент.
Пока, увы, темы про спортивное программирование у меня иссякли. Если кто подкинет идею, о чём можно написать ещё, буду очень признателен.
Жду комментарии от действующих и бывших 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» с комментарием «Лоси — они и в Лапландии лоси». Когда же было принято решение поискать в Яндексе алгоритм, коллективный разум родил лишь такой запрос: «эльфы олени рассадить». Тур на этом запросе был закончен, а в послужной список нашей команды добавился ещё один весёлый момент.
Пока, увы, темы про спортивное программирование у меня иссякли. Если кто подкинет идею, о чём можно написать ещё, буду очень признателен.
