Что такое спортивное программирование и как оно работает
Об эксперте: Андрей Райгородский, доктор физико-математических наук, профессор МФТИ, Директор Финала ICPC в Москве, Директор Физтех-школы прикладной математики и информатики МФТИ.
Что такое спортивное программирование
Представьте себе коридор с бесконечным рядом запертых дверей. Если превратить их открывание в задачу с алгоритмом, у нее будет несколько решений.
Классическому, «промышленному» программисту поручат отлить лом, вскрывающий как можно больше дверей, и дешевый в производстве. А задача спортивного — понять, какая отмычка взломает все за пять минут. К слову, спортивные программисты встречаются в 70 раз реже.
Ежегодно программисты со всего мира (главным образом, студенты) встречаются на командных и индивидуальных турнирах. Самые престижные: старейший в своем роде чемпионат ICPC (International Collegiate Programming Contest), конкурс Google Code Jam, олимпиада IOI.
Конечно, замки там никто не вскрывает — обходятся математикой и написанием кода. Задания финалов в разы сложнее примера выше, а время жестко ограничено. Да и по накалу страстей ИТ-чемпионаты порой дают фору Олимпийским играм.
Особенности и практический смысл ИТ-спорта
Участникам соревнований есть за что бороться: на кону не только денежные призы, но и вакансии в крупнейших корпорациях с самыми высокими зарплатами.
От спортивных программистов требуется не только решать алгоритмические задачи, но делать это быстро и оптимально. Такие навыки даются непросто: так, подготовка к чемпионату ICPC требует регулярных тренировок по 4–5 часов, занятий с личным тренером, участия в сборах и отборочных турах.
Не следует думать, что речь о какой-то отдельной науке. Основы традиционного и спортивного программирования едины, и поначалу функция соревновательного элемента — заинтересовать подростка. Олимпиады дают мотивацию к учебе, позволяют поступать в вузы без экзаменов — а уже в вузах программисты приобретают более фундаментальные навыки. Среди них умение создавать решения не на пять минут, а на годы вперед для нужд конкретной индустрии.
Олимпиадный опыт не снижает квалификацию, но для полноценной карьеры одних спортивных навыков недостаточно. Преподаватели МФТИ уже много лет избавляют олимпиадников от их «профессионального синдрома»: заботясь только о быстродействии кода, студенты жертвуют универсальностью и прибегают к сомнительным «костылям». А в промышленных программах «костыли» недопустимы.
Говоря проще, программист должен не только «изобретать, как Тесла», но и «продавать, как Эдисон».
Что изменилось за последние годы
Программирование постепенно превращается в профессиональный спорт. Подготовка стала массовой, в отрасль пришли спонсоры: 5–10 лет назад нельзя было вообразить количества открытых сейчас кружков и курсов подготовки. Программа постоянно усложняется: скажем, финалисты 2010-х годов уже не смогут повторить свой успех. На задачах финалов прошлых лет сегодня тренируют новичков.
Как и олимпийский спорт, современные чемпионаты по программированию все сильнее походят на «битвы титанов», где счет идет на секунды. Но такое сходство — лишь следствие повышения ставок. Повышаются они потому, что за ИТ-чемпионатами пристально следят все крупнейшие компании отрасли.
Что нужно бизнесу
С каждым годом карьерные возможности в секторе растут. Но суть не в том, что ИТ-гиганты встают за медалистами в очередь, — такое «коллекционирование» чемпионов для них просто дело принципа. Когда подготовка стала доступна всем, а число олимпиадников выросло в разы, те перестали быть штучным товаром — и стали рыночным.
А значит, спортивной натасканности и медали больше недостаточно для карьеры. Бизнесу нужны не только «теслы», но и «эдисоны». И тех, и других на рынке хватает — поэтому встает вопрос «а что я умею помимо решения задач?».
И тогда судьбу специалиста решают два качества: soft skills и кругозор. Первый термин объединяет эмоциональный интеллект, умения работать в команде, адаптироваться к новым задачам. Стереотип «айтишник — значит интроверт» сильно вредит индустрии, ведь успех разработки — это успех команды и коммуникации между ее членами.
А кругозор программиста — это его способность решать стратегические задачи. Это знания продвинутой математики, логики и профильных дисциплин; это практический опыт; это понимание процессов в индустрии, где он занят, какой бы та ни была. Такой кругозор — продукт всестороннего высшего образования, и ни олимпиады, ни модные сейчас «образовательные услуги» дать его не могут.
Почему россияне так популярны?
Вот уже восемь лет подряд чемпионами ICPC становятся только российские студенты — а в 2006 году лучшие вузы мира (Кембридж, Гарвард, MIT и десятки других) обошла команда Саратовского университета. Авторитет российской программистской школы непоколебим.
Секрет ее успеха — в трех чертах российского образования: охвате, массовости и глубине.
Охват школьных программ знакомит детей с основами программирования уже в 5–6 классах — ранний старт закрепляет навыки «на подкорке». Школьники за рубежом не изучают программирование вовсе или начинают ближе к выпуску, тратя время на азы.
Массовость гарантирует постоянный приток кадров и каждый год повышает планку. Речь о тех самых кружках, университетских курсах и секциях: их число с годами только растет.
Наконец, из российских вузов выходят не просто продвинутые «кодеры», а специалисты широкого профиля. Только в нашей стране есть площадки вроде Физтех-школы ФПМИ при МФТИ, где студенты не выбирают между «спортивным» и «промышленным» программированием. Их учат всему и сразу, развивая тот самый кругозор. В результате одни и те же программисты способны и выигрывать олимпиады, и разрабатывать бизнес-решения. Неудивительно, что спрос на них огромен.
Какую карьеру строят выпускники ICPC
Принято думать, что чемпионы уходят в ИТ-гиганты едва ли не с церемоний награждения. Это не всегда так, особенно для россиян. Фундаментальные знания и опыт позволяют им преуспевать и в банках, и в стартапах, и в собственных проектах. А кто-то и вовсе становится преподавателем или тренером олимпиадного движения (в сообществе экс-участников ICPC больше 300 тыс. лучших программистов мира, многие из которых выступают менторами для молодых коллег).
Особенно же программистов-спортсменов ценят в финансовой сфере: биржевой аналитике, алгоритмической торговле, блокчейн-платформах. Именно там прорывные идеи и нестандартное мышление олимпиадников пригождаются больше всего.
Как вырастить спортивного программиста?
Главный совет: начинать как можно раньше. Лучше всего — в 11–13 лет. Если закрепить в этом возрасте все базовые термины и методы, то уже к старшим классам можно приниматься за первые конкурсы, пробовать себя на молодежных хакатонах. В идеале — посещать курсы или летние сборы от центров подготовки, подобрать толкового репетитора.
Первым испытанием часто становится олимпиада по информатике или другой конкурс, дающий право поступить в вуз без экзаменов. А в вузах процесс встает совсем на другие рельсы: на базе центров подготовки предстоит сформировать команды, приучить их к жесткому графику тренировок, назначить тренеров и восполнить недостающие знания (например, языка: все международные чемпионаты проходят только на английском).
В МФТИ таким тренировочным центром является ЦРИТО — Центр развития ИТ-образования. На базе центра проводятся регулярные тренировки и состязания. Здесь опытные тренеры готовят команды для выступлений на международных соревнованиях, в том числе ICPC.
Несмотря на все усилия специалистов, процесс подготовки к олимпиадам — личное дело каждого программиста. И ключевую роль в успехе сыграют его трудолюбие, сообразительность и умение действовать в команде.
Спортивное программирование — социальный лифт в IT. Как его использовать школьнику, родителям школьника и разработчику?
С какого возраста можно обучать ребенка программированию и какой язык лучше выбрать? Как попасть на самые крутые IT-направления в лучшие вузы? Становятся ли дети разработчиков разработчиками? Как попасть на стажировку в Яндекс или на работу в Google?
Расскажи немного о себе. Как ты попал в спортивное программирование и почему остался в нем?
Все началось еще в детстве. В начальных классах я учился в деревенской школе и уже тогда очень любил решать разные загадки, задачки и головоломки. Я не знал, где их искать, но очень радовался, когда они попадались мне на глаза 🙂
В 5 классе я поступил в лицей №1 города Кунгур. Там было принято участвовать в олимпиадах по математике, и я стал ими заниматься. Так я попал в олимпиадную среду и остался в ней, потому что любил решать задачи.
В 9 классе я случайно зашел на кружок по программированию. Тренер (который был всего на 4 года старше меня) рассказал мне и моему однокласснику про спортивное программирование, и мы стали пробовать решать задачи. Получается, как участник я занимался спортивным программированием 9 лет: 3 года школы и 6 лет университета.
Почему я остался? Наверное, потому что мне всегда нравилось преподавать. В 10 классе я начал вести кружок по математике для 5-6 классов, а в 11 классе вел кружок по программированию. Даже когда я поступил в УрФУ и переехал в Екатеринбург, я продолжал ездить в свой лицей по выходным (4 часа на поезде в одну сторону!) и обучать школьников. Когда я был на третьем курсе, мои ученики поступили в УрФУ и я начал тренировать уже студентов. Сейчас я отошел от преподавания и ушел в менеджерскую работу, которая мне не менее интересна.
Михаил Рубинчик — главный тренер по спортивному программированию в Уральском федеральном университете и основатель онлайн-школы по спортивному программированию SPGuide
Расскажи о своей работе сейчас. Что ты делаешь общественно-полезного и чем занимаешься для себя?
Сейчас я занимаюсь двумя крупными проектами: развиваю спортивное программирование в УрФУ и свою онлайн-школу по программированию Sport Programming Guide (или путеводитель по спортивному программированию).
В УрФУ спортивное программирование по большей части бесплатно. Финансово нас поддерживает университет и спонсоры, первым из которых стал СКБ Контур. В компании поняли, что можно начать сотрудничать с университетом и создать на Урале институт спортивного программирования. Все начиналось с выплаты грантов (в частности, на мою зарплату тренера), а сейчас в Контуре есть целый отдел, занимающийся развитием спортивного программирования. Помимо Контура и УрФУ, нас поддерживают и другие местные компании: Naumen, Targem Games, Eastwind, ProSoft и т.д.
Еще один важный спонсор — фонд «Золотое сечение». Он существует под эгидой Министерства образования Свердловской области и поддерживает школьников. Вместе с фондом мы проводим олимпиадные лагеря для ребят из Свердловской области. Подробнее можно прочитать в группе Вконтакте. Проект преимущественно социальный, и можно сказать, что я его идейный лидер и архитектор этой системы 🙂
Второй проект — онлайн-школа спортивного программирования. Он не такой масштабный, и мы занимаемся им вместе с женой: она решает организационные задачи, а я методические. Наша школа — это команда преподавателей, завучей и не только. В отличие от спортивного программирования в УрФУ с лагерями, тренировками и кучей поездок, в школе все проще. Ученик с преподавателем в формате индивидуальных занятий (занятие в школе длится 1 час) обсуждают и решают задачи, готовятся его к школьным и студенческим олимпиадам. Еще в нашей школе можно подготовиться к собеседованиям в IT-компании — мы учим решать задачи, подобные тем, которые дают на собеседованиях.
Чем твоя школа отличается от онлайн-школ программирования без приставки «спортивное»?
Первые ученики появились у нас в 2016 году. Если бы тогда меня спросили, чем моя школа отличается от других, я бы ответил, что олимпиадному программированию кроме нас не учит никто. Сейчас ситуация изменилась, на рынке обучения программированию выделилось несколько крупных сегментов. Первый — школы промышленной разработки (Яндекс.Практикум, GeekBrains, Skillbox), которые ориентированы на взрослых учеников. Там учат языкам, конкретным технологиям и фреймворкам. Второй сегмент — онлайн-школы программирования для детей, где ребят помладше обучают визуальному программированию (типа Scratch), а более старшим ученикам преподают Python. Навскидку это школы вроде Кодиум, Kodland, Алгоритмика. Обучение языкам в них часто идет на стыке с робототехникой. Попыток бесшовного перехода от игрового программирования и изучения языка к промышленной разработке на рынке очень мало.
SPGuide отличается и от первых, и от вторых школ. Мы не ставим перед учениками цель выучить язык программирования, потому что непонятно, что делать дальше.
Игровое начало обучения у нас есть, но только для тех, кто пока не может программировать без игр. Затем мы плавно переходим на настоящие языки программирования и начинаем готовить учеников к олимпиадам и соревнованиям, параллельно изучая необходимую математику. Для младших школьников и тех, кто только начинает программировать, мы даем Python. После Python мы постепенно переводим ребят на C++ (или даем сразу его, если видим, что ученику “заходит”). Он не самый простой для изучения, но это самый быстрый из высокоуровневых языков, и в какой-то момент он занял нишу олимпиадного программирования. Примерно 80% всех решений на олимпиадах пишется именно на C++.
И C++, и Python изучаются в нашей школе на уровне базового синтаксиса. Мы считаем, что для решения задач ученикам полезнее знать алгоритмы, чем разбираться во всех структурах языка.
Как выглядит решение олимпиадной задачи?
Вам нужно написать код, который считывает входные данные с консоли и выводит выходные данные в консоль. Технологически это делается легко, нужен всего лишь экзешник или скрипт, который сделает все за вас. Сложность в том, чтобы быстро обработать считанные данные. Вы можете прочитать задачу и придумать программу, которая будет работать 100 лет, а вам нужно написать код, который будет работать 1 секунду. Олимпиада — это про то, как увеличить скорость выполнения программы. И в нашей школе, помимо игрового программирования, Python и C++, учат ускорять алгоритмы. Мы специализируемся именно на этом.
Где применить навыки решения олимпиадных задач?
Олимпиадные задачи встречаются в трех местах:
Школьные олимпиады — Всероссийская олимпиада школьников (самая крутая в стране) и олимпиады из перечня РСОШ (Российского совета олимпиад школьников). Победители и призеры этих олимпиад могут поступить в вуз без экзаменов или получить 100 баллов за ЕГЭ по профилю олимпиады.
Студенческие олимпиады, в основном турнир ICPC. Это командное соревнование, которое длится 5 часов. В течение олимпиады команда из 3 человек, сидящая за 1 компьютером, должна решить определенное количество задач. За каждую решенную задачу команда получает 1 балл. Чтобы участвовать в ICPC, нужно учиться в вузе и подходить по году рождения.
Собеседования в крупные IT-компании. Чтобы попасть на стажировку в Яндекс, нужно решить реальный контест с олимпиадными задачами. На собеседовании в Google и Facebook тоже дают подобные олимпиадным задачи.
Так получилось, что студенческие олимпиады не очень привлекательны с практической точки зрения. Конечно, на соревнованиях вас могут заметить интересные IT-компании и позвать на работу, да и в целом участие в ICPC можно воспринимать как тренажер для подготовки к собеседованию в компании с мировым именем. Но если вы хотите пройти на чемпионат мира, вам нужно иметь уровень гораздо выше, чем нужно для собеседования. И такие серьезные цели уже не коррелируют с практической полезностью «здесь и сейчас».
Давай остановимся на практической пользе подробнее.
Выгода от собеседования понятна. Вы получаете работу в компании, где мечтали работать вы и еще десятки тысяч ваших конкурентов.
У школьников тоже много выгоды. Во-первых, это поступление в университет. Призерам заключительного этапа Всероссийской олимпиады школьников даже ЕГЭ сдавать не надо, они и так могут поступить без экзаменов почти в любой российский вуз. Что же касается призеров РСОШ, то их поступление зависит от уровня олимпиады и баллов на ЕГЭ. Если призер РСОШ сдаст ЕГЭ по профилю олимпиады на 75 и более баллов, он поступит в университет без экзаменов. Но это работает не для всех олимпиад и университетов.
Поясню, как это происходит. Олимпиады РСОШ бывают 3 уровней: первого, второго и третьего. И каждый вуз сам решает, призеров каких олимпиад принимать без экзаменов. Один универ берет исключительно победителей олимпиад первого уровня, а призеров (не говоря уже о победителях и призерах второго и третьего уровней) уже не возьмет без экзаменов. Другой вуз возьмет победителей и призеров олимпиад первого уровня и только победителей второго. Есть вузы (и это 99% университетов страны), которые берут победителей и призеров всех трех уровней.
Конечно, многие школьники стремятся в “престижные” университеты, и поступить на ряд их специальностей без олимпиад невозможно. Самые популярные среди олимпиадников университеты — это МГУ, СПбГУ, МФТИ, ИТМО и ВШЭ.
Ты замечал какую-то зависимость: дети программистов становятся программистами?
Пока я знаю мало таких случаев, но думаю, что так и будет. Сейчас мы видим, что зарплата разработчиков в разы выше, чем средняя зарплата в стране. Любой родитель хочет, чтобы его ребенок был успешен, поэтому он по возможности будет влиять на ребенка и помогать ему добиваться высот. В том числе отдавать его на специальность, находящуюся на подъеме.
А кто приводит ребят к тебе в школу? Или они приходят сами?
Ко мне приходят даже взрослые разработчики, которые говорят: «Я крутой разработчик, у меня все хорошо. Но я хочу в Google/Facebook, а для этого требуется подучить алгоритмы». Такие люди учатся у нас, успешно проходят собеседования и остаются благодарны школе.
К примеру, у нас учился Илья Щукин. Он жил в Тель-Авиве, работал в местной IT-компании и целый год пытался попасть в Google, но никак не получалось. После полугода обучения в SPGuide он прошел отбор.
Но в основном мы, конечно, ориентируемся на школьников. Их можно условно разбить на две категории:
Олимпиадники, которые хотят побеждать на соревнованиях. Они уже знакомы со спортивным программированием и участвуют в олимпиадах, но не так успешно. Ребята постарше (примерно 9 класс) в основном приходят в школу сами, более младших олимпиадников приводят к нам родители.
Ребята, которые никогда не участвовали в олимпиадах и хотят заниматься программированием или олимпиадной информатикой. Таких ребят обычно приводят родители.
Для всех ребят мы проводим вводное ознакомительное занятие. Олимпиадников знакомим со школой, показываем нашу платформу, решаем задачи, чтобы посмотреть исходный уровень. Ребятам, которые только хотят участвовать в олимпиадах, также рассказываем о плюсах, минусах и вызовах, которые стоят перед олимпиадниками. Плюсы я уже называл выше (поступление в крутой вуз без экзаменов), а про минусы обычно говорим так: «Ребята, придется пахать. Если вы придете к нам и будете ждать, что преподаватель занесет знания в ваш мозг — ничего не получится. Толк появится, только если вы постоянно будете решать задачи самостоятельно”.
Сколько времени в неделю нужно уделять решению задач, чтобы добиться успехов?
Я понимаю, что людям всегда хочется получить точный ответ в часах, но, к сожалению, я не могу его дать. Расскажу, какие факторы влияют на затраты времени и результат.
Во-первых, имеет значение возраст, в котором ученик начал заниматься олимпиадным программированием. Например, человек без опыта математики и программирования приходит к нам летом после 9 класса и говорит, что хочет стать призером Всероссийской олимпиады. В этом случае я скажу, что нужно жестко пахать — около 40 часов в неделю. Даже так: я отвечу, что не уверен, что у него получится стать призером Всероссийской олимпиады, даже если он будет пахать по 40 часов в неделю. Потому что 2 года в таком случае — это очень мало, учитывая то, что первые этапы Всероссийской олимпиады начинаются осенью, и у этого школьника есть всего 1 год на подготовку и 1 шанс стать призером (уже в 11 классе).
Есть более реалистичные цели, например, стать призером олимпиады 3 уровня. С нормальной школьной подготовкой по информатике и математике можно спокойно прийти к этой цели за 2 года, занимаясь 10 часов в неделю.
Во-вторых, эффективность занятий зависит от особенностей ученика. Кто-то более усидчивый, кому-то легче даются алгоритмы. Мы не раз наблюдали, как разные ученики достигают очень разных результатов за 1 час занятия.
Хайповый вопрос: зависит ли результат от пола?
Нет. В этом вопросе я феминист. Если от пола что-то и зависит, то только по социальным причинам. Когда родители (учителя, друзья) говорят девочке, что программирование — это для мальчиков, у нее пропадает мотивация, снижается уверенность в себе и результаты становятся хуже. Хотя для для некоторых девчонок это становится вызовом, они думают: «Я вам покажу, что тут не женское дело!» и добиваются успехов.
Да, олимпиадников-девочек по-прежнему гораздо меньше, чем мальчиков, но ситуация меняется. Раньше девочки единично участвовали в олимпиадах по программированию, хотя по математике их было довольно много. Сейчас девочек в олимпиадной информатике стало существенно больше.
Назови, пожалуйста, признаки, по которым в определенном возрасте можно понять, что ребенку стоит заниматься программированием на более серьезном уровне, чем в школьной программе.
Тоже очень острый вопрос!
Думаю, можно ответить не про программирование, а вообще про все. Ребенку должно быть интересно. Если ребенку интересны танцы, ему надо заниматься танцами. Если интересно программирование, нужно заниматься программированием. Вопрос в том, как понять, ЧТО нравится ребенку и не перепутать его желания со своими. Потому что если родитель хочет, чтобы ребенок стал программистом, а у ребенка нет к этому склонности и желания, шансы очень маленькие. Можно потратить кучу нервов и денег и сделать из ребенка программиста, но будет ли он счастлив?
Если вы заметили, что ребенку в первом-втором классе интересно решать математические задачки, попробуйте привести его на кружок по визуальному программированию. Увидите, что глаза горят — значит, можно попробовать что-то посложнее. Главное — поддерживать и направлять, а не навязывать.
Какой идеальный путь должен пройти юный программист, чтобы в будущем легко найти работу по душе?
Я думаю, оптимальный сценарий — поступить в как можно более сильный университет. Сейчас популярно мнение, что вуз — это просто корочки, на которые можно забить, но я знаю немало IT-направлений в российский вузах, где отлично учат разработчиков и дают практически полезные знания. Я сам приложил руку к ФИИТ УрФУ и знаю, что даже в регионах есть сильные вузы и направления.
Главная цель в школьном возрасте — попасть на одно из таких направлений. Чтобы попасть, нужно участвовать в олимпиадах. И преимущество тут у того, кто начинает заниматься раньше. Общая рекомендация: как можно раньше начинайте учить Python — это самый простой язык для обучения. Если не получается, начните с чего-нибудь визуального, а потом переходите на Python.
Продолжи фразу: «Спортивное программирование — это шанс . «
Я думаю, что это не шанс, а возможность. Спортивное программирование — это социальный лифт в программирование вообще. Есть вопрос «Как стать программистом?» и есть 1000 разных ответов, каждый из которых имеет свои нюансы и особенности. Но если вы пришли в спортивное программирование, то вы вне сомнения сможете стать программистом.
Три основных навыка, которые вы тренируете у ребят в школе?
Я даже не буду называть три, потому что есть один самый главный. Это умение думать и рассуждать. Важно то, как мы это делаем.
Есть классический способ обучения всему и везде: прочитать лекцию и дать задачки. Мы считаем этот подход плохим. Потому что лекция — это пассивное восприятие информации. А мы «топим» за активное восприятие. Поскольку наши занятия проходят один на один, мы имеем возможность дать ученику задачу на тему лекции еще до лекции. А потом намекать, подсказывать так, чтобы он нам рассказал, как эту задачу решать, а не мы ему. Мы его только подталкиваем в тех местах, где сложновато. Если очень сложно, мы говорим: «Давай отложим тему и обсудим задачу попроще, а к этой вернемся потом».
Расскажи пару впечатляющих историй про своих учеников из серии «было/стало»
Про Илью Щукина я уже говорил. А вот общий формат изменений будет полезно описать.
Иногда бывает так. Человек приходит и говорит, что был в куче лагерей, прослушал 1000 лекций, проходил онлайн-курсы, знает вообще все темы, которые нужны, чтобы стать чемпионом мира, но с олимпиадами у него не складывается. Это классический портрет человека, пришедшего к нам «с опытом». И все его лекции, курсы и лагеря сработают только тогда, когда у него будет достаточно практики. Поэтому мы учим через практику, помогаем перейти от «я понимаю» к «я умею». Именно это изменение происходит с учениками в нашей школе.
Расскажу про еще один тип историй, которые всегда меня радуют. Приходит человек, который вообще не умеет программировать. Он даже не понимает, что такое переменная. Не в математике, а в программировании. Он не знает, как сложить два числа и вывести на экран. А через пару лет смотришь, а он участвует в олимпиадах и решает базовые задачи. Да, он пока не призер, но эта метаморфоза настолько мощная, что очень меня радует.
Ты упомянул, что спортивное программирование — социальный лифт, который поможет попасть в престижный вуз. Что ты посоветуешь ребятам, у родителей которых нет денег, чтобы заниматься в твоей школе?
Тоже классный вопрос. Тут все зависит от мотивации школьника. История примерно такая:
Если у родителей нет денег, а у ребенка мотивации — ничего не получится.
Если у родителей есть деньги, а у ребенка нет мотивации нет — сделать из него олимпиадника можно, но сложно (дорого и нервно для всех участников процесса).
Если у родителей нет денег, но у ребенка есть мотивация — это неплохой сценарий, и ничего страшного в нем нет!
До какого-то уровня мотивированный школьник может дорасти и сам, решая задачи без помощи наставников и преподавателей. Конечно, нужна дисциплина и усидчивость, но это вопрос привычки и желания заниматься олимпиадной информатикой. Есть много полезных онлайн-ресурсов. Например, сайт Timus с архивом задач по олимпиадному программированию. Очень советую. Сначала решаете как можно больше задач, и только потом участвуете в соревнованиях. Например, на CodeForces.
Можете поискать различные олимпиады школьников в своем регионе и поучаствовать в них. На олимпиадах можно встретить единомышленников, с которыми можно обсуждать различные задачи и делиться знаниями.
Также в развитии очень помогают лагеря и сборы, которые часто проводятся бесплатно или за не очень большие деньги. Например, есть российский лагерь «Сириус», и в нем смены Сириус Регионы и Сириус Юниоры. Юниоры — это 5-8 классы. Отбор проходит через онлайн курс. Вы регистрируетесь на сайте Сириуса и проходите курс, где фактически проверяется ваша усердность. Старт где-то в конце зимы, начале весны.
В нашей группе ВКонтакте мы выкладываем статьи, в которых даем советы по обучению олимпиадной информатике. Заходите, читайте, узнавайте полезную информацию.
В общем, если есть желание, возможности найдутся 🙂
В заключение
Мы благодарим Михаила за интервью. Надеемся, оно показало вам, как работает система олимпиад по информатике и соревнований по спортивному программированию, и как вы можете эту систему использовать. Если у вас есть вопросы Михаилу, можно писать ему сюда.
Также благодарим Михаила за помощь в организации RustCon Contest 2021 — онлайн-соревнования по решению задач на языке Rust. Кому интересен Rust — welcome в чат RustCon Russia.
Как проходят соревнования по спортивному программированию
Очень часто люди, даже увлекающиеся темой программирования, не знают как проходят соревнования по так называемому спортивному программированию. Люди же далёкие от этой темы зачастую невольно улыбаются, когда слышат слова «спортивное» и «программирование» в одном предложении. Сегодня я хочу рассказать как проходят контесты (англ. contest) по программированию.
Существует очень много различных форматов проведения контестов, но самый популярных из них — это формат ACM. Этот формат или похожие форматы проведения соревнований используются на большинстве школьных и университетских, региональных и международных соревнований, а также на Чемпионате мире по программированию ACM ICPC. Про соревнования в этом формате и будет дальше речь.
В контесте продолжительностью 5 часов участвуют команды по 3 человека, чаще всего защищающих честь школы или университета.
Состав команды может быть любой, но зачастую есть один алгоритмист (специалист по алгоритмам и структурам данных), один математик (дискретная математика, геометрия, теория вероятностей. ), а также один кодер (быстро, качественно пишет и отлаживает код). Конечно же, эти роли могут совмещаться или состав может меняться из стратегических соображений. У меня в университетской команде, например, было 3 программиста и не было математика, и мы достаточно неплохо выступали, просто пропуская сложные математические задачи, так как обычно их немного.
Каждой команде выдаётся один компьютер с настроенным для разработки окружением, таким образом одновременно писать код может только один человек. Окружение включает в себя среды разработки для всех разрешённых языков программирования — обычно это C++, Python, Java, иногда C, Pascal. Доступ к Интернету и любым другим источникам информации или кода закрыт. Более того, командам строго запрещено общаться между собой, иногда на соревнованиях и в туалет сопровождают, чтобы удостовериться в соблюдении правил fair play.
В точно назначенное время контест начинается и все участники начинают читать условия задач. Кто-то читает задачи последовательно всей командой, обсуждая задачи, а кто-то делит их на троих, а затем обсуждают кто что прочитал и какую задачу брать первой — это дело привычки и тактики.
Количество задач в среднем варьируется от 8 до 12, из которых 1-2 очень простые (для разогрева), а еще 2-3 — невероятно сложные (такую задачу называют «гроб»). Количество начисляемых очков за каждую задачу не отличается, поэтому критично важно найти и решить самые простые задачи, а также не тратить время сразу на «гробы».
Задача всегда состоит из описания в свободной форме, описания формата входных и выходных данных, ограничений по времени и памяти, а также примеров. На любых международных или серьезных региональных соревнованиях задачи описаны на английском языке. Формат входных данных гарантируется организатором, а формат выходных данных необходимо строго соблюдать. Любой лишний пробел или округление числа до 2 точек после запятой вместо 3 может не засчитаться как правильный ответ. Таким образом, будущих разработчиков учат быть внимательными, не допускать ошибок и многократно проверять свой код.
Вот пример элементарной задачи с тренировочного портала Codeforces. Естественно, что задачу такого уровня вы не встретите даже на городских олимпиадах учеников средних классов:
Достаточно длинное описание задачи, но еще на середине программисту становится понятно, что решение этой задачи — обычная сортировка по возрастанию. Тут сразу необходимо обратить внимание на ограничения входных данных — 100 символов, это очень мало, и сортировка успешно выполнится за миллисекунды.
Однако, это не самое эффективное решение. Мы знаем, что в формуле есть только сложение и числа 1, 2 и 3, поэтому можно схитрить — посчитать сколько у нас есть в формуле символов «1» (A), «2» (B) и «3» (C), а затем вывести по порядку A однёрок, B двоек и C троек, вставляя плюсы между ними. Этот алгоритм линейный и будет работать быстрее, что не критично конкретно в этой задаче, однако скорость выполнения алгоритма является ключевым фактором при больших входных данных.
Алгоритмисту очень важно знать и уметь оценивать скорость работы алгоритмов — будет обидно потратить 1 час на решение задачи, чтобы понять, что нужно более оптимальное решение, но ты его не знаешь; и не менее обидно потратить 1 час на очень производительное решение задачи с помощью сложных алгоритмов, когда задачу из-за маленьких входных ограничений можно было решить простейшим решением «в лоб» за 5 минут.
После того как команда реализовала и протестировала своё решение оно загружается на сервер, который компилирует и исполняет решение, подставляя тестовые входные данные и сверяя их с ожидаемыми выходными данными. То есть, автор задачи придумывает несколько разных вариантов входных данных и указывает какой правильный ответ должна дать программа участника.
Главным фактором победы является максимальное количество решенных задач, а при их совпадении — суммарное время (в минутах) каждой попытки решения всех решённых задач.
То есть, если решение команды с первого раза успешно прошло все тесты, то команде начисляется +1 к количеству решенных задач, а также начисляется время (штраф), равное количеству минут с начала контеста. Решив первую задачу спустя час после начала команда получит 1 решенную задачу и 60 минут штрафа.
Если же на каком-то из тестов решение «упало» (выдало ошибку или неверный ответ, превысило лимит памяти или «не успело» выполниться за указанное время), то это никак не влияет на текущий штраф. Однако, если эта задача всё же будет решена, к штрафу прибавится сумма минут штрафа всех попыток. Например, если команда неуспешно отправила задачу на 20-й минуте, затем неуспешно на 40-й минуте и сдала задачу на 60-й минуте, то команда получит 120 минут штрафа.
Именно поэтому как в разработке программного обеспечения, так и в спортивном программировании критично важно потратить время, чтобы качественно проанализировать и протестировать своё решение, выявить и проверить все граничные тест-кейсы и стресс-тесты (с данными, ожидаемо приводящими к максимально долгой работе решения).
Также важно выбрать оптимальную тактику и порядок решения задач, правильно и согласованно распределить роли. Например, стоит взять задачу посложнее, которую ты точно решишь без лишних попыток, чем простую, но получить штраф за попытки. У меня однажды были соревнования, на которых было 4 понятных, но непростых задачи, а также одна очень сложная и непонятная — эта сложная задача была отдана одному из программистов, который искал решение к ней, исписав все черновики, в течение 4 часов — столько же времени понадобилось нам, чтобы решить первые 4 задачи. Он выдал нам готовое решение, мы реализовали решение и завершили контест со всеми решенными задачами. Если бы мы взялись за эту задачу в конце, то точно бы не успели её решить.
Верхняя часть таблицы результатов региональных соревнований ACM ICPC в северо-восточной Европе в 2016-2017 году:
Данная таблица доступна всем участникам на портале соревнований в реальном времени. Таким образом, все участники видят какие задачи смогли или не смогли решить другие команды. На таблице видно, что задачи A и F были простыми, их достаточно быстро и почти без ошибок решили больше 150 из 228 команд, а задача I — классический «гроб», так как ни одна команда так и не смогла решить эту задачу.
За один час до окончания соревнований данная таблица обычно замораживается и участники больше не видят изменения в таблице. Иногда участникам предоставляют информацию о попытках других участников, но не говорят успешными они были или нет. Это самый волнительный час для участников контеста — особенно тех, кто находится в самом верху этой таблицы.
Спустя ровно 5 часов после начала контеста приём задач завершается, подводятся итоги и награждаются победители.
Результаты финала Чемпионата мира по программированию 2017 года:
Как проходит Чемпионат мира ACM ICPC? Как попасть в команду?
ACM ICPC — это студенческий чемпионат мира, поэтому каждый участник должен быть студентом университета, чьё имя он защищает.
У каждого хорошего IT-университета есть несколько команд — олимпийский состав, который усиленно (а иногда не очень усиленно) тренируется в течение года, отправляется за счёт университета на международные сборы и соревнования по всему миру. Для того чтобы попасть в этот состав зачастую достаточно просто собрать свою команду и показать себя на внутренних тренировочных соревнованиях, либо дополнив список команд в олимпийском резерве, либо заменив в резерве самую слабую из текущих.
Чаще всего спортивным программированием начинают заниматься не в университете, а еще в 7-9 классе, поэтому зачастую университеты «хантят» со школы успешных олимпийцев, предлагая им гранты, скидки, международные сборы и свободное посещение занятий.
Раз в год проходит четвертьфинал ACM ICPC (отборочные, внутри страны), каждая страна определяет свои правила и города для организации отборочных. Например, в Казахстане четвертьфинал проходит в Алматы, а каждый университет может выставить не более 10 команд. В Казахстане эти отборочные рассматриваются Министерством образования и всеми университетами как чемпионат Казахстана. В России квоты более строгие и университету нужно постараться, чтобы выбить каждое дополнительное место для участия на четвертьфинале.
По результатам внутристрановых соревнований команды отбираются на полуфинал ACM ICPC (региональные соревнования). Регионы строго регламентированы оргкомитетом.
Наш с вами регион называется NEERC — с 2017 года регион именуется Northern Eurasia (северная Евразия), ранее назывался «Northeastern Europe Regional Contest» (северновосточная Европа). Соревнования в регионе NEERC проходят одновременно (параллельно) в 4 городах: Санкт-Петербург, Барнаул, Тбилиси и Алматы. Ближайший полуфинал будет 2-3 декабря 2017 года. Каждый человек может не более 5 раз участвовать в региональных соревнованиях.
Затем, лучшие из каждого региона участвуют в финале, который проходит ежегодно в разных городах. У каждого человека есть возможность только дважды участвовать в финале, так что важно эти две попытки использовать с умом, когда готов.
Хорошее выступление на финале ACM ICPC гарантирует вам грант практически в любой технический ВУЗ, а также предложение по работе в ведущие технические корпорации мира.