Путь чемпионов: почему программирование — спорт XXI века. Пётр Митричев — Легенда спортивного программирования Все эти соревнования индивидуальные

«В Facebook и Google мы не пойдем»: Почему одни из лучших программистов мира живут и работают в Екатеринбурге

Любопытное интервью с призерами чемпионата мира по программированию из Уральского федерального университета.

Мне вот всегда было интересно понять, почему в России (точнее, вообще на постсоветском пространстве) так популярны соревнования по программированию (наверное, термин, используемый в этой статье, подходит лучше: "спортивное программирование"), притом что на загнивающем Западе я о них долгое время и не знал даже, а когда знал, почему-то совершенно не тянуло. Это как какой-то отдельный мир совершенно. Я много лет активно участвовал в разных программистких сетевых сообществах, например, тусовался на рассылках различных опенсорс-проектов, встречался в реальной жизни с людьми иногда, но никогда при этом не заходила речь о TopCoder"е, скажем. О том, что TopCoder существует, я узнал из русского ЖЖ, по-моему (а узнав о нем, немедленно и срочно не пошел туда, не создал аккаунт и не стал участвовать). Это как-то очень забавно и интересно понять, почему.

Частично эту популярность объясняют некоторые реплики этого интервью, по-моему:

"А почему именно в этот раз УрФУ показал лучший результат? Звезды сошлись?"

Михаил Рубинчик: Команда у нас звездная. Олег, Леша и все остальные очень сильные ребята. Олег сейчас на шестом курсе, начал заниматься на втором, но уже к третьему у него был приличный уровень.[...]

"Тебе что ближе? Стартап? Или большая компания?"

Олег Меркурьев: Я вообще нигде не работал. И в ближайшие полгода работать нигде не собираюсь. Пойду в аспирантуру, наукой надо немного позаниматься, а то я вообще все свое время тратил на спортивное программирование.

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

"Давайте поговорим немного про сам чемпионат. Три человека в команде. Один компьютер. Почему один? Почему не три?"

Михаил Рубинчик: Жюри когда-то так решило. Это было тридцать лет назад.

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

[...]На ЧМ можно пользоваться принтером. Первый человек сел, написал какое-то решение, оно не заработало. Ему нужно найти ошибку. Читать с компьютера – это дорого, у нас же ресурс один. Поэтому распечатывают на принтере и читают на листочке.

Ну вот я не понимаю, как это может быть настолько привлекательным. Программирование - это созидательная деятельность. Не было программы, и вот она есть. Ты не мог что-то сделать с помощью компьютера, и вот ты можешь. Какая разница, это заняло 20 минут или 40? Это просто какой-то неинтересный аспект.

Нет, я могу себе представить ограничения, которые привносят спортивный азарт - но на уровне нескольких дней и действительно сложных, интересных задач. Типа соревнования Ludum Dare - написать игру за два дня. Или The ICFP Programming Contest , там дают три дня, и условия обычно крышесносные. Сравните это с заданиями ЧМ по спортивному программированию . Если соревноваться на минуты и секунды (еще и с одним компьютером на троих), то задания выходят вот такого рода - хитрое применение нескольких стандартных алгоритмов с какой-нибудь заковыристой "изюминкой".

В общем, странный это какой-то мир. Не обессудьте, те, кто от него тащится. Но не понимал и не понимаю.

Всё и очень сложно и в то же время просто. Для чего вообще существует спортивное программирование? Не "зачем им заниматься" а именно "почему оно существует как явление". Спорт вообще зачем нужен, взять хоть интеллектуальные, хоть физические виды. Кто-то скажет что для здоровья, развития, всё такое? Да в профессиональном спорте столько травм, что никакого здоровья не хватит. Для денег? Да там все за год становятся миллионерами. Истинная причина одна: желание победить, быть не таким как другие, быть лучше, совершеннее, значимее. Делать что-то великое для своего народа. Всё остальное - следствие. Если бы не это желание, порождающее соревновательность как таковую, не было бы и всего остального. Так же и здесь.

Что привлекает людей в начале. Какой-то интерес, новизна, эдакий "wow-эффект". Но это проходит. Для появления устойчивой мотивации необходимы более глубинные механизмы. Иначе, если и останется что-то, то хватит лишь для занятий "for fun".

Поэтому первое и основное, чем можно мотивировать начинающего - это возможностью стать лучшим в своём деле! Не просто кодером, каких тысячи тысяч, а чемпионом. Ведь каждый человек мечтает о чём-то большом и значимом. Может быть тот мальчик в детстве мечтал забивать голы в Лиге Чемпионов, а эта девочка - исполнять песни на Евровидении. Он пошёл в спортшколу, а она в музыкальную, но не задалось. Зато математика всегда шла на ура, но чего крутого в том чтобы быть ботаником задротом, решая заумные одному тебе интересные задачки? А какому-нибудь отличнику, мечтавшему стать космонавтом, родители, которым было плевать на его мечту, вдалбливали что космонавт должен как минимум знать по каким физическим законам летают ракеты, вот он и стал решать физику, тем более идёт на ура. А теперь все они поступили в ВУЗ и где-то внутри уже начинает тревожно звенеть мысль: "И что? Неужели я так и не сделаю в этой жизни ничего выдающегося?" Ведь, по большому счёту, любого выпускника-программиста очень даже можно заменить на работе. И вот он шанс: выступать за свой город, за ВУЗ, за всю Россию, побеждать, выходить в полуфинал, финал, делать что-то такое, что если этого не сделаешь ты, то никто кроме тебя не сделает.

Когда мы только начинали заниматься программированием, в 11 классе, нам раз за разом рассказывали как всё начиналось. Как впервые наши команды поехали на полуфинал. Как сдавали первую задачу. Как они на финал попали впервые. Как поехали за границу. Как бились на равных с лучшими умами планеты! И сердце замирало от желания стать хоть немного похожими на них. Мы смотрели таблицы финалов и перед глазами проносились названия: МИТ, Гарвард, Стенфорд! Каждый мечтает там учиться? Но вот что куда круче: разорвать все хвалёные иностранные команды к чертям! Как команда Тарасова в первом же матче суперсерии снесла сборную самых великих хоккейных профессионалов из Канады 7:3. Вот он, челлендж нашей жизни! И ведь это всё возможно! Это реальность! И это то, ради чего действительно стоит жить. И может быть в родном ВУЗе когда-нибудь такие же истории будут рассказывать новобранцам и о нас. И каждый будет мечтать быть на нас похожим. Именно так смотрят на олимпиаду новички.

Знаете, вот мы все привыкли к этим словосочетаниям: "полуфиналист чемпионата мира", "призёр чемпионата северо-восточной Европы" и т.д. Нас этим не удивить. Но для рандомного человека с улицы такие достижения - это же просто космос! А новички - это и есть люди с улицы. Так почему не использовать это? Ведь попадание на полуфинал чемпионата мира NEERC для многих контестантов так и остаётся на всю жизнь самый высокой взятой ими вершиной, самым громким завоёванным титулом. Это сейчас была не шутка.

У вас десять тысяч студентов, и вот она возможность стать одним из тех трёх элитных студентов, которые на главном в мире студенческом состязании будут представлять университет и город. Каждый из них уже, что называется, "один такой на много тысяч"! Элитное подразделение вашего ВУЗа.

Да, потом уже будут часы работы на износ, но кто говорил что чемпионом мира стать просто? Работа на износ пойдёт сама собой когда человек знает что идёт к достойной цели. Никто не пробежит марафон и не заберётся на Эверест без подготовки. Все это понимают. Но если пройдёшь это - будет у тебя что-то, за что ты сможешь сам себя уважать. Так же и тут. Не меньше.

Только вот никто не идёт в горы только ради лишений, а на марафон - чтобы потом неделю с кровати не встать. Никто не выходит на боксёрский ринг из любви к получению ударов по голове. Мазохистов мало. Всеми этими людьми движет что-то иное. Как и спортивными программистами. А именно: цель!

Так вот, если вы преподаватель игры на гитаре, то не стоит рассказывать ученикам о том как будут болеть пальцы и давать попробовать им сразу взять баррэ ("ага, не можешь? сложно будет!"). Зато можно рассказать как круто быть душой компании на вечеринке у костра и какими глазами будут смотреть на тебя девушки. Если вы пилот-инструктор СВС, то не стоит сразу грузить про то как оценивать, например, погоду. Попытайтесь передать ощущение полёта и романтизма.

Так же и здесь. Если будете объяснять сбалансированные деревья и в конце лекции скажете: "А олимпиадник это может написать," - вас никто не поймёт. Будете гонять по пятичасовым контестам и разборам - заскучают и уйдут, ищя свою детскую мечту в другом месте. Кто-то останется, но без энтузиазма. Так, задачки порешать это всё-таки интереснее чем какие-нибудь кроссворды разгадывать или в соцсетях в приложениях торчать. Будете сомневаться в полезности, в успехе - ваши сомнения передадутся новобранцам. Если же вы сами убеждены что ICPC круче, больше, значительнее всех научных студенческих конференций и форумов вместе взятых, что побеждать можно, что уже получалось (или не получалось, но все так этого ждут) - вам тоже поверят. Самое главное - поверить во всё это самому.

Действительно, очень хорошо когда есть конкуренция. Ещё лучше когда в ВУЗе уже есть финалисты, а есть молодые и зелёные. Молодняк будет спать и видеть первый контест, на котором они наконец-то, хоть на пять минут, но обойдут старпёров! Для совсем начинающих даже просто оказаться в мониторе выше них на минуту уже счастье.

Вот они основы мотивации. Это алгоритмические задачи, которые никто не умеет решать, когда в три ночи вскакиваешь с кровати, включаешь комп чтобы допилить код, проходишь наконец этот чёртов 80-й тест и получаешь accepted, а потом чувствуешь себя немного Менделеевым, которому озарение пришло во сне. Это год подготовки, всего пять часов, ради которых всё это было, и решающая задача, сданная на самой последней минуте. Это честь представлять свой город и страну в том деле, которое ты умеешь делать лучше всего. Ну а дальше - они и сами разберутся. Кто поступал только чтобы получить корочку и устроиться на нормальную работу всё равно вряд ли вам нужен. Все остальные, а, как писал Мирзаянов, приходят и математики и геймеры, если любят процесс, если найдут отголоски детской мечты, если не боятся трудностей, если готовы к игре, добро пожаловать.

Говорят, когда он появился на свет, к нему заглянул сам Дональд Кнут. Говорят, когда его пригласили работать в Google, он за 15 минут переписал весь поисковый алгоритм 16 раз. Говорят, он с улыбкой следит за прогрессом квантовых вычислений, так как при виде его числа от страха факторизуются сами. Но мы точно знаем одно: Пётр - настоящий бог спортивного программирования.

Факты

• Призер многочисленных чемпионатов, Пётр дважды побеждал в TopCoder и дважды занимал второе место в ACM ICPC.
• В свободное время Пётр ведет блог о регулярных контестах «Алгоритмические задачи для чайников»: petr-mitrichev.blogspot.ru.
• Сейчас Митричев работает в Google, где занимается качеством поиска. Также Пётр помогает в подготовке соревнований Google Code Jam.

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

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

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

На каком языке ты писал решения для задач?

На Java. В школе я писал на Pascal, потому что больше тогда ничего не знал. А потом, когда нужно было выбрать, на что перейти, Java оказался ближе к Pascal.

В условиях соревнования нужно написать программу за 20–30 минут, и она должна сразу работать правильно. Поэтому очень важно, чтобы язык не позволял сажать баги. C++, который использует большинство, отличается тем, что на нем довольно легко написать неправильную программу. Можно случайно забыть что-то, присвоить неправильный тип переменной, но все это будет как-то компилироваться и как-то работать. Скорее всего, не так, как ты ожидаешь.

В Java, если допустить ошибку или опечатку, программа, скорее всего, просто не скомпилируется. Здесь все строже, как и в случае с Pascal. Мне это показалось более подходящим. Обратная сторона медали - программы на Java часто работают раза в полтора медленнее, чем программы на C++. Иногда именно этих полутора раз не хватает, чтобы программа укладывалась в условие задачи.

Язык программирования каждый может выбирать сам, да?

Есть ограничения. Конечно, бывают разные соревнования... возьмем Google Code Jam, к примеру. Когда мы решали, как лучше его сделать, мы придумали, что можно работать на любом языке. Ты скачиваешь на компьютер входной файл с данными задачи, запускаешь на компьютере свою программу, а потом посылаешь на сервер результат. Какой у тебя на компьютере стоит компилятор/интерпретатор, тем и можно пользоваться. Минус данной системы в том, что компьютеры у людей разные. У кого-то компьютер в десять раз мощнее, чем у другого. Поэтому приходится создавать задачи, где неправильное решение от правильного по скорости отличается хотя бы в сто раз. Чтобы если у человека компьютер в десять раз медленнее, правильное решение у него работало, или на компьютере в десять раз быстрее неправильное решение все равно не работало. Поэтому нужны задачи с большим зазором между правильным и неправильным решением по скорости работы.

На Topcoder, Codeforces и ACM используется стандартная система, где ты посылаешь исходный код и они запускают его у себя на сервере. Здесь ты ограничен тем, что у них на сервере есть. Большинство участников, 70–80% используют C++, еще 20% используют Java, остальных языков очень мало. Это, мне кажется, такой цикл - новые люди, которые приходят на соревнования, начинают общаться с другими, более старыми участниками, те учат новичков тому, что умеют сами. В итоге новые люди тоже начинают пользоваться теми же языками. Так что эти два языка не то чтобы как-то особенно подходили для соревнований, просто так сложилось исторически.

То есть в жизни все это применимо? Ведь наверняка сложно найти работу, на которой эти знания пригодились бы. Да, можно пойти в Google или Яндекс, но прийти в какой-нибудь банк уже сложнее?

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

У тебя, наверное, была какая-то особая история, как ты попал в Google?

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

Спортивное программирование: «за» и «против»

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

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

А если попытаться придумать причину, почему не стоит тратить время на спортивное программирование?

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

Но что говорит практика, возможно ли, например, построить карьеру вокруг спортивного программирования?

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

Ты сам не задумывался о подобном? Нигде не участвуешь в жюри или как составитель задач?

Я пробовал учить школьников в 57-й школе, где сам учился. Пробовал готовить команды к олимпиадам. Сейчас в Москве эта тема очень активна - есть команды у МГУ, Физтеха, Высшей школы экономики. Но с преподаванием у меня как-то не сложилось.

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

Можно ли заработать на соревнованиях? Ведь за победу дают денежные призы.

Слишком маленькая вероятность. Один приз на десять тысяч участников?.. Я не назвал бы это заработком. Рассчитывать на это как на основной источник дохода... мне кажется, без шансов.

Но, как я уже сказал, есть много разных соревнований. Тот же Topcoder проводит соревнования по разработке программ. Допустим, нужно разработать компонент для программы, который делает то-то. По итогам оценивают, у кого что получилось, и лучшее используют - это решение покупает клиент и платит деньги тому, кто это решение сделал. Люди, которые занимаются этим full time, как я понимаю, зарабатывают довольно прилично.

Контесты сегодня

Расскажи подробнее, какие сейчас бывают соревнования, как все это происходит?

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

TopCoder - самый старый и известный сайт с еженедельными контестами. У них следующие правила. На решение трех задач отводится один час пятнадцать минут.

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

Дальше делают перерыв пять минут и еще пятнадцать минут отводится на поиск ошибок у других. Можно открыть решение любого человека, по любой задаче в твоей «комнате». «Комната» - это когда люди, участвующие в соревновании, случайно разбиваются на группы по двадцать человек. Разбиваются на «комнаты». Ты можешь открыть любое решение любого человека из твоей «комнаты». Если решение кажется тебе неверным, то можно вбить входные данные, на которых оно будет неправильно. И если оно действительно дает неправильный ответ, ты получаешь за это еще 50 баллов. Это, конечно, меньше стоимости задачи. Но это опять же делается для разделения людей. Основные баллы все-таки начисляют за решение задач, а не за поиск ошибок.

После всего этого задачи проверяются на тестах, которые готовило жюри. Если задача не работает, человек получает 0 баллов.

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

Но еще есть крупные, ежегодные контесты?

Да, кроме двух описанных соревнований, что проходят еженедельно, есть еще множество ежегодных соревнований. Обычно они устроены так: некая крупная компания (Google, Яндекс, TopСoder, IBM) проводит соревнование, с несколькими этапами отбора. Первые этапы проходят по интернету. А финальный этап уже проводится в каком-то конкретном месте, куда свозят всех финалистов. Таких соревнований всего штук пять-десять, но они длинные, так что все время происходит какое-то из них.

Все эти соревнования индивидуальные?

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

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

Да, на первом месте Гена Короткевич, очень умный студент из Гомеля, сейчас он учится в ИТМО. На Codeforces у меня в последнее время результат похуже, сейчас я шестой или пятый. Там тоже Гена на первом месте.

Наверное, играть в онлайне и офлайне - это совсем разные ощущения и опыт?

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

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

Бывает такое, что компании потом пытаются использовать в жизни наработки из сданных конкурсантами решений?

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

Соревнования со временем меняются? Становятся сложнее или, наоборот, проще?

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

О задачах и их составлении

Как составляют задания для соревнований? Есть составители, люди, которые уже умеют это делать, или это некий краудсорсинг, где каждый может предложить что-то свое?

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

Придумывать такие задачи - это ведь особый скилл?

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

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

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

Бывают и другие соревнования. У TopCoder это называется Marathon Match, и другие компании тоже проводят подобные контесты. Они устроены немного иначе. Это уже соревнования не по алгоритмам, а по решению приближенных задач. Когда нет точного решения и нужно придумать вариант как можно лучше. Такие соревнования длятся обычно две недели, месяц. Можно присылать разные решения и наблюдать, что, ага, вот сейчас мое решение лучше остальных на 20%.

«Лучше» - в смысле быстрее, использует меньше памяти и так далее?

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

Тот же Topcoder проводил соревнования вместе с NASA, и они говорят, что решения, которые им предложили, потом действительно адаптировали и использовали на МКС. Там решали какую-то конкретную задачу, кажется, как поворачивать солнечную батарею, чтобы та получала больше энергии.

С чего начать

С точки зрения подготовки хорошего алгоритмического программиста и участника разных контестов - как подготовить себя к такому? Если представить себя на месте старшеклассника или студентов первых курсов?

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

А если я беру задачу и вообще не знаю, с какой стороны к ней подойти?

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

Что нужно делать, чтобы набрать алгоритмическую базу? Вряд ли нужно прямо сразу кидаться читать Кнута.

Мне кажется, начинать нужно именно с задач. Уже потом, когда ты поймешь, что не можешь решить какую-то конкретную из них, в этих соревнованиях у каждой есть разбор. Можно прочитать решение, если справиться самостоятельно не получается. Например, в разборе указано, что в решении задачи используется некий алгоритм. Можно почитать, что это за алгоритм, где еще он применяется.Так лучше, чем читать по списку «ага, у меня есть алгоритм, который мне нужно изучить за лето». Лучше отталкиваться от конкретной задачи, которую ты не смог решить, потому что не знаешь какой-то конкретный алгоритм. Это более правильно. Запоминаешь лучше, мотивация получается сильнее. Такой способ изучения алгоритмов, наверное, дольше, чем по списку, но он приводит к лучшим результатам.

Если хочется «прокачать» себя именно по алгоритмам, есть какая-то литература, учебники?

Самый стандартный учебник - Кормен, Лейзерсон, Ривест с ослом на обложке. «Алгоритмы: Построение и анализ» называется. Не знаю, я довольно давно не учился, сейчас наверняка есть новые учебники, которые могут быть лучше. Но в мое время использовали Кормена. Кнут - это, скорее, этакий reference book. Если что-то нужно найти и оно нигде не находится, скорее всего, там оно будет. Но читать Кнута подряд... это довольно грустное занятие.

Нас часто спрашивают про спортивное программирование. Какой смысл имеют олимпиады? Насколько они важны при работе над реальным проектом? Если важны, то поздно ли начать заниматься данным направлением 11-класснику? Мы, конечно же, передали вопросы экспертам.

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

Начинать заниматься в 11 классе не поздно. Замечательный пример - человек, с которым в прошлом году мы вместе играли финал ACM ICPC. Он активно начал заниматься олимпиадами на 2 (!) курсе и добился очень даже неплохих результатов.

Повысить Понизить

Многое зависит от того, какой проект. Большинство (95%) проектов связаны с автоматизацией бизнес-процессов, графикой и т.п. В таких проектах олимпиадные навыки практически не играют роли.

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

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

Повысить Понизить

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

Начать участвовать в олимпиадах по программированию одиннадцатикласснику - не поздно. У меня есть много знакомых, которые занялись спортивным программированием только в университете и добились значительных успехов. Сам я принял участие в первой олимпиаде в конце первого курса и не считаю, что это было поздно. Если бы это случилось на последнем курсе, вот тогда бы я жалел.

Повысить Понизить

, технологический евангелист Microsoft, доцент МФТИ, МАИ, преподаватель детского лагеря JUNIO-R

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

Есть такое понятие – overqualification. Если вы будете слишком хорошо владеть теоретическими знаниями Computer Science, то вам будет скучно решать повседневные задачи, и полностью реализовать свой потенциал вы сможете только в крупных компаниях, типа Яндекс, Mail.ru, или тот же Microsoft. Поэтому круг интересных вам работодателей будет несколько уже, но и решаемые задачи будут намного интереснее и глобальнее.

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

11 класс - это немного поздно, поскольку надо слишком много успеть сделать для поступления в вуз, и будет сложно уделять олимпиадам достаточно времени. Но лучше поздно, чем никогда!

Повысить Понизить

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

Повысить Понизить

Отрывок из нашего , Станислав отвечает на вопрос «правда ли, что успехи на олимпиадах по программированию (математике) негативно коррелируют с работой в компании? Много ли у вас в команде олимпиадников?»

Напрямую олимпиады не помогут. Так же, как и знание матанализа не поможет человеку писать программы на Java или Python. Но олимпиадное программирование, если хотите, это как спортивное самбо. Оно не гарантирует успеха в уличных драках, мало того, есть много примеров, когда спортсмены-самбисты были жестоко покалечены именно в уличных драках, потому что там нет правил: там могут ударить ножом и втроем накинуться на одного. Но спортсмен-самбист намного быстрее становится именно бойцом, начав изучать боевое самбо (или другое рукопашное единоборство), чем человек, который с попкорном смотрит в экран монитора. Поэтому относиться к этому нужно ровно так: олимпиадное программирование - это хороший способ улучшить свой уровень. Человеку, который этим занимается, овладеть новой областью компьютерной науки или способом программирования будет легче. Это полезная деятельность, ее не стоит избегать. Если человек профессионально работает в компании, делает продукты, продающиеся широко, это становится как хобби. Человек, который работает в компании, производящий продукты для резервного копирования, наверное, за несколько лет становится профессионалом мирового класса в этой области. И олимпиадное программирование, если он начнет в нём участвовать, вряд ли ему сильно поможет, чтобы он стал на голову выше своих коллег. Но это полезное хобби, которое развивает нужные навыки.

А вообще, удивительно, как люди отказываются учиться. Когда я был молодым, пропаганда была очень мощная: надо учиться, это полезно, знание - сила, невежество - тьма. Не понимаю, почему у ваших ребят могут возникать такие вопросы. Знания не бывают лишними. В конечном итоге жизнь устроена так, что если человек понимает что-то очень-очень глубоко, ему легче увидеть, как работает какая-то совершенно, казалось бы, несвязанная с ним область. Всё, что мы делаем, в конечном итоге похоже. Так, я пребывал в иллюзии по поводу строителей, пока не стал делать свой первый ремонт. Первый и последний. Я обнаружил, что работа строителей в квартире очень похожа на работу коллектива программистов. И мало того, что все те проблемы, с которыми мы сталкиваемся, у строителей стоят в полный рост. И там еще хуже. Потому что средний уровень строителя ниже среднего уровня программиста, с точки зрения образования и общей толковости. Они так же ошибаются, у них есть баги, бывают как хорошие, так и плохие проектные менеджеры. Если плохой – могут, образно, и унитаз на потолок прикрутить, а потом делать вид, что так и было. Поэтому знаний избегать не надо. Возможно, конкретно данное знание мне никогда не пригодится, но если я что-то понял, понял почему так, а не иначе, мне оно пригодится хотя бы в виде аналогии.

Повысить Понизить