[Базовый олимпиадный курс] Занятие 3. Поиск путей на графах

Добрый день, дорогие, друзья!

Сегодня предметом нашего изучения станут графы на путях пути на графах. С целью входа в тему Вам следует до 9 января посмотреть лекцию 1, а с целью дальнейшего ее развития до 12 января посмотреть лекцию 2, а также прочитать и понять статью об алгоритме Флойда.  Далее 10 и 13 января пишем по одному тренировочному контесту. Сначала этот, затем этот. Контесты пишем в виртуальном режиме. Разумеется, кто будет готов раньше, может написать их раньше.

И да пребудет с Вами Сила!

[Базовый олимпиадный курс] Занятие 2. Динамическое программирование

Добрый день, уважаемые друзья!

На этот раз нашей темой будет динамическое программирование. Тема очень важная и обширная, поэтому одной лекцией Андрея Станкевича не исчерпывается. Однако, в для начала вам следует посмотреть его лекцию на youtube до воскресенья, а в воскресенье, 2 декабря, решить в виртуальном режиме следующий трехчасовой контест. Убедительная просьба условия до начала виртуального контеста не читать — хороших тренировок не так много и портить их себе не стоит.

Также напоминаю про соревнование Proggy-Baggy в субботу, 1 декабря.

Всем неравнодушным настоятельно советую Educational Codeforces Round 55. Контесты этой серии вообще пропускать не стоит, что напрямую следует из их названия.

Также напоминаю про необходимость добивания задач прошедших соревнований. Пока всего два студента занимаются дорешиванием первого контеста нашей тренировочной серии. Присоединяйтесь!

[Базовый олимпиадный курс] Занятие 1. Сложность алгоритмов, сортировка и поиск

Добрый день, уважаемые друзья!

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

Каждый участник курса должен создать аккаунт на сайте codeforces.com, где будут проходить подготовительные соревнования в рамках специально созданной группы. Подавайте заявки на вступление прямо на сайте!

В качестве первого задания олимпийцам следует принять участие в завтрашнем контесте, прочитать разбор и дорешать нерешенные задачи. Также до воскресенья следует посмотреть две лекции Андрея Станкевича 1, 2, по темам которых в нашей группе будет проведен 3-часовой индивидуальный контест в воскресенье, 25 ноября в 12:00. Разбор задач будет опубликован под этом постом.

В качестве дополнительного задания следует зарегистрировать свою команду на онсайт-контест Proggy-Baggy, намеченный на субботу, 1 декабря, обнаружить его место проведения — офис Data-Art (предположительно в комплексе стадиона «Черноморец») и принять в нем активное участие.

Также следует зарегистрироваться на сайте topcoder.com и участвовать во всех личных контестах, проводимых там и на codeforces по мере их появления.

С 1 декабря объявляется бессрочный timus-марафон — личное соревнование по количеству сданных задач на платформе acm.timus.ru, промежуточные итоги которого будут проводиться ежемесячно. Для участия в нем следует создать аккаунт на тимусе и сообщить мне имя пользователя. Победителям, как водится, почет, слава и уважение.

Возникающие вопросы по задачам и командной тактике можно адресовать мне лично, либо выносить на обсуждение под постами данной тематики.

Медали для всех, даром, и пусть никто не уйдет обыгранным!

Добрый день, уважаемые друзья!

Глядя на нижеследующие ссылки (2011, 2012, 2013, 2014 — следует нажать ссылочку Standings), многие современники не спрашивают у меня, как прийти к подобным результатам. А зря.

К сожалению, сам по себе ритуал еженедельного посещения кружка умелых информационных ручек с опцией прорешивания особо приглянувшихся задач способен перевести Вас лет за 5 из состояния «сдаю на OCPC-18 три задачи» в состояние «сдаю на OCPC-23 семь задач». Цели и задачи факультатива не могут выходить за пределы предоставления Вам базовых олимпиадных знаний и навыков, а также развития способности самостоятельно ориентироваться в джунглях алгоритмов и языков программирования. Поэтому, воспользовавшись лицензией GNU (то есть, бесплатно), хочу распространить методику превращения обычной команды в призера полуфинала чемпионата Мира.

Данный подход зиждится на трех китах и одной черепахе:
1) Практика
2) Дорешивание
3) Теория
4) Собственно, черепаха

1) Практика. Состоит из личной и командной подготовки.
а) Личная тренировка заключается в ежедневном прорешивании по 1-5 задач в течение нескольких лет. Для этого на начальном этапе неплохо подойдет сайт acm.timus.ru, поскольку там, в отличие от е-олимпа, нет тысяч задач уровня а+б и задач с битыми тестами и поломанными чекерами. Через какое-то время после начала Ваших тренировок на тимусе Вы неизбежно столкнетесь с необходимостью овладения новыми алгоритмами, что и требуется. Также крайне рекомендуется решать личные контесты на codeforces.com и topcoder.com каждый раз, когда они начинаются не в 4 утра.
б) Командная тренировка заключается в еженедельном совместном с командой решении 5-часового контеста, соответствующего Вашему текущему уровню. Для этого отлично подойдет субботний кружок. Здесь Вы отрабатываете командную тактику, опыт взаимодействия, одновременное придумывание одной задачи, написание второй и дебага третьей за одним и тем же компьютером. Для этой цели может подойти, например, codeforces.com — там много соревнований самого разного уровня с очень хорошими тестами и возможностью соревноваться с другими участниками этого контеста.
Если закончился контест, а у Вас еще 2 недодебаженные задачи и 3 — с придуманными решениями, но Вы не успеваете их сдать, это верный признак того, что нужно поднажать на личные тренировки с целью довести до блеска известные Вам методы решения.

2) Дорешивание. Задачи, не решенные во время личной или командной тренировки, необходимо дорешать после разбора. На контесте Вы учитесь сдавать задачи, которые Вы умеете решать. На дорешивании — учитесь сдавать задачи, которые решать до сих пор не умели. Это основа любого роста, который состоит из двух частей — вширь и вглубь. Недорешенная задача может преследовать Вас годами из Полуфинала в Полуфинал, пока Вы не избавитесь от нее, как нерешенной, либо она — от Вас, как участника. Второе наступает всегда в силу возрастных ограничений для ACM ICPC.

3) Теория. Однажды наступает такой момент, когда прошла половина контеста, у Вас 5 задач, сданных с плюса, и еще 5, с которыми Вы понятия не имеете, что делать. Скорее всего, это означает, что настало время изучать новые алгоритмы. Для этих целей служит книга Кормена и др. «Алгоритмы. Построение и анализ», а также сайт e-maxx.ru/algo. В первую очередь стоит изучать те алгоритмы, которые чаще других упоминаются на разборе нерешенных Вами задач.

В команде для каждого «разлоченного» алгоритма должен быть один человек, который пишет его за известное время и со строго ограниченным сверху количеством ошибок и еще 2 человека должны иметь представление, что этот алгоритм делает, чтобы узнавать на него задачи. Для более простых/распространенных алгоритмов важно, чтобы их хорошо писали все трое. Чтобы изучить новый алгоритм, нужно прочитать и понять соответствующую статью, написать соответствующий рабочий код, а затем прорешать все доступные по теме задачи (их можно найти на тимусе и кодфорсе). Очень важно не заниматься копипастом, а писать решение каждый раз заново. Более того, желательно одну и ту же задачу сдавать по несколько раз, засекая время. В идеале, Вы должны тратить на реализацию от 5 до 15 минут (и знать заранее, сколько именно).
Где-то раз в пару месяцев нужно делать пересдачу хотя бы одной задачи по каждому изученному алгоритму, дабы навыки находились в тонусе. В целом, это касается более редких алгоритмов, поскольку часто встречающиеся и так будут попадаться Вам каждую неделю.
Кстати, важная составляющая теории — знание того языка программирования, на котором Вы пишете. Для C++ могу порекомендовать книгу Аммерааля по STL — в ней довольно неплохо описаны структуры данных и алгоритмы, реализованные в стандартной библиотеке.

4) Черепаха, на которой все и стоит, — осознание того, что никто не научит Вас решать задачи. Ни ув. преподаватели ОНУ, ни я, ни ув. Андрей Лопатин с ув. Андреем Станкевичем не проделают за Вас когнитивную работу по утрамбовыванию алгоритмов и методов решения задач в Ваш персональный мозг. Только Ваши усилия и Ваша инициатива способны перевести Вашу команду из аутсайдеров в лидеры. И всякое творчество приветствуется: читайте участникам кружка лекции по изученным Вами алгоритмам, придумывайте свои задачи и проводите по ним контесты (благо, сервер у нас есть), ездите на школы и сборы, общайтесь с единомышленниками. Искренняя заинтересованность и упорный труд свернут горы!

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

Завершить хочу мотивирующей ссылкой (ищем слово Odessa). С целью не повторения, но преодоления, разумеется.

FAQ или диалоги с умным человеком.

  1. Q: Ну выиграю я этот ваш Финал и что дальше?
    A: Ничего особенного.

  2. Q: Ваша команда возникла не на пустом месте. В ней было два призера школьных Всеукров по математике, не считая вашего основного кодера, который может работать по 16 часов в сутки. Мы не такие талантливые/трудоспособные.
    A: В команде ONU_Antananarivu не было ни одного призера Всеукра, однако до 2013 года они тренировались где-то на 70-80% мощности от ONU 1 2/3 и смогли решить достаточное для выхода в Финал количество задач. Их остановило только правило «один ВУЗ — одна команда». В то же время, к 2015-му году они почти перестали тренироваться, а победителем стала команда, занявшая 13-е место двумя годами ранее, а в 2012-м вообще не вышедшая в Полуфинал. Тем не менее, все участницы означенной команды сегодня работают в Корпорации Добра.