Как выиграть всерос по информатике
Как стать призёром Всероса по математике и информатике
Реальная история студента МФТИ о том, почему стоит участвовать во всевозможных олимпиадах и ездить ботать в летнюю школу
Долгая дорога к успеху в математике
К призёрству на Всеросе я плавно шёл с пятого класса. Раз в неделю мы приходили на кружок и по 2-3 часа решали задачи. Достаточно найти одного хорошего преподавателя, который даст базовые знания, а дальше — практиковаться как можно больше.
Постепенно ребята из нашего маткружка стали участвовать во всевозможных олимпиадах, причём по разным предметам. Опыт олимпиад стал ключевым в моей подготовке: я меньше волновался, больше узнавал разных подходов и методов решения задач. В результате на очередную олимпиаду приходил как к себе домой. Это не значит, что я был совершенно спокоен. На заключительном этапе в 11-ом классе было трудно справиться с волнением — всё-таки это большая ответственность.
Я, например, думал, что стану историком, когда в 6 классе занял одно из первых мест в Москве по этому предмету. Но в следующем году уровень конкуренции среди «историков» серьёзно возрос, я не успел под него подстроиться, а вот в математике успел — так определился мой путь.
На протяжении всей средней и старшей школы я посещал математический кружок раз в неделю. Домашних заданий в кружке нам не задавали: мы приходили, решали, кто сколько мог. Конечно, были и обычные уроки по школьной программе, но никаких других дополнительных занятий не было. Если математики слишком много — тоже плохо, может надоесть. Я знаю нескольких ребят, в том числе трёхкратного призёра Всероса по математике, которые побеждали в олимпиадах, занимаясь только в нашем кружке.
Я становился призёром заключительного этапа Всероссийской олимпиады школьников по математике три года подряд: в 9, 10 и 11 классах. Каждый раз я оказывался в числе «средних» призёров: не приближался к победителям, но и не был «в хвосте».
Так выглядит диплом призёра заключительного этапа Всероссийской олимпиады школьников
Короткий путь к призёрству по информатике
До 8 класса я был с компьютером «на вы», а потом в школу пришла новая преподавательница курса программирования, и я заинтересовался информатикой. Я понял, что не хотел бы заниматься теоретической наукой и увидел возможности применить знания на практике.
Поначалу в олимпиадной информатике я опирался на знания по математике и умение решать задачи. Так я прошёл на финальный этап ВсОШ: оказался третьим или четвёртым с конца, ничего не занял и уехал расстроенный.
На выездной школе ученики не распыляются на другие школьные предметы, нет больших перерывов — все сосредоточены на занятиях. Мой уровень значительно вырос, и эффект летней школы сказался через год — я стал призёром на Всеросе.
Хотя я занялся информатикой довольно поздно и добился успеха на олимпиаде, не советую затягивать с подготовкой. Единицы выпускников способны взять призовые места, если начали готовиться во втором полугодии 10 класса. Нужно как минимум за 2-3 года готовиться к Всероссийской олимпиаде.
Выбор вуза: между МФТИ и НИУ ВШЭ
Я выбирал между факультетом инноваций и высоких технологий МФТИ и факультетом компьютерных наук Вышки. В обоих вузах были кафедры «Яндекса», а я мечтал поработать в этой компании. В Вышке факультет только открывался, и было непонятно, что из этого выйдет. Поэтому я послушал совета родителей и лучших друзей — «выбрать что-то проверенное» — и пошёл на Физтех.
Из нашей школьной олимпиадной компании трое пошли на Физтех и двое в Вышку. Мы до сих пор общаемся, так что я могу судить о сходствах и отличиях учёбы в наших вузах. С точки зрения качества образования, набора дисциплин и подготовки выпускников принципиальной разницы я не вижу. Ключевое отличие — уклад жизни, и если бы я снова поступал, то выбрал бы МФТИ.
Пожалуй, на Физтехе приходится больше ботать. Для меня это плюс, так как получается воспитательный эффект — меньшая нагрузка меня бы расслабила. Сейчас я привык много трудиться и всегда знаю, чем себя занять. В любом случае надо быть готовым к тому, что придётся работать больше, чем в школе. Свободного времени у студентов сильных вузов мало, тусовки — редкая возможность.
По моим ощущениям, Физтех — это что-то более коллективное, ВШЭ — более индивидуальное. МФТИ расположен в Долгопрудном, студенты вместе и учатся, и отдыхают — это создаёт командную атмосферу. Сначала я этого не понимал, но теперь считаю атмосферу единения главным преимуществом Физтеха.
Что запомнить
Хотите получать новые статьи во «Вконтакте»?
👉🏻 Подпишитесь на рассылку полезных статей
Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter
Как подготовиться к олимпиаде по информатике?
Информатика во многом отличается от других предметов, имеющихся в школьной программе. И это касается, в том числе, подготовки к олимпиадам и другим подобным конкурсам. Основное отличие: в этом предмете практически нет незыблемых постулатов теории, на которые всегда мог бы опереться учащийся. Эта дисциплина постоянно развивается и меняется, что влияет и на ее преподавание, и на конкурсы.
Как лучше всего описать это различие? Возьмем для примера литературу. В ней произведение, написанное 10 лет назад, может еще не появиться в школьной программе. А в информатике информация 10-летней давности уже считается устаревшей (за редкими исключениями).
Вторая особенность – на олимпиаде по данному предмету важны не только теоретические познания, но и практические навыки. Поэтому подобные конкурсы обычно выигрываются теми школьниками, которые уже занимаются программированием вне учебной программы министерства образования.
Наконец, последняя особенность предмета: школьная программа по нему обычно устаревает на момент выхода. А на олимпиадах по информатике многие вопросы относятся к тому, как работает программирование на текущий момент. Поэтому в процессе подготовки особое значение играет самообразование.
Основные методики подготовки
Для победы в предметной олимпиаде по информатике важна правильная подготовка. Имеется ряд методик, которые могут увеличить шансы на успешное прохождение конкурса:
Причем надо помнить, что залогом победы является постоянная работа и развитие. Если школьник уже разбирается в предмете, ему будет проще наверстать недостающие знания, а затем – выиграть конкурс.
Изучение школьной программы
На текущий момент это – наименее действенный метод подготовки. Но отказываться от него нельзя. Во-первых, в школе закладывают необходимую базу, которая пригодится при изучении прочего материала. Во-вторых, тот ученик, который не знает базовой программы, не будет допущен до участия в конкурсе.
При этом надо помнить, что вопросы, касающиеся базовых познаний о компьютере, обычно задаются на олимпиадах для 5-6 класса. Для учеников постарше составляются вопросы, где требуются определенные познания в программировании. Причем теоретических вопросов относительно немного. Большая часть задания связана с практической работой.
Самообразование
Самообразование является главным источником знаний для многих из тех, кто изучает программирование. Ведь зачастую информации немного, и нужные программы и языки приходится изучать самостоятельно. Причем для тех, кто хочет остаться в профессии, подобное самообразование должно войти в привычку.
Как это связано с подготовкой к олимпиаде по информатике? Все просто – на конкурсах нередко встречаются дополнительные вопросы, никак не относящиеся к школьной программе. А эти вопросы могут принести дополнительные баллы, которые так важны для победы в соревновании. Но дать правильный ответ в этих заданиях сможет только тот ученик, который систематически занимается самообразованием по информатике.
Для тех, кто желает проверить свои познания, пригодятся порталы с дистанционными олимпиадами. Они помогут выявить основные пробелы в образовании, что очень пригодится любому учащемуся. Прохождение этих конкурсов абсолютно бесплатное, причем ограничения на количество попыток здесь не имеется. Это позволяет периодически тестировать свой уровень знаний для участия в реальных олимпиадах по образованию.
Изучение дополнительных материалов
По сути, это изучение дополнительной литературы. Но здесь нужно принимать во внимание один важный момент: не стоит рассчитывать на одни только бумажные источники информации. Для ответов на большую часть базовых вопросов их хватит. Но следует помнить – информация в книгах обычно уже считается устаревшей. Особенно это касается тех материалов, которые уже переведены на русский язык.
Лучше всего изучать дополнительные материалы в интернете. В частности, очень полезными станут рекомендации от опытных программистов, равно как и записки разработчиков приложений. Правда, иногда возникает другая проблема – не всегда имеются нужные материалы на русском языке. Хотя по ним вопросы возникают нечасто.
Но тем ученикам, которые желают победить в международных олимпиадах по информатике, очень пригодится знание английского языка. На международных конкурсах очень часто задаются вопросы по материалам, информация о которых имеется только на английском. Даже базовый уровень владения этим языком сильно увеличит шансы на победу в олимпиаде. Поэтому всем школьникам, желающим в будущем заниматься программированием, рекомендуется изучать английский.
Задания с прошедших олимпиад по информатике
Обязательно стоит ознакомиться с теми заданиями, которые были представлены на уже прошедших олимпиадах по информатике. Причем имеется одна полезная рекомендация: смотреть задания не только с российских, но и с международных конкурсов. Это поможет заработать дополнительные очки на соревновании учащихся, и повысит шансы на успех. Желательно поискать детальные разборы заданий, на русском или английском языке.
Полезно будет проверить официальные ресурсы, занимающиеся проведением олимпиад. Особенно будут полезны разборы заданий и курсы для самообучения, представленные опытными педагогами. Не лишним будет и прочтение методических рекомендаций по проведению конкурсов. Их можно найти на сайте организаторов мероприятия. А в письменном варианте их могут получить педагоги или администрация соответствующего учебного заведения.
Отдельное внимание нужно будет уделить видеоурокам с разбором заданий на каждом из этапов мероприятия. Подобные уроки выпускаются, например, Центром Педагогического Мастерства (ЦПМ). Их рекомендуется использовать каждому школьнику, желающему победить на олимпиаде по информатике.
Рекомендации преподавателей и олимпиадников
Устроители олимпиад не устают повторять – на этих конкурсах ученики не соревнуются между собой. Их целью является проверка знаний и расширение кругозора. И большинство олимпиадников разделяет эту точку зрения. Поэтому многие победители конкурсов часто делятся опытом, рассказывают о различных приемах и лайфхаках, которые помогли им победить. Немало подобных рекомендаций имеется и по информатике.
Еще не стоит забывать о преподавателях и руководстве школы. Эти люди более чем заинтересованы в том, чтобы их учащиеся победили в олимпиаде. Подобный успех положительно сказывается на престиже учебного заведения. Поэтому и учителя, и администрация сделают все, чтобы помочь своим школьникам. Не стоит отказываться от такой подмоги. Ведь они смогут узнать, например, какие вопросы задаются чаще всего, или дать дополнительное время для подготовки.
Также полезно будет проконсультироваться у опытного специалиста: программиста, веб-дизайнера или системного администратора. Его рекомендации помогут при решении практических заданий. Нужно учитывать: на всероссийских или международных соревнованиях многие вопросы относятся уже к университетской программе. Школьные преподаватели далеко не всегда могут помочь в их решении.
Как победить на Всероссийской олимпиаде: три новые истории школьников Тинькофф Поколения
Для школьников, которые увлекаются программированием и математикой, каждый год проводятся олимпиады. Узнают о них и начинают участвовать по-разному: кто-то занимался в школьном кружке или почти случайно прошел на городской этап в первый раз. А потом увлекся и начал побеждать.
Призеры и победители Всероса могут в течение четырех лет поступить без экзаменов в вуз, куда бывает сложно попасть из-за большого конкурса. Тинькофф Поколение помогает подготовиться к олимпиадам. Можно бесплатно заниматься на курсах по олимпиадной математике, алгоритмам и машинному и глубокому обучению, но для этого нужно пройти отбор. Занятия проходят онлайн, а школьники из Москвы могут учиться очно.
В прошлой статье мы рассказали про опыт старшеклассников, а сейчас взяли интервью у призеров Всероса, у которых впереди есть еще олимпиадные сезоны. Ребята подробнее расскажут, как готовиться в течение года и сохранять спокойствие на самой олимпиаде.
— похвальная грамота олимпиады им. Эйлера;
— победитель Всероссийской олимпиады по информатике им. Мстислава Келдыша;
— победитель олимпиады им. Максвелла.
— участник финала Всероссийской олимпиады школьников по информатике;
— призер Всероссийской олимпиады школьников по математике;
— призер олимпиады им. Максвелла.
По математике и информатике я уже всех в семье обогнал, но папа может помочь с физикой — он тоже в олимпиадах участвовал
Я начал всерьез заниматься математикой в конце шестого класса. Тогда по итогам муниципального этапа Всероса я прошел на финал олимпиады им. Эйлера.
На олимпиаде Эйлера попробовал решить задачу, за которую почти никто из ребят не взялся. Решить ее до конца не получилось, но моя идея понравилась судьям, и меня позвали в летнюю заочную школу при Физико-математическом лицее в Долгопрудном. Там я начал заниматься по «листочкам», так называются наборы задач по одной теме, и набил на них руку.
После летней школы я прошел отбор в Тинькофф Поколение. Тинькофф Поколение — это дополнительные курсы, на которых я занимаюсь математикой и программированием. Еще хожу на кружок к Павлу Александровичу Кожевникову, с опережением — за 10—11 класс, и к Илье Анатольевичу Иванову-Погодаеву.
В этом году я участвовал в двух Всеросах: по информатике и математике.
На информатике все прошло ужасно. Я решил первую задачу на полный балл, а потом несколько часов решал вторую. Не хватило буквально нескольких минут, чтобы сдать ее. Мне хотелось за каждую задачу получить максимальный балл, и я сидел над ней до последнего — не мог переключиться.
Второй тур написал гораздо лучше, но из-за того, что завис над задачей в первый день, упустил возможность стать призером. Очень злился на себя за это, ни тренеры, ни родители не могли меня отвлечь от переживаний. Хорошо, что на олимпиадах придумывают развлечения, чтобы мы могли отвлечься. Мне понравилось играть в VR-автоматы.
Всерос по математике прошел для меня спокойнее. Я чувствовал, что написал хорошо. Вообще, по математике обычно заранее представляю уровень задач, не было такого, что на олимпиаде оказалось проще или сложнее, чем я думал.
На каникулах я поехал на смену по математике в «Сириус», это образовательный центр в Сочи, и в Летнюю компьютерную школу. В следующем году хочу добавить физику, но пока занимаюсь мало.
Все-таки из этих трех предметов, математика, физика и информатика, мой любимый — математика. Когда вырасту, конечно, хочу стать математиком и заниматься наукой.
2019: призер МОШ по информатике для 6—9 классов
2020: победитель Всероссийской олимпиады им. Келдыша
2021: призер Всероса по информатике
Я привыкаю к олимпиадам, но при этом и ответственность растет. В пятом классе я даже не ожидала, что хорошо выступлю, а теперь жду от себя результатов
Я учусь в школе № 2007, у нас сильная подготовка по математике и информатике. В пятом классе я пошла на школьный кружок по программированию. Мы начали с простых игр на Pascal, например, писали змейку. У меня получалось, и мне предложили подготовиться к Московской олимпиаде школьников по информатике для 6—9 классов.
Для участия в олимпиадах начала учить Python, но на региональном этапе Всероса в прошлом году поняла, что его не хватает для некоторых задач. Сейчас я пишу на C++.
Я хожу в три кружка — в школьный кружок, в Тинькофф Поколение и в Центр педагогического мастерства. В сумме это 20 часов программирования в неделю. Мне нравится, что задания везде отличаются. А еще, если ходишь в несколько кружков, можно пообщаться с разными людьми, с кем-то подружиться.
Обычно в начале учебного года на кружках нет подготовки к олимпиадам, мы изучаем теоретические темы. Ближе к региональному этапу Всероса появляются дистанционные туры, разборы задач прошлых лет. В Москве перед региональным и финальным этапом Всероса проходят сборы — на них мы каждый день готовимся к олимпиаде.
Перед олимпиадами я не очень волнуюсь, но несколько случаев запомнилось. В шестом классе на региональном этапе Всероса я не стала решать задачу, потому что условие показалось длинным и запутанным. Я подумала: «Слишком много текста, даже разбираться в этом не буду». Сейчас я бы разобрала условие по частям и постаралась понять, что от меня требуется.
Еще был случай на Технокубке. У меня не получалось решить задачу. Во время этой олимпиады участники видят онлайн результаты друг друга. Я видела, что многие эту задачу уже решили. Какое-то время я просто смотрела на таблицу с результатами и думала: «Вот еще один участник решил, и еще один». Потом поняла, что так ничего не получится, и десять минут в нее не заглядывала — как раз за это время сама смогла решить.
Перед самой олимпиадой я стараюсь не готовиться и заняться чем-то другим. А сразу после тура мы договариваемся с другими участниками пойти погулять, чтобы не переживать, если чего-то не решили. У меня много друзей-олимпиадников, с которыми потом можно пообщаться.
Я люблю гулять, играть с друзьями в настолки, особенно в «Монополию». Читаю научную фантастику, сейчас — «Задачу трех тел» Лю Цысиня. Раньше еще занималась плаванием, у меня даже разряд есть, а сейчас думаю пойти на рисование.
На олимпиадах я поняла, что можно получить хороший результат, если много готовился. Это работает везде, не только в учебе.
Перед Всеросом я волновался, но чувствовал предвкушение — надвигается испытание, которое я хочу пройти с высоко поднятой головой
В школе на информатике мы программировали на Pascal в шестом-седьмом классе, а с восьмого класса у нас был Python.
Олимпиадами я не интересовался, но в девятом классе практически случайно прошел на региональный этап Всероса. И конечно же, выступил там отвратительно.
Мне было обидно, что я плохо написал, но зато стало интересно. Я познакомился с ребятами из олимпиадной тусовки, они добрые и отзывчивые, несмотря на то, что соперники. Я расспрашивал, как они занимаются и как нужно готовиться, чтобы выступить лучше. Но тогда я еще не знал, что сам скоро в это погружусь.
Потом началась пандемия, дистанционка. Просто учиться в школе и делать уроки мне стало скучно. Я стал думать, где еще можно развиваться, и вернулся к мысли про олимпиадное программирование. Прошел курс в интернете, понял, что мне это нравится, и стал заниматься всерьез.
Мне захотелось чего-то достичь, но чем позже ты начинаешь, тем меньше времени для разгона, нужно стартовать быстро. Все лето перед десятым классом я занимался с репетитором. Он показал мне базовые алгоритмы, и через пару месяцев я уже решал задачи на уровне призера третьей степени перечневых олимпиад.
Осенью я поступил в кружок Тинькофф Поколения и попал в параллель B. У нас была полная свобода, например, не было код-ревью, как у младших параллелей. Мы изучали темы, которые чаще всего встречаются на олимпиадах. Я старался решать все задачи и не пропускал занятия, так что у меня получилось закрыть пробелы в теории, которые мешали продвигаться дальше.
У меня не было строгого графика занятий для подготовки к олимпиадам. Я занимался в свободном режиме: по вечерам зависал на разных сайтах, смотрел лекции, что-то решал. Готовился по три часа в день, но эти три часа искал информацию и решал интересные задачи.
В январе начался региональный этап Всероса. Я волновался и понимал, что не смогу оправдать плохие результаты после такой интенсивной подготовки. Но региональный этап прошел аномально хорошо, и я почувствовал себя увереннее на своем уровне.
Уверенность помогла мне на Всеросе. Во втором туре четыре часа не мог решить задачу А, это самая простая задача контеста. Я понимал, что при моей подготовке должен ее решить, но ничего не получалось. Помог конструктивный диалог с самим собой. Я вышел в туалет и сказал себе, глядя в зеркало: «Гриша, на самом деле ты все можешь, это не тот случай, не опускай руки».
Первый раз попробовал такой психологический трюк, раньше таких напряженных ситуаций у меня не было. Если что-то не получалось на других олимпиадах, успокаивал себя: «Ничего страшного, не получится в этот раз — получится в другой». А на финале Всероса так сказать уже не мог, надо было прямо сейчас успокоиться и решать.
После олимпиады чувствуется опустошение. Нужно возвращаться в школу и сдавать долги за все время, что ты пропустил, попадаешь из одного стресса в другой. Хорошо бы отдохнуть хоть неделю.
Когда я достиг своей глобальной цели и стал призером, было сложно перестроиться. Пока не знаю, к чему стремиться в следующем году. Было бы здорово выступить от России на международной олимпиаде, например IATI, или взять победителя Всероса, но пока я не думал об этом.
Программирование, тригонометрия, рекурсивный перебор: как готовиться к олимпиадам по информатике
Олимпиады — отличный способ не только продемонстрировать свои знания, но и шанс поступить без экзаменов в хороший вуз. Наш блогер Алексей Малеев рассказывает всё, что нужно знать об олимпиадах по информатике, и объясняет, как к ним готовиться.
Прежде всего, надо понять, где вы хотите участвовать и какую цель ставите перед собой. Из наиболее авторитетных олимпиад по информатике можно выделить:
Если ваша цель — поступить в топовый профильный вуз, для этого нужно либо стать призёром олимпиады первого уровня, либо призёром Всероссийской олимпиады. Конечно, чем раньше вы начнёте заниматься, тем лучше. Мало кто становится призером Всероса с первой попытки. Начинать готовиться лучше не позже 9 класса.
Если перед вами задача — попасть в сборную на Международную олимпиаду в 9-10 классе, то надо начинать заниматься еще раньше — с 6-7 класса.
С чего начать
Подготовку надо начинать с выбора языка программирования. Популярностью сейчас пользуются C++, Python, Java, Pascal, но для олимпиад по информатике мы рекомендуем именно C++. Pascal на олимпиадах по программированию не пригодится, потому что его отменили. А Python, хотя и многих школьников учат ему, мы не рекомендуем, потому что он медленный и по сути является интерпретатором и на нём нельзя решить все задачи. Но если вы уже знакомы с Python, вам это пригодится в решении нескольких простых задач, например, задач с длинной арифметикой или написать какой-то скрипт для тестирования.
399 баллов за четыре экзамена: как Рамиль из Казани стал рекордсменом ЕГЭ
В дальнейшем мы будем говорить про C++. Здесь надо знать базовый синтаксис, владеть функциями, классами, уметь работать со стандартными алгоритмами и структурами данных библиотеки STL (sort, vector, set, map, pair и т. п.) и т. д. Освоение языка начинаем с изучения базовых вещей и задач, таких как: ввод-вывод, преобразование данных, операторы цикла, перебор. Начинающие могут брать задачи с онлайн-архивных ресурсов — например, acm.timus.ru или с informatics.mccme.ru. Начинать лучше с тех задач, которые на платформе решили больше всего пользователей. Потом переходить к базовым алгоритмам, например, начать с алгоритмов сортировки, двоичного поиска, простейших понятий о динамическом программировании.
При подготовке важно уделять внимание самым разным темам и быть готовым ко всему. Например, если на олимпиаде дают восемь задач, то скорее всего все восемь задач будут на разные темы. Но главное — это понимать, что в информатике без серьёзной математической подготовки вероятность успеха невелика.
Что нужно знать, кроме языков программирования?
Математику и тригонометрию
По математике нужно знать: делимость, свойства делимости, представление целых чисел, геометрические задачи. Геометрия в информатике немного другая, не такая, как в школе. 90% задач по геометрии в информатике решаются через векторы. В векторном представлении формулы выглядят совсем не страшными. Можно решать задачи на e-maxx.ru, acm.mipt.ru или codeforces.com и потом участвовать в онлайн-соревнованиях.
Требуется понимание, как устроен компьютер, что такое точность вычислений, нужно знать типы данных, сколько бит занимает целое число, уметь проводить вычисления с плавающей точкой, потому что на это часто бывают задачи.
С формулами типа Герона с корнями, которые даются в школе, никакие задачи по информатике не решишь. А вот тригонометрию знать очень желательно, хотя бы для того, чтобы лучше понять векторы. Тригонометрия используется в любых геометрических задачах, таких как поиск расстояния между двумя отрезками, проверка факта пересечения отрезков, поиск расстояния от точки до прямой, определение взаимного расположение окружностей и т. п.
Рассмотрим для примера задачу, в которой нужно найти расстояние от заданной точки С до отрезка AB. Сначала нужно понять, является ли один из углов CAB и CBA тупым; это легко сделать с помощью скалярного произведения. Если, скажем, угол САВ тупой, то ответ — это расстояние от С до А; аналогично с СВА. Если же оба угла тупые, то ответ — это высота треугольника ABC, равная удвоенной площади, деленной на длину отрезка АВ; площадь можно найти через косое (векторное) произведение. Таким образом, получилось простое решение, не использующее ничего, кроме школьной тригонометрии и векторов.
Динамическое программирование
Также для участия в олимпиадах надо знать динамическое программирование. Задачи на динамику будут практически в каждой олимпиаде, включая региональные. Это очень важная тема. Уметь оценивать скорость работы программы, асимптотику, растет ли скорость как O(n), O(n^2) («n квадрат») или как логарифм.
Классический пример задачи: черепашка движется из верхнего левого угла в правый нижний, в клетках поля написаны отрицательные числа. Она может двигаться только вниз или вправо. Нужно пройти и собрать наибольшую сумму. Это задача на двумерную динамику. Бывают задачи вида «найдите количества последовательностей длины N из нулей и единиц, в которых нет двух единиц подряд», решаемые с помощью чисел Фибоначчи, и многие другие. Это нужно решать через числа Фибоначчи.
В чём ещё надо разобраться?
Хотя в стандартной библиотеке языка C сортировка есть, но все равно необходимо уметь написать алгоритмы сортировки лучше, чем за N2. Например, знать сортировку слияния (Merge sort).
Нужно уметь решать уравнения методом двоичного поиска. Задача может звучать так: «найти корень уравнения, если известно, что в одной точке величина отрицательная, в другой — положительная». Для решения всякий раз берем середину отрезка и смотрим, поменялся ли знак в этой середине.
На олимпиаде надо знать вещи типа алгоритма Евклида для простых чисел. Надо уметь находить взаимную простоту чисел, уметь работать с остатками от деления по модулю
Если сложение, умножение, вычитание — это довольно простые вещи, то для деления будет нужен нетривиальный алгоритм быстрого возведения в степень. В очень многих олимпиадах ответ требуется вывести в виде остатка от деления на какое-то большое простое число.
Из того, что не проходят в школе надо также знать темы, касающиеся теории графов: что такое ориентированный и неориентированный граф, представление графа в виде списка, в виде матрицы и в виде списка вершин, базовые алгоритмы, обход в ширину, обход в глубину, компоненты связности, топологическая сортировка остовные деревья и т. п.
Андрей Колмогоров. Математический гений ХХ века, который хотел реформировать школы
Надо научиться решать задачи на рекурсивный перебор, типа задачи обхода доски ходом коня. Лучше найти какой-нибудь продвинутый учебник по информатике. На начальном этапе стоит ознакомиться с книгами «Программирование: теоремы и задачи» А. Х. Шеня и «Программирование в алгоритмах» С. М. Окулова. Хорошим помощником также будет книга Е. В. Андреевой «Программирование — это так просто, программирование — это так сложно». Недавно вышла неплохая книга Антти Лааксонена «Олимпиадное программирование». Она для студентов, но первые главы пригодятся школьникам. Помимо различных приемов проектирования алгоритмов в ней подробно описано, как готовиться к олимпиадам, какими качествами нужно обладать, чтобы добиться высоких результатов.
От теории к практике
После освоения базы надо начинать решать задачи по той тематике, которую вы уже освоили. Обязательно не просто «придумывать» алгоритм, но писать программу на одном из языков программирования и сдавать в тестирующую систему. Если задача не проходит, нужно искать ошибки в коде; для этого необходимо проанализировать правильность алгоритма, тестировать программу и т. д.
Если решить задачу продолжительное время не удается, то необходимо изучить разбор задачи; но после этого желательно написать предлагаемый в разборе алгоритм и сдать задачу, чтобы удостовериться, что вы освоили этот алгоритм. Для этого на олимпиадных школах и на международных сборах всегда есть «дорешка». На ней можно задать дополнительные вопросы преподавателям. На выездных школах дети много общаются с преподавателями, там отработана система подготовки, потому занятия проходят очень эффективно.
В качестве примера разбора возьмем классическую олимпиадную задачу.
Задача «Рыцари и лжецы»
На острове Буяне жили N человек, каждый из которых был либо рыцарем, либо лжецом. Все они встали в круг. Рыцари говорят только правду, лжецы всегда только лгут. Каждому человеку в кругу задали вопрос: «Кто ты и кто твой сосед слева: рыцарь или лжец?». При этом каждый человек сказал, что он — рыцарь. А ответы всех людей о левом соседе были записаны в следующем формате: ответ «он рыцарь» обозначался за 1, ответ «он лжец» — за 0.
Все ответы были записаны в строку через пробел в порядке опроса (совпадающем с порядком обхода). Последний спрошенный человек отвечал на вопрос о первом.
Написать программу, которая по ответам жителей определяет, какое количество рыцарей заведомо присутствует в круге.
Формат входных данных:
Первая строка входного файла содержит число N (1
Задача о рыцарях и лжецах — переборная. К счастью, перебор можно ограничить всего лишь двумя вариантами: первый человек — рыцарь или лжец? Предположив один из двух вариантов, можно однозначно вычислить, рыцарь или лжец следующий (так как человек с известным статусом сказал про человека слева) и так далее по индукции до первого. В процессе индукции можно считать, сколько у нас рыцарей. Когда по индукции выяснен статус первого жителя, проверяем, соответствует ли он нашему предположению. Если же соответствующих вариантов 2, то выбираем тот, в котором меньше рыцарей (то есть заведомо присутствует столько-то, а может быть, есть и больше).
Где можно готовиться
Готовиться в одиночку намного сложнее, а школьных уроков по информатике недостаточно для успешного выступления на олимпиадах. Нужно иметь хорошую алгоритмическую подготовку, а не только уметь решать стандартные задачи, и безупречно владеть языками программирования, которые используются на олимпиадах. Большинство победителей олимпиад посещают различные факультативы, участвуют в выездных школах, где можно пообщаться с преподавателями, единомышленниками и получить от них новые знания. Это веселее, интереснее и, что важно, продуктивнее.
6 лучших приложений для развития пространственного мышления
Например, Олимпиадные школы МФТИ, которые мы проводим на кампусе университета в летние и зимние каникулы. Ежедневно ребята полтора часа слушают лекции, полтора часа занимаются практикой. Зависимо от уровня подготовки ребят распределяют по группам: Информатика+Информатика, Информатика-Профи, Информатика Hard. Есть группы по обучению C++ с нуля, и группы, в которых учат базовые алгоритмы и готовят победителей Всероса и Межнара.
Поэтому как начинающему, так и опытному олимпиаднику будут интересны занятия. На выездных школах дети много общаются с преподавателями, там отработана система подготовки, потому занятия проходят очень эффективно.
На codeforces.com участвовать в соревнованиях могут даже новички, на acm.timus.ru тоже можно найти интересные задачи для подготовки. Также рекомендую курс на Stepik «Быстрый старт в спортивное программирование», который прошли уже свыше 9 тысяч человек.
Сложный уровень и Межнар
После базовых знаний надо приступать к освоению более продвинутых алгоритмов. В частности, познакомиться с алгоритмами нахождения кратчайшего пути в графе (алгоритмами Дейкстры, Флойда, Форда-Беллмана). Также надо изучить геометрию (тернарный поиск, алгоритмы поиска выпуклой оболочки, метод сканирующей прямой), базовую теорию игр (ретроанализ, теория Шпрага-Гранди). Более сложное динамическое программирование — динамика на деревьях, на подотрезках, подмножествах, динамика по профилю.
На студенческих соревнованиях появляются задачи на преобразование Фурье, задачи на потоки, паросочетания, стереометрические задачи на точность и другие темы, которые практически не встречаются на школьных олимпиадах.
«Мне очень обидно, когда говорят, что в школе решают только нудные задачки»
На сайте международной олимпиады по информатике IOI опубликован текст «IOI Syllabus» — это тематическая программа IOI, где написано, что может быть на олимпиаде, а чего не может быть. На Всеросе не будут давать задачи на темы, которых нет на Межнаре, потому что Всерос — это отборочный этап перед IOI.
Участие в разных олимпиадах
Самой основной олимпиадой, которая дает возможность поступления без экзаменов в любой российский вуз по специальности — это индивидуальная Всероссийская олимпиада школьников по информатике. Есть еще командная — Всероссийская командная олимпиада школьников, но она не имеет статуса для поступления.
Как и у Всероса, первый уровень олимпиады имеет также Открытая олимпиада школьников по программированию, она проводится Московским физико-техническим институтом, Московским государственным университетом им. М. В. Ломоносова, Центром педагогического мастерства и Московским центром непрерывного математического образования. У нее есть отборочный онлайн-этап, а в марте 600 победителей приглашают в 1С для оффлайн-соревнования.
В марте проходит очный тур Индивидуальной олимпиады школьников по информатике и программированию (ИОИП) Университета ИТМО. Она тоже первого уровня. СПбГУ тоже проводит свою олимпиаду.
Первого уровня есть олимпиада «Технокубок», организованная Mail.ru Group, МФТИ, МГТУ им. Баумана и Codeforces. Третий уровень представляет Открытая олимпиада школьников по программированию «Когнитивные технологии», которую проводит «МИСиС» и МФТИ совместно с компанией Cognitive Technologies. Отбор проходит в декабре, а олимпиада в январе. Третий уровень, если он включен в список, дает определенные баллы по информатике в определенные университеты.
Как выстроить стратегию
На Всеросе дается по пять часов на решение четырех задач на каждый из двух дней участия. На Межнаре — два дня по три задачи.
Школьные олимпиады идут с зачетом частичных решений. Всегда есть задачи, которые решить относительно просто, на них можно набрать много баллов малыми усилиями, в то время как другие задачи решить полностью значительно сложнее; но получить баллы можно даже за их частичное решение. Нужно выделить время, чтобы по каждой из задач написать даже простое решение, которое получит хотя бы 10 или 15 баллов из 100. Всегда уделяйте время стратегии получения частичных баллов.
Нельзя постоянно долбить одну и ту же задачу, если она не получается, надо переключаться
Потому что иначе все может закончиться частичным баллом по одной задаче и полным провалом по другим. Обычно первые две задачи в каждом туре — самые простые. Исходя из этого, надо попытаться простые решить, по сложным — набрать хотя бы базовые баллы за простое решение.
В целом, возможны различные методы подготовки к олимпиадам. Наиболее оптимальный вариант — сочетать все способы, это значительно ускорит прогресс. Читать книги, решать задачи на сайтах, посещать факультативы и участвовать в образовательных лагерях. Самое главное — много решать.
Вы находитесь в разделе «Блоги». Мнение автора может не совпадать с позицией редакции.