Олимпиады по спортивному программированию. Олимпиады по программированию — помогают ли они в реальной работе? Все эти соревнования индивидуальные

Вслед за результатами регионального полуфинала чемпионата мира ACM ICPC стали известны итоги Всероссийской олимпиады школьников по программированию. В стенах Университета ИТМО золотые медали вручили ребятам из Алматы, Астаны и Москвы. Петербуржцы поделили «серебро» с коллегами из Тбилиси, а «бронза» досталась ребятам из Екатеринбурга, Ижевска, Кременчуга и Витебска. Тренеры петербургских команд Андрей Лопатин и Андрей Станкевич, тьютор кафедры компьютерных технологий Университета ИТМО Лидия Перовская, декан факультета информационных технологий и программирования Владимир Парфенов и чемпионы мира по программированию разных лет рассказали, почему ребята из СНГ бьют все рекорды последние 15 лет.

Победители ACM ICPC из Университета ИТМО

Пора болеть за программистов

«За программированием будущее: в каждом доме есть огромное количество программируемых устройств, и эти технологии продолжают проникать во все сферы нашей жизни. Точно так же, как инженеры в Советском Союзе, программисты находятся сейчас на острие науки и техники. Соревнования по программированию становятся все более популярным и зрелищным видом спорта, и будущее у него очень многообещающее», — подчеркивает Андрей Станкевич .

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

Как отмечает тренер команды СПбГУ Андрей Лопатин , соревнования по программированию не только зрелищны, но и по-настоящему полезны. По его наблюдениям, современные чемпионы легко решают задачи, которые еще 10 лет назад казались нерешаемыми. Эффективность и скорость работы команд растет, а код упрощается, и это дает возможность тратить на разработку и отладку программ меньше времени. А это уже выгодно крупным IT-компаниям, которым важно удешевить производственные процессы.


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

Победы от и до

Как замечает Андрей Станкевич , спортивное программирование развивается волнообразно. Стратегий развития команд немало, но порой на результат влияет ключевой игрок. Например, во многом благодаря талантливому студенту Университета ИТМО Геннадию Короткевичу сборная вуза два раза становилась абсолютным чемпионом мира ACM ICPC. Однако лавры достаются и тем, кто придерживается долгосрочной стратегии, когда одна команда долгие годы оттачивает навыки и в конце концов заслуженно вырывается в топ — так команда СПбГУ стала абсолютным чемпионом ACM ICPC-2016. Поэтому нет ничего удивительного, когда какая-то из команд или кто-то из игроков уступают место в топе другим: это значит, что кто-то вырвался вперед благодаря долгому и упорному труду.


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

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

Как подчеркивает директор Центра развития IT-образования московского Физтеха Алексей Малеев, тем, кто хочет проявить себя в спортивном программировании, необходимо осознавать, что его ждут 4−5 лет настоящей пахоты. И при этом никто не может гарантировать, что через пять лет ты войдешь хотя бы в десятку ACM ICPC. Но эта тяжелая работа вкупе с сотрудничеством вузов позволяет выпускникам из России и стран СНГ выйти на глобальный рынок образования с реальным козырем. И именно поэтому российская школа программистов пользуется спросом во всем мире, уверен представитель МФТИ.

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


Экономический вопрос

«Сейчас вопрос с актуальностью спортивного программирования перешел в чисто экономический аспект. Все дело в том, что мы с вами находимся в некой критической точке, когда недолго осталось до нового витка развития информационных технологий. Это мир, в котором мы все скоро окажемся: полностью изменится банковская система, медицина, появятся беспилотные автомобили, не говоря уже о том, что многие профессии просто исчезнут — люди потеряют работу. Зато у программистов ее будет по-настоящему много. И это мы видим уже сейчас: спрос на них таков, что зарплаты физиков и математиков даже в США в два раза ниже, чем у программистов. И те страны, которые сейчас обладают высококвалифицированными кадрами в сфере IT, совершат рывок в ближайшие 10−20 лет» , — уверен Владимир Парфенов.

Именно поэтому нужны олимпиады. Чтобы выявлять лучших из лучших, талантов и тех, кто просто любит программирование и нуждается в поддержке, уверен Владимир Парфенов. Кроме того, талантливые дети — тот самый будущий актив — горят желанием соревноваться и проявлять себя с малых лет. Таких ребят, которые скоро изменят мир, в одной России 3 тысячи на 140 миллионов, и самое главное — увидеть тех, кто может составить им компанию. Ведь остальной мир не стоит на месте, добавляет декан факультета информационных технологий и программирования — за последние 15 лет колоссальный рывок уже сделал Китай, а США остаются на коне из-за развитой инфраструктуры.

«Наш современный программист начинает работать сразу на четвертом курсе, если не идет в науку, где, увы, зарплата пока меньше. При этом ему поступает масса предложений от работодателей. Конечно, если мы говорим о Петербурге, наши 400−500 IT-компаний стараются создавать что-то новое, и в них стоит идти. Нередко те, кто начинает работать в крупных компаниях вроде Google, возвращаются на родину, иногда с жалобами. Ведь одно дело, когда вы сидите в красивом городе Санкт-Петербурге, и совсем другое, когда находитесь в деревне под названием Кремниевая долина…» , — смеется преподаватель.


Допинг

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

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

  • участвовал в финале ACM ICPC;
  • выступал от белорусского университета;
  • уже закончил обучение в вузе;

сделали выборку. Получился список из двадцати одного финалиста АСМ ICPC от Беларуси. Нам удалось связаться с большинством из них и задать три простых вопроса:

  1. Какое ваше текущее место работы и какова позиция/суть выполняемой работы?
  2. Почему именно эта компания/занятие?
  3. Какие планы на будущее, каким его для себя видите? Куда хотелось бы двигаться?

Кто из них выбрал управленческую карьеру, кто остался верен спортивному программированию, а кто все-таки разрабатывает поисковые алгоритмы, вы узнаете из «прямой речи» белорусских финалистов АСМ ICPC.

Иван Михневич (ACM ICPC 2000)

  1. Wargaming Public Company Limited, Director.
  2. Это результат роста в группе компаний с самого начала трудовой карьеры.
  3. Реально уже все это надоело и пора начинать новую карьеру, на новом месте, в новой области (скорее всего, не ИТ).

Сергей Степанцов (ACM ICPC 2000)

  1. В настоящее время я работаю в должности Vice President Business Development в компании Intetics Co.
  2. Большая часть моей карьеры связана именно с этой компанией, здесь я успел попробовать себя в самых разных ролях: начал как специалист по тестированию, а также поработал программистом, руководителем проектов, руководителем производственного подразделения. И в итоге пришел к специализации в развитии бизнеса.
  3. Всё еще не чувствую себя старым настолько, чтобы перестать саморазвиваться:). Думаю, что будущее деловой части моей жизни еще порадует множеством увлекательных поворотов.

Владимир Танкович (ACM ICPC 2000, 2003)

  1. Сейчас в Microsoft занимаюсь алгоритмами Computer Vision для Kinecta. До этого был в search relevance.
  2. В этой компании с 2005. Они меня привезли из РБ, и переходить пока смысла не было. В эту команду перешел потому, что она позволяет заниматься научной работой, которая идет не в сборник статей, а в готовый продукт.
  3. На будущее конкретных планов нет. В ИТ деньги не проблема и в Минске, и тут. Пока что мне очень интересно разбираться с Machine Learning и AI. Тут получается, что я занимаюсь почти все время чем хочу, а мне за это еще и хорошо платят. То есть ближайшие 1—2 года я буду заниматься тем же, а дальше посмотрим. Опыта получаю много и, если будет идея, как его надежно применить, то попробую стартап.

Алексей Кирковский (ACM ICPC 2002, 2005)

  1. НТ ООО «ЛюксСофт», инженер-программист 2-й категории.
  2. Очень хотелось пойти в известный московский бодишоп ЛюкСофт (Luxoft), так как с детства мечтал заняться автоматизацией люков, но не заметил одну букву и попал в белорусский ЛюксСофт (LuxSoft). Там не глядя подписал какие-то бумажки, и теперь вот работаю по 20-летнему контракту на фиксированную зарплату в белорусских рублях, которой хватает только на бензин.
  3. Планирую выполнить норматив по количеству строк в минуту и стать инженер-программистом 1-й категории. Затем получить КМС по программированию, который мне тут присвоят, если не будет ни одного опоздания на работу за весь срок действия контракта.

Алексей Данченко (ACM ICPC 2002, 2005)

  1. НТ ООО «ЛюксСофт». Инженер-программист. В последнее время занимаюсь разработкой предметно-ориентированного языка программирования для нашего продукта.
  2. Возможность поработать с друзьями над реализацией интересной идеи.
  3. Продолжать получать удовольствие от жизни.

Евгений Гончар (ACM ICPC 2003)

  1. Google Switzerland (Zurich), Senior Software Engineer. Работаю на одном из проектов инфраструктуры веб-поиска.
  2. С детства любил программировать.
  3. Хотелось бы продвинуться в игре на электрогитаре и еще раз съездить в Новую Зеландию.

Иван Метельский (ACM ICPC 2003, 2004)

  1. TopCoder, Inc., Marathon/Algorithm Problem Coordinator. Запуск Marathon и Algorithm Competitions на TopCoder.
  2. В каком-то смысле просто так вышло. Если более серьезно — хороший доход, относительно интересная работа, сложно найти лучшую альтернативу.
  3. Планы на будущее — не сильно важно куда, но куда-то в сторону несколько меньшей занятости и большей свободы действий. Возможно, какой-то свой бизнес, совершенно не обязательно в ИТ.

Виктория Лебедь (ACM ICPC 2004)

  1. Я была и осталась математиком. В команде была единственным человеком, не прикасавшимся к компьютеру:) Выполняла всю «побочную» работу. Живу и работаю в Париже. Сейчас у меня временная позиция в университете Paris 7 — научная деятельность и преподавание. Недавно получила PhD.
  2. Это занятие потому, что оно даёт редкую возможность сохранить личную и творческую свободу.
  3. Планов на будущее стараюсь особо не строить. Опять же, чтобы не ограничивать себя какими- то рамками и не подставлять себя самолично под груз ожиданий, надежд и прочего. Я отлично представляю продолжение начатого пути в университетско-научной среде, но не закрываю дверь для иных вариантов.

Максим Осипов (ACM ICPC 2004)

  1. VironIT, директор. Управление бизнесом (преимущественно не операционное, а направленное на изменение процессов продаж, разработки, качества выполнения работ и т. п.)
  2. Компания VironIT, потому что это моя компания, я владелец. Это занятие (неоперационное управление), потому что придумывать, как развиваться бизнесу — самое интересное для меня.
  3. Развивать свою компанию, перейти, в том числе, на продуктовую модель, завести семью, детей. Будущее вижу интересным, непростым, но однозначно позитивным.

Павел Иржавский (ACM ICPC 2007, 2008)

  1. Преподаватель БГУ, математик-программист в «Ориентсофте», преподаватель в ШАД, аспирант (формально это учёба, но по факту ближе к работе).
  2. В каждом занятии есть и интересное, и полезное (помимо того что все они приносят доход:)), и простое, позволяющее немного отдохнуть, и сложное, позволяющее мне развиваться. Мне кажется, я становлюсь в целом менее эффективным, когда начинаю заниматься одним и тем же, грубо говоря, по 8 часов в день, а ежедневная смена рода деятельности позволяет мне быть на пике.
  3. В планах на будущее существенных изменений нету:)

Владимир Керус (ACM ICPC 2007, 2008)

  1. ЕПАМ. Ведущий инженер-программист отдела мобильных разработок. Занимаюсь разработкой приложений под Android.
  2. Люблю изучать новые вещи, и в текущей компании получается безболезненно менять профиль и находить нужных людей-учителей.
  3. Дерево уже посадил, коплю на строительство дома, планирую завести малышей (в идеале — свой состав «Барселоны»).

Сергей Тихон (ACM ICPC 2009)

  1. EPAM Systems, Lead Software Engineer. Архитектор/разработчик специальных проектов.
  2. Дружный, сильный коллектив, интересные задачи, неплохие возможности профессионального роста.
  3. Работа в ИТ, но на границе с наукой, работа по внедрению Data Science в реальные приложения и сервисы (машинное обучение, обработка натурального языка, поисковые технологии, моделирование). Пропаганда, распространение и внедрение функционального программирования (веду блог по F#).

Алексей Лобанов (ACM ICPC 2010)

  1. Компания «Яндекс», разработчик в «Яндекс.Картах». Параллельно с этим учусь в аспирантуре БГУ и работаю ассистентом на кафедре ДМА ФПМИ (веду практические занятия по курсу «Алгоритмы и структуры данных»).
  2. Почему «Яндекс»: здесь есть интересные задачи (в том числе и сложные, наукоемкие, алгоритмические), комфортные условия работы и отличный коллектив. Почему ФПМИ БГУ: считаю, что важно передавать свои знания следующим поколениям студентов.
  3. Планы на будущее: успешно доучиться в аспирантуре и постараться защитить кандидатскую.

Алексей Толстиков (ACM ICPC 2010)

  1. БГУ, ассистент кафедры вычислительной математики, окончил аспирантуру, преподавание курса « Параллельные и распределенные вычисления » (практика). Яндекс, куратор академических программ, руководитель минского филиала Школы анализа данных (+преподаватель в ней), разработчик поиска.
  2. Одним предложением не смогу, но потому что: «Мне это нравится!»
  3. Нечего особо сказать. Двигаюсь во всех этих направлениях.
«В Facebook и Google мы не пойдем»: Почему одни из лучших программистов мира живут и работают в Екатеринбурге

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Говорят, когда он появился на свет, к нему заглянул сам Дональд Кнут. Говорят, когда его пригласили работать в 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. Но олимпиадное программирование, если хотите, это как спортивное самбо. Оно не гарантирует успеха в уличных драках, мало того, есть много примеров, когда спортсмены-самбисты были жестоко покалечены именно в уличных драках, потому что там нет правил: там могут ударить ножом и втроем накинуться на одного. Но спортсмен-самбист намного быстрее становится именно бойцом, начав изучать боевое самбо (или другое рукопашное единоборство), чем человек, который с попкорном смотрит в экран монитора. Поэтому относиться к этому нужно ровно так: олимпиадное программирование - это хороший способ улучшить свой уровень. Человеку, который этим занимается, овладеть новой областью компьютерной науки или способом программирования будет легче. Это полезная деятельность, ее не стоит избегать. Если человек профессионально работает в компании, делает продукты, продающиеся широко, это становится как хобби. Человек, который работает в компании, производящий продукты для резервного копирования, наверное, за несколько лет становится профессионалом мирового класса в этой области. И олимпиадное программирование, если он начнет в нём участвовать, вряд ли ему сильно поможет, чтобы он стал на голову выше своих коллег. Но это полезное хобби, которое развивает нужные навыки.

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

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