Как научиться решать олимпиадные задачи по программированию
Автор ruzana.miniakhmetova, 11 лет назад ,
Друзья, недавно в нашем Хаброблоге мы опубликовали пост о том, что же вообще представляет из себя задача спортивного программирования. Изначально пост предполагал сравнение олимпиадных задач с задачами реальной разработки. Однако в финальном варианте мы решили исключить аналогии с промышленным программированием. Будет интересно почитать в комментариях примеры ваших подобных сравнений 🙂
«Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог ABBYY, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с олимпиадной задачи.
Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной. Например, в USACO героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи.
Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно, вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи 🙂 Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно, чем на других.
Вернемся к обсуждению условия. Олимпиадные задачи очень формализованы:
Такая строгая формализация является оправданной. Все решения участников соревнований проверяются на некотором наборе тестов, который готовится жюри олимпиады и обычно заранее не известен участникам.
Следующая особенность заключается в анализе задач. Автор олимпиадной задачи думает о том, сколько процентов участников решит такую задачу, за какое время (с точностью до минут), к какой тематике относится данная задача (например, задача на графы или задача на жадный алгоритм).
Вообще существует два типа олимпиадных задач: «классические» и «эвристические». Классические задачи предполагают наличие точного строго доказанного решения. При решении эвристических задач участники соревнуются между собой, кто сможет получить лучшие ответы. Например, чье решение правильно распознает большее количество символов. Эвристические задачи обычно не имеют точных решений. Здесь они более всего близки к реальной разработке. Например, распознавание символов – вполне себе «эвристическая» задача.
Существует немало способов оценки решений для «классических» задач:
Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче, которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.
Конечно, говорить об особенностях олимпиадных задач можно бесконечно. Мы осветили лишь самые главные моменты. Если у вас есть вопросы или комментарии – добро пожаловать в комментарии. «
abbyy, конкурс задач, хабрахабр
Методика подготовки к олимпиадам по информатике
Чтобы научиться решать олимпиадные задачи по информатике, надо решать задачи по информатике. Естественно при этом заглядывая в соответствующею литературу.
Вопрос 2. Сколько необходимо решить задач, чтобы достойно выступать на олимпиадах по информатике?
Вопрос задан конечно не корректно и ответить на него, пожалуй вряд ли возможно, но сказать пару слов по этому поводу стоит. Как мне соощил специалист в области подготовки к олимпиадам ACM Михаил Медведев, то создать принципиально новую олимпиадную задачу не так то просто, как может показаться на первый взгляд. По этой причине, лица ответственные за проведения олимпиад просто берут задачи за прошлые годы и подают их под «новым соусом». Часто случается, что задачи для районных и зональных олимпиад по информатике «сдирают» без каких либо изменений с сайтов посвященных олимпиадному программированию.
Итак, поскольку многие задачи весьма и весьма схожи, то необходимо научиться решать задачи из всего диапазона: сортировка, динамическое программирование, длинная арифметики и т.д.
Вопрос 3. Можно ли подготовить школьников к олимпиадам по информатике в рамках школьной программы?
Думаю, что это нереально. Всем давно известно, что школьный курс информатики — это одно, а олимпиады по информатике — это совсем другое. Да, в примерной программе по информатике, в 9 классе, довольно большое количество часов уделено изучению программирования. В учебнике Семакина для 9 класса обучение программированию основано на языке Паскаль, у Угриновича примеры дана применительно к Visual Basic . Но, даже если применить дифференцированный подход к обучению школьников, вряд ли этих часов хватит для подготовки к олимпиадам отдельных школьников с «нуля».
Вопрос 4. Если часов по программе не достаточно для подготовки школьникам к олимпиадами, то как тогда готовиться?
Вижу три варианта:
- Кружок по программированию
- Факультатив по программированию
- Личный энтузиазм.
По первым двум вариантам все понятно, но должно быть понимание со стороны руководства школы. Частенько, между учителями бывает «битва за часы», на кружок или факультатив по программированию часов может и не перепасть.
Личный энтузиазм доведенный до крайней меры — это весьма пагубное, на мой взгляд, явление. Российское образование не должно держаться на энтузиазме. Иначе получается, что пока есть энтузиазм — дело идет, закончился запал и все рухнуло. На энтузиазме долго не протянешь, но его иногда стоит проявлять в надежде, что дело сдвинется с «мертвой точки».
Вопрос 5. У меня 25 (26, 30. ) часов основной нагрузки, реально ли еще заниматься с учащихся на кружке по программированию?
Как мне кажется, при такой нагрузке реальней сойти с ума, чем готовить учащихся к олимпиадам. Искренне сочувствую всем учителям с большой нагрузкой. Я понимаю, что брать большое количество часов приходится не от хорошей жизни, но не понимаю, как можно работать в таких условиях.
Вопрос 6. Могут ли школьники готовиться к олимпиадам во внеурочное время и если могут, то как лучше организовать подготовку?
Могут, но у них как минимум должен быть домашний компьютер. В идеале должен быть еще и Интернет. При наличии ПК и Интернета можно решать задачи на одном из специализированных сайтов с автоматизированной проверкой решений, например на сайте Школа программиста.
Вопрос 7. Что требуется от учителя для качественной подготовки школьников к олимпиаде?
- Умение учиться. Ведь как случается, закончил человек учебное учреждение и на этом его развитие в плане получения информации порой и заканчивается. Для работы в школе вроде хватит, так зачем еще заморачитваться.
- Всегда быть на связи. У вашего ученика может возникнуть вопрос в любое время, есть ведь и такие, которые решают задачки по ночам. Если вам не спится, то почему бы, при возможности, ему не ответить при помощи той же «Аськи» или программы Skype .
Как решать олимпиадные задачи по программированию?
Пытаюсь решать олимпиадные задачи по программированию и столкнулся с тем, что не понимаю как это правильно делать.
Обычно они делятся на два типа — первые, те, которые я прямо сразу знаю как решать. И тут все решение — просто начинаю писать код, отлаживать и т.д., никаких проблем.
А вторые — те, для которых или не знаю решения или даже условие сходу не понимаю. (уровень сложных на hackerrank или F,G на codeforces) Как решать такие «правильно»? Правильно — в смысле, чтобы улучшать не только скилл кодирования, но и какую-то теоретическую часть?
Имеет ли смысл сначала попытаться придумать решение самому или сразу гуглить теорию?
Если гуглить не сразу, то через какое время (сколько попыток решения)?
- Вопрос задан более трёх лет назад
- 6214 просмотров
1 комментарий
Оценить 1 комментарий
Как научиться решать олимпиадные задачи по программированию
Олимпиадное или спортивное программирование — это участие в соревнованиях по решению нетривиальных алгоритмических задач. Оно позволяет получить фундаментальные знания, научиться эффективнее писать код и подготовиться к дальнейшей карьере — победителей и призеров олимпиад охотно нанимают ведущие IT-компании.
На старте
Программирование — это умение превращать объекты из реальных задач в абстрактные сущности и выражать их взаимодействие на языке программного кода. Поэтому главное условие для изучения программирования — абстрактное мышление, на которое сильно влияет уровень преподавания школьной математики.
Если вам интересно программирование, и у вас уже начало формироваться абстрактное мышление, с поддержкой увлечённого педагога довольно быстро освоите базовые знания, достаточные для участия в олимпиадах. Однако подготовиться к соревнованиям можно и самостоятельно, главное — сопровождать каждую пройденную тему, даже самую простую, усиленной практикой.
С чего начать?
Сперва нужно освоить какой-нибудь язык программирования. Например, раньше учебным языком был Pascal. Сейчас принято начинать с Python, который популярен среди тех, кто хочет быстро научиться писать код. Этот язык очень дружелюбный к начинающим, у него есть подробная и понятная документация и большое количество библиотек. Но чтобы продолжать участвовать в более сложных олимпиадах, надо будет рано или поздно овладеть C++.
Минимум тем, которые нужно изучить: переменные, операторы присваивания, логические и арифметические операции, условные операторы, потом — массивы и циклы, процедуры и функции. Для того, чтобы в них разобраться, можно, например, посмотреть курс Михаила Густокашина по C++ на Stepik. С этой базой можно решать первые олимпиадные задачи.
Как тренироваться?
Для программирования в первую очередь важна практика, хотя оно требует и теоретической подготовки. Это как водить машину: правила движения можно изучить и в классе автошколы, но научиться ездить можно только сидя за рулём автомобиля.
Я думаю, есть два основных способа выучить программирование:
- «Задачное» обучение — изучение конструкции языка через решение абстрактных задач. Например, когда надо прочитать все числа из файла и подсчитать сумму нечетных.
- Проектное обучение, при котором учащийся получает наглядный результат своей работы, небольшой работающий «продукт».
Олимпиадное программирование хорошо тем, что практиковаться можно и самостоятельно, без помощи преподавателя. Есть платформы, на которых доступно большое количество олимпиадных задач. Решаешь задачу, пишешь код, отправляешь его на проверку и тут же получаешь результат. Мгновенная обратная связь мотивирует продолжать заниматься программированием.
Например, есть сайт «Информатикс», созданный коллективом московских преподавателей олимпиадной информатики. На нём есть и теоретические материалы: например, вводные лекции по Python, к которым прикреплены примеры олимпиадных задач. Прошёл тему — и сразу выполняешь по ней задание.
Самая популярная платформа для решения задач — это codeforces.com, которую создал и активно развивает Михаил Мирзаянов. На ней постоянно проводятся контесты (соревнования), открытые для всех желающих. Они рассчитаны на людей с разным уровнем: от тех, кто только вчера узнал базовые конструкции языка, до настоящих профессионалов, которые выигрывали международные соревнования и занимаются спортивным программированием уже много лет.
Путь к успеху — решать, решать, а потом ещё немного решать. Регулярно писать контесты — хотя бы один раз в неделю, а лучше два. Если решение задачи после долгих раздумий так и не нашлось, читайте её разбор.
Когда сталкиваетесь с незнакомым алгоритмом — знакомьтесь с ним, смотрите лекции на эту тему, изучайте статьи, форумы и книги. Например, «Алгоритмы: построение и анализ» Томаса Кормена и соавторов. Так выглядят дни тех, кто занимается олимпиадным программированием уже профессионально.
А ещё решать задачи гораздо приятнее и полезнее в команде. Ребята, которые занимаются в сообществе, как правило, достигают больших успехов.
Продолжение обучения
Когда человек освоил базу и знает конструкции языка, ему пора идти дальше: углубленно изучать теорию и разнообразные алгоритмы, которые позволяют по-новому работать с уже известными комбинаторными объектами. Знать алгоритмы и уметь применять сложные трюки — это хорошо, но задача никогда не состоит только из применения готовых знаний. Надо уметь сопоставлять разные параметры, вспоминать алгоритмы и модифицировать их для дальнейшего применения.
В любой задаче есть своя уникальная идея — даже если ты видел до этого тысячу других идей и задач, то 1001-я всё равно будет новой.
До многих вещей можно дойти самостоятельно, но проще и быстрее будет, если знающие люди расскажут готовые способы решения. Самый действенный путь — общаться с единомышленниками и посещать места, где делятся знаниями и опытом: выездные школы и сборы. Например, есть смена «Алгоритмы и анализ данных» в «Сириусе», где много времени уделяется тому, чтобы помочь ребятам прокачать необходимые навыки для участия в олимпиадах по информатике. Поищите и регулярные занятия, которые можно посещать круглый год: например, кружки олимпиадного программирования, которые работают в вашем городе.
Самостоятельное обучение по книгам и материалам из интернета — это длинный и сложный путь, хотя поиск самой информации и не составит труда. В частности, на сайте MAXimal собраны 145 алгоритмов для решения разных задач, а также в открытом доступе опубликованы книги по алгоритмам, оптимизации, С++ и Java.
Тактическое преимущество
Чтобы эффективно выполнять задачи, надо понимать, решение каких из них принесет наибольшую пользу в будущем.
Я подразделяю задачи на четыре уровня сложности:
- Первый уровень: даже не замечаешь, как решил задачу. Решение приходит в голову сразу же, как только прочитал условие. Это бесполезные с точки зрения опыта задачи, хотя их и можно встретить на олимпиаде. Если есть возможность их не решать — не решайте.
- Второй уровень: задание вызывает небольшое напряжение. Сходу его не решить, хотя и примерно ясно, в каком направлении нужно двигаться. На такие задания уходит минут 5-15. Подумал, попробовал наиболее очевидный вариант решения или два — и решил.
- Третий уровень: трудные, но подъёмные задачи. Для выполнения придётся опробовать или с нуля придумать новую идею. Не просто собрать решение из готовых кирпичиков, а распутать головоломку. Пока выполняешь такие задачи, осознаёшь то, с чем раньше не сталкивался, возможно, пробуешь малознакомые алгоритмы. На обдумывание может уйти час, а на написание кода — ещё пару часов. Это тяжело и требует волевых усилий, но очень полезно.
- Четвёртый уровень: не для тебя (пока). Например, ты семиклассник, а для решения задачи нужны знания университетских математических формул и громоздких алгоритмов. Прочитал разбор и всё равно вообще ничего не понял. Ты можешь попытаться разобраться и в итоге выполнить это задание, потратив колоссальное время, но получится неэффективно для общего результата.
На смене в «Сириусе» ребята, например, решали такие задачи:
Ошибки при подготовке к олимпиаде
Ударяться в крайности. «Я всегда дохожу до решения сам и никогда никуда не подсматриваю. Если мне нужно будет потратить три недели, чтобы решить задачу, то я потрачу три недели». До всего доходить самостоятельно — это круто, но неэффективно. К тому же, этот путь потребует слишком много силы воли, которая редко у кого встречается, а также может привести к выгоранию и утрате мотивации.
Тут же сдаваться. «Если я не понял, как решать задачу за 15 минут, то я узнаю, как она решается, прочитав её разбор». При помощи ресурса Codeforces, про который я говорил выше, можно узнать, как автор видел решение этой задачи, и как эту задачу решили бы другие люди. Но ты не дал себе шанса подумать как следует, упустил возможность найти решение самостоятельно, а это плохо для опыта и развития интуиции.
Решать только те задачи, которые нравятся. В олимпиадном программировании существуют разные типы задач: некоторые требуют в первую очередь развитого математического аппарата (например, знания теории чисел), в других идёт упор на написание кода, в-третьих — на математику (системы уравнений, теория чисел), а иногда — комбинаторику (графы). Углубляться всегда надо в те области, где возникло сопротивление. Для успеха на соревнованиях полезнее решить пять задач на нелюбимую тему, чем на ту, которая легко даётся.
Не уделять достаточно внимания коду. В процессе написания программы наброски решения переводятся на формальный язык. Иногда ты за пять минут находишь решение и потом пару часов пишешь код, а бывает и наоборот. Писать код так, чтобы в нём было меньше ошибок, способность эти ошибки находить и исправлять — навык, который можно и нужно нарабатывать. Чем больше пишешь код, тем лучше начинаешь это делать. Также полезно обсуждать с другими людьми, как писать программы с меньшим количеством ошибок и читать чужой код.
Что дают олимпиады?
- Льготы при поступлении. Есть линейка всероссийских предметных олимпиад, диплом которых — билет в вуз на бюджетное место.
- Олимпиадный опыт помогает проходить собеседования в крупные компании, так как на них очень часто дают олимпиадные задачи.
- Призовое место — это весомое дополнение к любому портфолио и резюме. Перспектива повышать уровень олимпиадного программирования и дальше, поехать на международные соревнования. Например, на международный чемпионат по алгоритмическому программированию ICPC, который считается самым престижным соревнованием в мире.
- Возможность попасть в специальные летние или зимние школы, на сборы, в проекты вроде «Сириуса», и стать частью сплоченного сообщества.
- Даже если вы не будете занимать призовые места на олимпиадах, участие в них позволит набраться фундаментальных знаний и опыта разработки, разовьёт умение размышлять.
Фото на обложке: Unsplash