В этом году первый набор Факультета Компьютерных Наук заканчивает третий курс, у них прошел первый год специализаций (предыдущие посты про новости ФКН: 1, 2, 3, 4, 5).

Все студенты 3-го года обучения прошли курс по машинному обучению от Евгения Соколова (автора известной специализации на Coursera и руководителя отдела машинного обучения сервиса Яндекс.Дзен). Если вы еще учитесь в школе, то вы можете послушать Евгения в летней школе ФКН; также он отвечает за преподавание машинного обучения в августовской параллели A-ML ЛКШ.

Также общим был курс методов оптимизации, состоявший из непрерывной части и курса по комбинаторной оптимизации от Максима Бабенко, руководителя отдела технологий распределенных вычислений в Яндексе, в прошлом вице-чемпиона ACM ICPC. Среди семинаристов курса также хорошо известный вам Zlobober.

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

Радует, что уровень поступающих к нам каждый год растёт. Это ясно и из отзывов преподавателей, и из результатов поступивших к нам абитуриентов на школьных олимпиадах. Каждый год мы заметно повышаем требования для поступления по олимпиадам, и несмотря на это, каждый год у нас происходит перенабор из-за поступающих олимпиадников. Кстати, у нас ежегодно проходят встречи в Яндексе с победителями всероссийских олимпиад, и вот видео последних двух встреч: 1, 2.

В мае я рассказал на Codeforces о запуске новой специализации по структурам данных и алгоритмам на Coursera, а в сентябре в рамках этой специализации запустился Курс по продвинутым алгоритмам и теории сложности, и о нем хочется рассказать поподробнее.

Темы курса:

1. Потоки в сетях (алгоритмы Форда-Фалкерсона и Эдмондса-Карпа).
2. Линейное программирование (симплекс-метод).
3. NP-полнота (теория, сведения, решение NP-полных задач SAT-solver'ами).
4. Методы борьбы с NP-полнотой (оптимизации полного перебора, решаемые частные случаи, приближенные алгоритмы).
5. Стриминговые (потоковые) алгоритмы.

Задачи для этого курса готовили ifsmirnov, ilyakor, Michael, Perlik, romanandreev, Zlobober и Павел Мельничук.

Потоки и те алгоритмы для их нахождения, которые есть в специализации, наверно для многих участников Codeforces не звучат как продвинутая тема. Зато это точно популярная тема, задачи на поток сегодня есть почти в каждом контесте, и знать базовые алгоритмы для competitive programming просто необходимо. В подтверждение этому одна из задач на программирование, которые идут в конце темы: Google Code Jam любезно разрешил нам использовать условие задачи Stock Charts с GCJ 2009 R2 (тесты и решения к ней готовил ilyakor). К тому же, на практике оказывается, что в 99% случаев именно алгоритмом Форда-Фалкерсона нужно все решать, потому что и писать быстро, и работает на практике быстро, кроме случаев, когда авторы специально заморочились и подготовили тесты против этого алгоритма — это нетривиально, и мало кто этим занимается.

Линейное программирование никогда не было темой спортивного программирования...вплоть до финала ACM ICPC 2016-го года, когда задача I своим условием просто кричала "напиши Дейкстру и симплекс-метод". В результате задачу на контесте сдала только команда Стэнфорда, а пробовало сдавать только три команды. Стэнфорду повезло: у них в team notebook был симплекс-метод. Однако, судя по происходившему на финале с точки зрения аналитика, им также и не повезло: в нём был баг) В результате они довольно много времени потратили на исправление и сдали задачу только на последнем часу, хотя начали сильно раньше. (Возможно, я путаю проблемы Стэнфорда и Вроцлава — прошу прощения, если так.) Так или иначе, сколько команд упустило свой шанс получить результат значительно выше! Ведь не нужно было ничего решать, только реализовать два алгоритма, один из которых многие финалисты могут написать не просыпаясь посреди ночи. romanandreev, готовивший задачу, убедился, что задачу I с финала его алгоритм решает успешно, а вот у студентов на курсере весь форум в обуждениях проблем с точностью и других граблей линейного программирования. Некоторые даже жалуются, что они уже проходили ранее отдельный курс, посвященный только линейному программированию, там эту задачу сдавали, а у нас она не проходит :) Так что оттестировать для team notebook'а можно вполне неплохо)

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

NP-полнота и методы борьбы с ней, как ни странно,- чуть ли не самый практический раздел курса. Вы скажете, там есть слова "теория сложности", но на практике, во-первых, большинство задач изначально NP-полные, а во-вторых, гораздо продуктивнее сразу распознать в задаче NP-полную и думать об одном из способов борьбы с этим (а именно об этом мы и рассказываем в двух разделах про NP-полноту), а не пытаться придумать какую-нибудь хитрую структуру данных в бесперспективных попытках, не догадываясь об этом, опровергнуть P!=NP. Некоторые задачи в качестве чекера используют SAT-solver, т.к. для решения задачи достаточно свести ее к SAT, а дальше на практике огромнейшие instance'ы решаются современными SAT-solver'ами, основанными на последних достижениях, за секунды.

Стриминг — крайне актуальная на сегодня тема, т.к. при обработке огромных объемов данных очень часто нужно посчитать какую-то статистику (количество различных ключей, самый частотный ключ, оценить размер пересечения множеств) по тера- или петабайтам, затратив на это очень ограниченное количество памяти и прочтя данные, желательно, только один раз, ну или два. Эту тему у нас читает приглашенный лектор — Михаил Капралов. Впоследствии у нас появится и задача на применение стриминг-алгоритмов. Для того, чтобы отделить стриминг-алгоритмы от обычных в рамках типичных time limit'ов, нужно постараться, но вроде это принципиально уже получилось, осталось оформить.

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

В этом году первый набор Факультета Компьютерных Наук заканчивает второй курс, и на этом фундамент, обязательный для всех, почти заканчивается. Что же ждет их дальше, на 3-4 курсе и в магистратуре? Ниже я расскажу об этом, а также об основных новостях ФКН: старт специализаций, новая магистерская программа, открытие двух лабораторий, изменения в базовой программе 1-2 курса по итогам первых двух лет существования ФКН, включая оценки и фидбэк от самих студентов.

UPD. Льготы по олимпиадам опубликованы здесь, а про всероссийские олимпиады написано здесь.

На 3-4 курс все студенты выбирают себе специализацию. Это набор курсов в рамках одной широкой темы, некоторые из которых обязательны для всех, кто выбрал специализацию, а из остальных нужно выбрать определенное количество (не все). Всего у нас будет пять специализаций, про две из них я расскажу подробнее ниже. Кроме курсов специализации, есть обязательные для всех курсы и общие курсы по выбору, а также курсовая работа, которая может быть либо научной работой, либо проходить в форме командного проекта.

Специализация по машинному обучению

Одна из самых горячих тем в Computer Science сегодня и, вероятно, на многие годы вперед – Data Science, включающая в себя Big Data и Machine Learning. Она настолько популярна, что в университетах начинают появляться отдельные программы по Data Science не в рамках Computer Science программ, а параллельно с ними. В последнее время многие постановки задач в теории алгоритмов появляются из Data Science. По оценкам McKinsey, только в США к 2018-му году нехватка Data Scientist’ов составит от 490000 человек, а Harvard Business Review пишет, что Data Scientist — the sexiest job of the 21st century. Могу добавить, что работа в этой области предполагает и программирование, и алгоритмы, и сложную математику, а знания, полученные в университете, пригождаются ежедневно.

В этом году на ФКН стартует специализация по машинному обучению, создававшаяся таким образом, чтобы отражать взгляд и со стороны науки, и со стороны индустрии. Кураторы специализации — Дмитрий Ветров и Евгений Соколов.

Дмитрий Ветров – профессор Сколтеха — переходит в этом учебном году на полную ставку на ФКН и становится главой новой лаборатории Байесовских методов — это большая удача для ФКН! Дмитрий — один из всего нескольких людей в России, работы которых принимают на две главные в мире конференции по Machine Learning – ICML и NIPS. Еще важнее то, что статьи на эти конференции принимают у учеников Дмитрия – аспирантов и даже магистров: для магистра иметь статью на такой конференции – это прорыв, гарантирующий попадание в аспирантуру в сильнейшие научные группы мира. Дмитрий Ветров будет читать курс по байесовским методам в рамках специализации. В лаборатории Дмитрия будут работать его магистры и аспиранты, а также ученики Антона Конушина – руководителя академической программы ПМИ на ФКН и руководителя одной из ведущих научных групп в России в области Computer Vision. Антон Конушин будет читать у нас курс по компьютерному зрению.

Евгений Соколов – профессиональный data scientist, руководитель группы в Yandex Data Factory. Он будет читать общий для всех студентов курс машинного обучения, а также его продвинутое продолжение для студентов специализации. Евгений совместно с Петром Ромовым, Эмели Драль, Виктором Кантором и Евгением Рябенко недавно запустили на Coursera русскоязычную специализацию по машинному обучению в анализе данных. Практически все они, а также половина остальных data scientist’ов Yandex Data Factory будут преподавать на специализации. Таким образом, студенты смогут перенять опыт людей, ежедневно применяющих машинное обучение для решения задач в областях от банковской индустрии, мобильных операторов и интернет-торговли до космической индустрии, металлургии и физики высокой энергии в ЦЕРНе.

Описание специализации и ее программу можно посмотреть здесь. Думаю, что аналогов этой программы нет ни в одном университете в России. В частности, в рамках специализации пройдет новый курс по Deep Learning, который будет отражать последние достижения в области и будет все время обновляться с прогрессом глубинного обучения. Для первых выпускников специализации через два года мы в ШАДе будем готовить и создавать новые продвинутые курсы, чтобы студенты не скучали в магистратуре.

Те из вас, кто был на всероссийской олимпиаде по информатике в этом году, могли видеть выступление Евгения Соколова на тему применения машинного обучения для рисования картин в стиле Ван-Гога, игры в Го и предсказания успеваемости абитуриентов по их успехам в олимпиадах. Для тех, кто не был, если вам интересно послушать про другие применения машинного обучения, есть видеозаписи выступления Евгения на Открытой олимпиаде и выступления Петра Ромова на ЗКШ про предсказание того, кто «затащит катку в доту» :)

Если вам интересно «потрогать», что такое машинное обучение, то записывайтесь в параллель ML летней школы ФКН в августе. Также в июле пройдет параллель A-ML в ЛКШ, которую будут вести Евгений Соколов и Петр Ромов. Набор в ЛКШ уже закрыт, но если вас пригласили в другую параллель ЛКШ, у вас там будет возможность сходить на спецкурс по машинному обучению. Ну а для изучения Machine Learning по полной программе – конечно, поступайте на ФКН.

Специализация по распределенным системам

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

Куратор специализации – Иван Пузыревский, преподаватель ШАД и руководитель группы в Яндексе. Группа Ивана являются частью отдела Максима Бабенко. Отдел Макса работает над созданием и развитием распределенной системы хранения и обработки данных под названием YT (“Ыть”), использующейся во всем Яндексе. В марте Zlobober, также работающий в этом отделе, делал небольшой рассказ для школьников на тему вычислений над большими данными.

Биоинформатика

С этого учебного года на факультете стартует магистерская программа «Анализ данных в биологии и медицине» под руководством Михаила Гельфанда, одного из главных специалистов в России в области биоинформатики. Биоинформатика — активно развивающаяся область на стыке биологии и информатики, в которой уже достигнуты большие успехи, но есть и множество открытых вопросов, связанных с пониманием функций отдельных частей генома. Ответы на эти вопросы могут привести к методам лечения болезней, которые сегодня неизлечимы, а также возможностям усиливать или ослаблять те или иные стороны и способности организма. Если вы когда-нибудь активно изучали строковые алгоритмы, от Кнута-Морриса-Пратта до суффиксных деревьев, массивов и автоматов, то, вероятно, замечали, что книга Гасфилда написана в первую очередь для биоинформатиков.

На программе математиков (программа-то по направлению "Прикладная математика и информатика", при поступлении экзамен только по математике и английскому языку) научат основам биологии (курсы по молекулярной биологии, молекулярной эволюции и сравнительной геномике), а также компьютерным методам и специальным алгоритмам, необходимым для работы в такой междисциплинарной области, как анализ медико-биологических данных.

Вводные лекции Гельфанда можно посмотреть здесь.

Теоретическая информатика

На ФКН открылась международная лаборатория по теоретической информатике под руководством Николая Константиновича Верещагина. Николай Константинович — д.ф.-м.н., профессор мехмата МГУ с 1999 года, член Европейской Академии (Academia Europaea) по секции информатики, научный руководитель Максима Бабенко, много лет читает в ШАДе курсы по теории информации и теории вычислений, которые очень любят наиболее «математические» студенты ШАД. Несколько лет назад он пришел на матфак ВШЭ, а недавно перешел к нам на ФКН. Николай Константинович ведёт научный семинар “Теоретическая информатика” для студентов 3-4 курсов, читает курсы по математической логике и сложности вычислений.

Сотрудник лаборатории и руководитель специализации по теоретической информатике — Александр Ханиевич Шень, Directeur de Recherche (DR2) du CNRS, наверняка также известный вам как автор книги “Программирование: теоремы и задачи”.

В качестве ведущего зарубежного ученого в лаборатории работает Владимир Александрович Гурвич, профессор университета Ратгерс в США, специалист в области комбинаторной оптимизации и алгоритмической теории игр. Основные научные интересы В.А. Гурвича лежат в областях теории алгоритмов и теории сложности вычислений, алгоритмической теории игр, теории графов.

Есть предварительные договоренности о визитах профессоров из Microsoft Research, UCLA (Computer Science программа #15 в мире), Institut des Mathématiques de Lille, Université de Montpellier и др.

Лаборатория в целом будет заниматься следующими научными направлениями: сложность вычислений, теория информации, алгоритмическая статистика (один из основателей — Н.К. Верещагин), построение и анализ алгоритмов (один из научных руководителей — М.А. Бабенко), комбинаторная оптимизация и алгоритмическая теория игр.

Теоретическая информатика — не самое массовое направление, но его выбирают некоторые из наших самых сильных студентов, которые параллельно с учёбой имеют возможность работать стажёрами-исследователями в этой лаборатории.

Изменения в базовой программе обычного и пилотного потоков

По результатам первых двух лет мы решили дать студентам больше времени на то, чтобы освоиться и с программированием, и с алгоритмами, и с курсами архитектуры компьютера и операционных систем. Мы выделили дополнительное время на каждый из этих трех курсов в течение первых двух лет обучения, а курсы по сетям и базам данных перенесли на 3-4 курс, где их можно взять по выбору или в рамках специализации.

Что касается пилотников по программированию, то мы столкнулись с неожиданной проблемой: не все пилотники умели программировать на C++ в достаточной степени, чтобы сразу заниматься продвинутыми алгоритмами на этом языке, и поэтому в 2016-2017 году сначала будет один модуль интенсивного курса C++ от любимого лектора всех студентов Алексея Зобнина, а затем уже пилотники попадут к GlebsHP на годовой курс алгоритмов.

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

11-го мая в Яндексе прошла встреча с победителями олимпиад, на которой рассказывали про программу ФКН в целом, пилотный поток по программированию и по математике, а также рассказывал о своих ощущениях студент пилотной группы Валентин Бирюков. Видеозапись мероприятия можно посмотреть здесь.

Что касается пилотных групп по математике, то у них по всем предметам, кроме одного – курса дифференциальных уравнений – разный подход к изучению, отдельные лекторы и семинаристы. Проще всего объяснить, в чем разница, на примере курса дискретной математики.

Студенты, прошедшие базовую школьную программу, не участвовавшие в олимпиадах по математике и не обучавшиеся в матшколах, должны начать с конкретных объектов – графов, перестановок и др. и теорем вроде того, что вершин нечетной степени в графе четное число. Олимпиадники эти вещи давно прошли, они уже кажутся очевидными, но для первого знакомства с ними требуется ненулевое время — и получается, что если проходить их совместно, то либо олимпиадники/матшкольники будут скучать, либо остальные не успеют вникнуть. Кроме того, студентам основного потока нужно научиться формальным способам рассуждений, строгим доказательствам. Только после этого для них имеет смысл перейти во втором модуле к более абстрактным и более высокоуровневым вещам – теории множеств, отношениям эквивалентности, отношениям порядка – и увидеть, что конкретные объекты являются частными случаями этих общих объектов.

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

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

Отбор на пилотный поток проводится в августе по результатам тестирования по математике и по программированию. Никого не заставляют идти на пилотный поток, это дело сугубо добровольное, причем можно решить отдельно как про математический трек, так и про программистский (можно выбрать сразу оба). Студенты довольно трезво оценивают свои силы, поэтому «конкурс» на пилотный поток небольшой и составляет не более 1.5 человек на место. Конечно, если вы активный участник соревнований на Codeforces, то мы предлагаем вам попробовать свои силы и поступить на пилотный поток, по крайней мере по программированию, тем более что для этого вам понадобится только выразить желание и хорошо написать контест :)

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

http://www.csc.kth.se//icpc/finals2016solutions.pdf

Мы в прошлом году выиграли в конкурсе заявок и в этом году запустили специализацию по алгоритмам на Coursera, которая в результате является на этой платформе основным способом изучения алгоритмов и структур данных. Специализация — это не один курс, а целая последовательность курсов, заканчивающаяся Capstone Project, что позволяет изучить предмет значительно глубже, чем это обычно получается в рамках массового онлайн-курса.

Мы — это University of California, San Diego (11 место в мире по Computer Science) и ФКН ВШЭ:

1. Daniel Kane — профессор в UCSD, закончил Гарвард, получил PhD в MIT, четырежды победитель Putnam competition (американская студенческая олимпиада по математике), про него даже есть страница в википедии.
2. Павел Певзнер — профессор в UCSD, последние 12 лет преподает там алгоритмы и биоинформатику, является автором специализации по биоинформатике на Coursera, по материалам которой в десятках ВУЗов во всем мире сейчас преподают биоинформатику, является одним из основателей Лаборатории алгоритмической биологии в Санкт-Петербурге, которая разработала платформу Rosalind.
3. Neil Rhodes — лектор в UCSD — в прошлом Staff Software Engineer в Гугле, преподает последние 10 лет, разрабатывал программы обучения для Apple.
4. Александр Куликов — visiting professor в UCSD, научный сотрудник ПОМИ РАН, директор Computer Science Center и координатор Computer Science клуба в Санкт-Петербурге.
5. Михаил Левин — Chief Data Scientist в Yandex Data Factory, преподаватель курса алгоритмов в ШАДе, куратор программы ПМИ на ФКН ВШЭ.

Одна из главных "фишек" специализации — большое количество задач, позволяющих по-настоящему разобраться в алгоритмах: ведь всем вам хорошо известно, что пока не начнешь писать задачу, только кажется, что решил ее правильно и полностью понимаешь. Дело обстоит точно так же и с отдельными алгоритмами и структурами данных. Всего в специализации порядка 70 алгоритмических задач, многие из которых подготовили Burunduk1, Gassa, GlebsHP, ifsmirnov, ilyakor, nk.karpov, Perlik, romanandreev, tourist, Zlobober, Павел Мельничук и Руслан Савченко.

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

Конечно, если вы красный или сильно желтый, вероятно, вы узнаете не очень много нового. Тем не менее, процитирую некоторые из отзывов на нашу специализацию, связанные со спортивным программированием:

"Amazing Course. I have been looking for this kind of course for months. Must for anyone who wants to be good in Competitive Programming and Algorithms"

"An excellent course. Though I have 10 years of experience in software engineering and I've participated in programming contests in my undergraduate years, this course gave me a much clearer vision on solutions for typical programming problems."

"Very good course on algorithms,particularly useful for competitive programming."

UPD. Если вы не хотите сдавать задачи и получить сертификат, чтобы посмотреть видео лекции и прочитать readings, нужно пройти по ссылке на конкретный курс, например, Algorithmic Toolbox, и выбрать опцию "Audit only". Второй курс специализации — Data Structures — запустился в апреле. Остальные три курса пока не запущены, ближайший — Algorithms on Graphs — запускается в начале июня, следующий — Algorithms on Strings — в начале июля, последний — Advanced Algorithms — в начале августа.

UPD.2 Задачи можно сдавать на одном из следующих языков: C, C++, Java, Python2, Python3, C#, Haskell, Javascript, Ruby, Scala.

UPD.3 Курс по графам стартует 6-го июня, еще можно записаться.

UPD.4 Курс по строкам стартует 25-го июля, уже можно записываться.

UPD.5 Курс по продвинутым алгоритмам и теории сложности стартовал, про него я собираюсь написать отдельный пост.

UPD.6 Финальный проект по сборке генома стартовал, а проект по продвинутым алгоритмам поиска кратчайших путей, включающий Contraction Hierarchies, стал опциональным модулем в конце курса по алгоритмам на графах.

Всем привет из Тайланда!

На ФКН НИУ ВШЭ я занимаюсь проработкой программы бакалавриата для ПМИ и курирую проектную работу. Вопрос "стоит ли давать студентам "настоящие" проекты уже с первого года обучения?" стоял перед нами еще на этапе формирования программы. Мы решили, что стоит, и, думаю, не ошиблись. Расскажу о результатах конкурса проектов, который мы провели в конце, и о некоторых проектах участников конкурса. Буду рад, если прокомментируете и расскажете, что происходит в этом направлении в других вузах (в том числе не в России): интересен опыт, который можно применить и у нас.

Всего было примерно 180 студентов, каждый из которых делал один из 53-х предложенных менторами проектов. Каждый из менторов мог по желанию выдвинуть 1-2 лучших работы из своих студентов (обычно 10 человек на ментора) на конкурс, затем кураторы проектного семинара отобрали 12 финалистов. На самом конкурсе у каждого участника было 7 минут, чтобы изложить суть своего проекта, и несколько минут для ответов на вопросы. В жюри вошли преподаватели факультета, не участвовавшие в проектной работе.

Как прошел финал конкурса — можно посмотреть здесь, а новость с подробным описанием некоторых из проектов — на сайте факультета.

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

Победитель — Глеб Пособин — начинал делать проект, целью которого было ознакомление с теорией нейронных сетей, а реализовать нужно было персептрон Розенблатта, с возможным последующим развитием. Персептрон у Глеба получился за вечер, так что в итоге он реализовал многослойную (или как сейчас модно говорить глубокую) нейронную сеть и применить ее к реальным данным (известный датасет MNIST) для распознавания рукописных цифр на картинках. Глеб также реализовал сверточные нейронные сети, которые особенно хорошо себя проявили в распознавании изображений и не только. Вообще, сейчас это очень горячая тема в науке, т.к. с 2012-го нейросети побеждают все в распознавании изображений, речи, уже в некоторых задачах распознают лучше человека, а недавно с некоторыми оговорками нейросеть научили делать машинный перевод лучше, чем создававшийся пару десятилетий до этого статистический. Для первокурсника реализовать и применить на практике нечто, что сейчас находится на переднем крае науки,- это огромная победа.

Павел Поляков, разделивший второе место, реализовал приближенное и точное решение задачи коммивояжера. Исходное описание проекта здесь. В итоге у Павла получилось лучше, чем ожидал ментор, и приближенное решение работает на графе из 100 вершин за пол-секунды и давало погрешность сверху порядка 2-3%, а точное решение на 100 вершинах работает за 1-2 минуты. Кроме алгоритмической части реализован также интерфейс и визуализация графов и получаемых решений.

Еще двое ребят должны были реализовать какую-нибудь свою идею для "умного" устройства, и у одного получились гоночки под Oculus VR, а у другого — летающий "дракон", управляемый голосом. Оба смогли продемонстрировать свои программы прямо во время конкурса.

Кроме того, на конкурс попали разного рода веб-сервисы — анализирующий инстаграм, цены на квартиры в Москве, а также дающий возможность написать что-нибудь на эзотерическом языке программирования или поиграть в набор самописных игр; лингвистический проект по очистке текстов от обсценной лексики; реализация удаленного вычислительного агента; питоновский WebDAV сервер и библиотека для работы с ним, а также сервис статистического анализа истории рыночных цен финансовых активов.

Знакомые и коллеги, которым я про это рассказывал, все прониклись: мы в свое время на первом курсе и близко такого не делали.

В прошлом году я писал про создание нового факультета компьютерных наук в ВШЭ силами команды Школы анализа данных, отвечал на частые вопросы абитуриентов. Кстати, можете регистрироваться и приходить на день для школьников 5-го апреля с 12:00, если вам интересно что-то из этого.

Летом я лично общался со многими призерами и победителями олимпиад через ВКонтакте и выяснял их настроение по поводу выбора факультета, причины того или иного выбора. Субъективно, наиболее частыми ответами, который я получал, или просто запомнившимися, были такие (не обязательно в порядке частотности):

1. А я и так уже выбрал ваш факультет.
2. Я бы к вам пошел, но боюсь, что на первом году у вас будет бардак, поэтому все-таки пойду на ВМК/ФИВТ.
3. Я решил остаться в родном городе.
4. Я пойду на ФИВТ.
5. Я пойду на матфак ВШЭ.
6. Мне нравятся физика и математика, поэтому я пойду на ФУПМ.

Люди, выбравшие матфак ВШЭ, заведомо делают лучший выбор, если уж решили заниматься математикой. Дада, при том, что я сам заканчивал мехмат, у меня сейчас уже нет в этом сомнений. Люди, решившие остаться в родном городе, заслуживают уважения, потому что именно на них потом держится образование в регионах. Хотелось бы в первую очередь побороться с вариантом 2, т.к. эти опасения, с моей точки зрения, и так были необоснованны, учитывая опыт команды организаторов, но сейчас это можно доказать уже фактами.

Итак, что же интересного произошло на ПМИ ФКН за первые три модуля обучения [вместо бардака]:

1. На факультет поступило неожиданно много студентов. На ПМИ было предусмотрено 100 бюджетных мест. К середине июля к нам подали заявления более 200 человек, которых мы были обязаны взять исходя из критериев приема по олимпиадам. Кроме того, ректор ВШЭ лично гарантирует, что 25% от общего количества бюджетных мест (то есть 25) будут предложены людям с наилучшими баллами по ЕГЭ. Также мы набираем студентов на платное отделение — до 40 человек (кстати, информация про скидки здесь). В итоге мы набрали около 200 человек — почти в 2 раза больше, чем предполагалось.

2. Как вы понимаете, подавляющее большинство поступивших оказались олимпиадниками. Из них было 14 всероссов — 8 по информатике, 4 по математике, 2 по физике. По ЕГЭ поступило только примерно 10 человек самых-самых. Кстати, впоследствии они себя проявили лучше, чем некоторые люди, поступившие с олимпиад низкого уровня, см. об этом ниже.

3. В связи с повышенным набором мы сформировали два лекционных потока по каждому предмету вместо предполагавшегося одного. Удалось найти достаточное количество лекторов и семинаристов. Всего образовалось 8 групп по 25 человек, разделенных на два потока по 100 человек.

4. На входе мы провели, как и собирались, тестирование по математике и программированию. Желающие смогут по ссылке попробовать свои силы и сравнить свои результаты с результатами наших первокурсников. По результатам тестирования из топа (и с учетом пожеланий студентов получить дополнительную нагрузку) мы выделили пилотную группу. Пилотная группа на семинарах по обязательным предметам уходит вперед или рассматривает темы более глубоко; кроме того, все студенты пилотной группы сдают продвинутые факультативы по математике и по алгоритмам. На факультативы по математике, в принципе, допускаются все желающие, а на факультативе по алгоритмам места на семинарах ограничены (на лекции допускаются все желающие).

5. В 1-2 модулях студенты изучали программирование на Python и на C++, в 3-м модуле начался базовый курс алгоритмов, и он же продолжится и в 4-м модуле. Почти все семинаристы на обоих курсах — разработчики Яндекса. Лекторами по курсу также были сотрудники Яндекса, одним из лектором по Python и C++ был Алексей Зобнин; в прошлом он преподавал C++ в ШАДе. Мы знали, что студентам очень нравится стиль преподавания Леши, и смогли убедиться в этом еще раз. В ВШЭ каждые полгода проводятся опросы студентов о качестве преподавания, по результатам которых можно производить улучшения в учебном процессе. Насколько я знаю, это уникальная черта именно ВШЭ. Леша получил очень высокие оценки: проголосовавшие 63 студента (из 100 на его потоке) оценили происходившее на лекциях по нескольким критериям на оценки 4.5-4.7. Семинаристов также оценивали, и большинство семинаристов получили по всем 4-м критериям оценки не ниже 4.3.

6. Также студенты изучали математический анализ, дискретную математику, линейную алгебру и геометрию. См. общую программу бакалавриата здесь. С выбором лекторов мы тоже постарались, в том числе пригласили хороших лекторов из НМУ, с мехмата. В результате все лекторы по всем математическим предметам получили оценки выше 4 по всем критериям, а большинство оценок были выше 4.5.

7. Мы также организовали факультатив по базовым математическим структурам для тех студентов, которые не успели получить нужную математическую культуру в школе или за счет участия в олимпиадах. Факультатив оказался успешным, мы собираемся продолжать проводить его и в следующем году. Также мы планируем добавить дополнительные консультации от преподавателей программирования для тех студентов, которым они необходимы. Также у нас в этом году самообразовались учебные группы, в которых студенты занимались программированием совместно и поясняли друг другу непонятные моменты. Мы помогли им организовать эту деятельность: для них были выделены аудитории и время в расписании.

8. Как я писал ранее, студенты ПМИ ФКН начинают проектную работу прямо с 1-го курса. В 3-м модуле стартовал проектный семинар, в котором более 25 менторов из индустрии и науки руководят индивидуальными проектами студентов. Темы проектов простираются от приближенных решений задачи коммивояжера, архиватора, написания ботов, хорошо играющих в 2048 до веб-схемы метро с поиском маршрута до распознавателя капчи до кластеризации раковых транскриптов и до сервиса статистического анализа истории рыночных цен финансовых активов, посмотрите сами. Леша Гусаков даже ушел из Гугла, чтобы вести проекты у наших студентов :) В конце 3-го модуля студенты должны были сдать менторам промежуточный отчет в свободной форме, и сейчас у большинства уже есть некий работающий проект с частично реализованным функционалом. Мы планируем рассказать о наиболее ярких результатах проектного семинара в конце учебного года.

9. С первых учебных дней начал работу центр студенческих олимпиад ВШЭ под руководством gustokashin. По субботам ребята приезжали в Яндекс на совместные Яндекс.Тренировки с командами МГУ и других московских ВУЗов. По четвергам тренировки проходили прямо на факультете. Результаты не заставили себя ждать: две команды факультета прошли на полуфинал ACM, одна из них прошла в финал ACM, который пройдет в мае в Марокко. Если учесть, что эта команда целиком состояла из первокурсников ПМИ ВШЭ, это очень сильный результат: ребята выступили лучше любой другой команды первокурсников в России. Также наши студенты успели отличиться и в математике: Вадим Калашников занял 5-е абсолютное место на Mirror of Putnam Competition — международной студенческой олимпиаде по математике. А если говорить о совсем прикладных вещах, то наша студентка Александра Фенстер выиграла конкурс Avito.ru по распознаванию контактных данных на изображениях, а Станислав Семенов занял 7-е абсолютное место на крупном международном Kaggle-соревновании Higgs Boson Machine Learning Challenge.

10. Мы проанализировали результаты поступления и их корреляцию с нашим собственным тестированием по математике и программированию, с результатами сессии. Поняли, что и должны, и можем себе позволить повысить критерии приема на факультет по результатам олимпиад. Официальные критерии будут озвучены в конце мая, но в целом видно, что победители и призеры олимпиад 3-го уровня существенно проигрывают людям с очень высокими баллами по ЕГЭ, но без дипломов олимпиад, пригодных для поступления, а также некоторым из студентов платного отделения.

11. Конечно, жизнь факультета не была ограничена только первокурсниками. У нас продолжает работать магистратура, в которой в том числе есть отделение ШАДа. Была создана новая магистерская программа математические методы оптимизации и стохастики под руководством Владимира Спокойного. Также была организована аспирантская школа по компьютерным наукам со своим научным семинаром.

12. В этом году были организованы Коллоквиум ФКН и ИТ-лекторий ФКН. Коллоквиум — научное мероприятие, на нем выступали с лекциями различные российские и зарубежные ученые, такие как Александр Шень, Stefan Haar, Дмитрий Ветров, Илья Разенштейн, Глеб Гусев, Max Kanovich, Владимир Спокойный и другие. ИТ-лекторий — место, где представители компаний могут рассказать об интересных проектах в индустрии. Нас посетили представители Яндекса, Facebook, ВКонтакте, Одноклассников, Крока, SAP и других компаний.

13. В начале 2015-го года открылась лаборатория LAMBDA (ЛАборатория Методов анализа Больших ДАнных), которую возглавил Андрей Устюжанин. Андрей руководит в Яндексе исследовательской группой, которая помогает физикам из CERN анализировать эксперименты с Большого Адронного Коллайдера и применять для этого машинное обучение, в том числе на основе алгоритма MatrixNet, разработанного в Яндексе. В этом году благодаря команде Андрея Школу анализа данных приняли в LHCb — одну из коллабораций ЦЕРНа. Таким образом, ШАД стал единственной организацией, не специализирующейся на физике, которую официально приняли в CERN.

14. Яндекс учредил стипендию имени Ильи Сегаловича. Ее получат трое аспирантов, трое магистров и 10 бакалавров факультета, вручение пройдет в день рождения факультета — 1-го апреля.

В начале нового учебного года мы проводили тестирование по программированию наших первокурсников факультета компьютерных наук ВШЭ в формате контеста на 5 часов. Затем мы проводили на этих же задачах тестирование первокурсников ШАДа этого года, чтобы выделить тех, кому нужно ходить на новый, продвинутый курс алгоритмов. Радует, что за последние годы уровень преподавания Computer Science в некоторых вузах вырос, и есть уже несколько десятков человек, которым можно не слушать наш обычный курс алгоритмов, т.к. они его не только знают, но и могут решать практические задачи.

Все наши первокурсники протестированы, и теперь мы решили предложить желающим проверить себя, сделав контест открытым. Написать его можно в любой момент по ссылке в системе Яндекс.Contest. Контест виртуальный, продолжительность 5 часов. Дисклеймер: все задачи — баяны, так как цель была проверить знание и умение применять базовые алгоритмы, а не устроить олимпиаду с призами.

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

Результаты — ниже, но тем, кто хочет честно проверить себя, рекомендую не смотреть их перед участием в соревновании.

Результаты первокурсников ФКН ВШЭ

Результаты первокурсников ШАД

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

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

Q1. Чем программа обучения будет отличаться от ВМК?

A1. В первую очередь, можете посмотреть саму программу здесь и почитать о преподавателях. Программа будет отличаться и организационно, и содержательно. Организационно, не будет стандартных сессий, к которым нужно все заботать за несколько дней, ничего не делая весь предыдущий семестр. Будут постоянные домашние задания с дедлайнами, контрольные, баллы за которые напрямую будут влиять на итоговую оценку, и даже сильнее, чем экзамен — то есть работать придется весь семестр, а благодаря модульной системе сессии будут не такие концентрированные. По всем предметам будут и лекции, и семинары, и домашние задания, чтобы предмет был освоен глубоко и на практике. Содержательно — добавится с 1-го же курса проектная работа под руководством менторов — опытных разработчиков. Мы привлекли к менторству уже по 5 человек из Яндекса и московского Гугла, а также других практиков, например, академии наук. Это 3 семестровых индивидуальных проекта и 3 семестровых командных проекта. Программа по математике будет меньше по объему (например, вместо 3 семестров диффуров и уравнений в частных производных будет 1 семестр, т.к. computer scientist'ам они нужны в меньшем объеме и в более прикладном виде, чем математикам), но она переработана таким образом, чтобы студенты действительно знали те предметы, которые пройдут, и могли решать задачи, применять методы в новых ситуациях (например, программа по теории вероятностей и мат. статистике — больное место многих программ: студенты не владеют статистическим аппаратом, не умеют проверять гипотезы, оценивать параметры распределений и т.п.). Будет математический практикум, где студенты будут решать задачи "по листочкам" и сдавать их преподавателям, как учат во многих хороших мат. школах. Полностью переработана программа по информатике: студент, закончивший обязательную программу первых двух лет, будет в состоянии реализовать полноценный современный программный проект, работающий на нескольких серверах, взаимодействующих по сети, базу данных, имеющий фронтенд, использующий адекватные алгоритмы и структуры данных. Затем он сможет углубиться в одной из многих специализаций: машинное обучение, распределенные системы, теоретическая инофрматика и др. Будут факультативы повышенной сложности по математике и информатике для сильных студентов. Например, Виталик Гольдштейн уже согласился вести годовой факультатив по продвинутым алгоритмам на 1-м курсе.

Q2. У вас будет халява!

A2. Во-первых, см. выше. Дополню, что вместо 2-х длиннющих сессий будет 4 короткие сессии в год. Система баллов: в итоговой оценке по предмету учитываются домашние задания, контрольные, промежуточный экзамен и основной экзамен. Необходимо будет сдать все выбранные курсы и факультативы, нельзя будет переметнуться и сдать халявный курс. Будет специальный человек, который будет общаться со студентами, выяснять их проблемы, помогать их решать, а также пинать их, чтобы они успевали все к дедлайнам, отслеживать прогресс по проектной работе. Ну и наконец, мы ставим себе целью закрыть все возможности для халявы, про которые мы знаем в других программах. А те, кто учился в ШАДе, хорошо знают, как мы умеем жестко соблюдать дедлайны и отчислять тех, кто ничего не делает.

Q3. У вас будет бардак!

A3. Факультет создается не с нуля, а на основе двух существующих отделений. У всего нового руководства большой опыт преподавания, организации мероприятий и успешного управления образовательным процессом. Мы делали ШАД, среди нас преподаватели мехмата, ВМК, руководители в Яндексе, поэтому для большинства это не новое, а привычное дело. В ВШЭ детально прописаны большинство управляющих процедур, есть набор информационных систем поддержки организационных и учебных процессов, которые облегчают многие орг. вопросы. Для некоторых новых процессов, таких как проектная работа, мы будем использовать привычные в IT проектах инструменты (issue tracker). Нам в помощь есть опытная учебная часть, которая переходит от существующих отделений, она составляет расписание, решает орг. вопросы со студентами. У нас есть и будет большая орг. поддержка от Яндекса.

Q4. Чем вы отличаетесь от ФИВТа?

A4. См. для начала отличия от ВМК. Кроме них, есть следующие важные отличия. Во-первых, бОльший упор на самостоятельную работу. В нашей программе меньше курсов идет одновременно, но мы будем вас больше загружать домашними заданиями и проектами, чтобы вы на практике осваивали предметы и инструменты, решали задачи. Во-вторых, мы поборемся с известными нам проблемами ФИВТа. Например, программа изначально продуманная и целостная: все преподаватели не только общаются друг с другом, но и составляют программы курсов с оглядкой на предыдущие и будущие курсы, сразу же прописываются prerequisites курсов и требования к предыдущим курсам, ожидаемые знания и навыки студентов к моменту окончания курса, с обоснованиями того, почему именно этому мы хотим научить. Другой пример — глубина знания предметов, особенно математики. Многие преподаватели самого ФИВТа жалуются на поверхностные знания студентов по математическим предметам. Мы действуем по принципу меньше, но лучше. Все будут решать много задач, причем не только типовых бессмысленных задач, как это часто происходит, но и задач, которые отходят в сторону, требуют использования нетривиальных идей, применения теорем и методов в нетривиальных ситуациях.

Q5. Что с гуманитарными курсами?

A5. Во-первых, вас будут хорошо учить английскому языку, причем именно тому, который затем понадобится вам в работе и/или занятиях наукой. Будут не только учить, но и проверять: на 3-м и 4-м курсах нужно будет обязательно взять по крайней мере один предмет, который будет читаться полностью на английском языке, а также предзащита бакалаврской диссертации будет проходить на английском языке (защищаться можно на русском). Знание технического английского позволяет читать статьи и документацию, что совершенно необходимо для любой интересной работы computer scientist'а, а также вам пригодится умение общаться с коллегами и представлять свои результаты на английском (при работе в международных компаниях, при выступлениях на международных конференциях). В остальном, гуманитарных курсов немного, всего 4 за 4 года — история, экономика, философия и психология. Причем в ВШЭ хороши соответствующие факультеты, эти курсы будут читаться интересно, и мы выберем для вас действительно интересные программы из возможных по этим направлениям. Физкультура...она есть, но по факту все происходит по желанию.

Q6. Да у вас энтузиазм пройдет, и вы бросите дело посередине

A6. Мы ждали этой возможности кто несколько лет, кто все десять или больше. Мы уже сделали ШАД, и занимаемся им уже 7 лет, и продолжаем его развивать. Наш декан ради этого проекта уволился с мехмата МГУ. Мы понимаем, что это наш шанс сделать что-то огромное и очень важное, такой шанс, который выпадает раз в жизни.

Q7. Вы притащите интересных людей из Яндекса, которые красиво говорят, но никогда не преподавали

A7. Посмотрите на страницу преподавателей. Почти все имеют опыт преподавания более 5 лет. Большинство "проверены" придирчивыми и голосующими ногами студентами ШАД. Есть преподаватели, которые вели занятия на мехмате, ВМК, ФИВТе, в том числе и на младших курсах.

Q8. Будет ли какое-то взаимодействие с иностранными ВУЗами?

A8. Давно существуют совместные программы с некоторыми европейскими ВУЗами: магистры ВШЭ могут часть времени обучения, порядка года, отучиться в одном из этих ВУЗов, а остальное время — в ВШЭ. Академическим аспирантам будут оплачиваться стажировки в научных группах, с которыми есть связи у групп на ФКН, а среди них есть группы в MIT, Ecole Normal Superior, Zurich ETH, Microsoft Research Cambridge и другие. Кроме того, мы давно взаимодействуем с EPFL и рассчитываем привозить оттуда лекторов по определенным темам, которые не так хорошо представлены в России.

Хочу поделиться с вами замечательной новостью. Команде Школы анализа данных доверили создать новый факультет компьютерных наук (computer science — пора уже вводить русские аналоги) в Высшей Школе Экономики. Это шанс, которого мы ждали много лет: целый факультет, начинающий обучение с первого курса, на котором можно будет сделать все правильно. Составить программу, изучив лучшее в Стэнфорде, MIT, EPFL и др., и добавив то, что есть хорошего у нас. Привлечь лучших преподавателей. Научить студентов и математике, и программированию, причем так, чтобы полученные знания и навыки у них остались и пригождались в работе в индустрии или науке, а не забылись или были вовсе не поняты изначально. Если вы хотите узнать больше и задать вопросы лично и можете оказаться в Москве в ближайшее воскресенье, то приходите на День Открытых Дверей факультета в воскресенье 27 апреля в 12:00 в культурном центре ЗИЛ, большой зал, см. подробности по ссылке. Вы также можете задать свои вопросы в комментариях, а ниже я расскажу про факультет немного подробнее.

Почему команда ШАДа?

ШАД — одна из лучших в России магистратур по Computer Science и анализу Данных. В Москве к нам стремятся попасть лучшие старшекурсники и выпускники МГУ, МФТИ и других вузов, мы ежегодно выбираем 100 человек из 700-800 таких кандидатов. Нас просят открывать отделения в других городах, и мы уже есть в Питере, Минске, Киеве, Новосибирске, Екатеринбурге, Харькове.

Среди нас есть победители олимпиад по математике и программированию, выпускники лучших мат. школ, преподаватели мехмата, ВМК и ФИВТа. Мы знаем, где брать лучших школьников и лучших преподавателей, и как все это правильно перемешать и посолить: мы участвовали в составлении и доработке программы ФИВТа, привлечении туда школьников и преподавателей. Нам удалось привлечь к работе над факультетом Александра Шеня. Даже если вы не знаете его лично, то с большой вероятностью вы учились по его книжке или по ее мотивам. Шень написал изначальную концепцию факультета, а сейчас помогает нам отбирать преподавателей и составлять математическую часть программы.

Я отвечаю за "программистскую" часть программы. Активно привлекаю людей из индустрии и из сообщества спортивного программирования к критике и доработке программы, к преподаванию и к ведению проектов. Кстати, старшие товарищи, приходите к нам преподавать и вести проекты (см. ниже).

Почему Высшая Школа Экономики?

Это современный, динамичный вуз, у которого отличные руководители. Им удалось создать и вырастить за несколько лет факультет математики, который уже выигрывает соревнование с мехматом за сильных абитуриентов-математиков. Идея создания факультета про computer science давно была у ректора Кузьминова, но когда с этой идеей пришла команда ШАД, он сразу решил доверить это дело нам.

Как участвует Яндекс?

Сразу скажу, это НЕ корпоративный университет. Мы привлекаем людей из Гугла и ABBYY, из научного сообщества. Конечно, наши сотрудники будут там преподавать. Мы помогли составить программу, найти людей, рассказать о факультете. Но это не будет исключительно факультетом Яндекса, потому что хорошее образование так не делается.

Формат обучения

Самый главный вопрос, если вы абитуриент или школьник,- это чему вас научат, и как вам это пригодится. Есть три главных части вашего образования — это математика, computer science и проектная работа.

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

Обязательные курсы по программированию:

1. Программирование на C++ и введение в Python;
2. Алгоритмы и структуры данных;
3. Операционные системы, архитектура компьютера и низкоуровневое программирование;
4. Технологии программирования — введение в базы данных, в компьютерные сети, в веб-программирование.

Именно этот набор позволит человеку самостоятельно сделать полноценный проект. В современном проекте не обойтись без баз данных и использования целого кластера компьютеров, объединенных по сети. Про важность алгоритмов здесь никто спорить не будет. А базовые знания про HTML, CSS и JavaScript нужны, чтобы сделать хотя бы простенький фронтенд.

Конечно же, будет и курс по Java/промышленному программированию. Есть в программе и курсы по продвинутым алгоритмам, и по машинному обучению, и по распределенным системам, и по алгоритмам для работы с внешней памятью и обработки больших данных, и компьютерное зрение, и многое другое. После 2-го курса вам предстоит выбрать специализацию, в рамках которой будет продуманная цепочка из 8-10 курсов. Кого-то из вас больше заинтересуют распределенные системы, кого-то – машинное обучение, других — теоретическая информатика, и вы углубитесь в свою область.

Не менее важная — проектная часть. С самого первого курса вы будете делать законченные проекты. На 1-м и 2-м курсе это будут индивидуальные проекты, на 1-м — простые, на 2-м — посложнее. Проект на семестр. На 3-м и 4-м курсе — командные проекты на год под руководством опытного разработчика. Вести такие проекты уже согласились некоторые мои бывшие коллеги из московского Гугла и мои нынешние коллеги из Яндекса, и я в процессе активного соблазнения других людей из индустрии :) В Яндексе уже несколько лет существует система «практик», в которой студенты на part-time делают проект под руководством опытного разработчика. Мы очень довольны результатами такого обучения студентов. После него студенты могут успешно проходить собеседования в любые компании, в том числе Яндекс, Google, Facebook. Участники таких проектов приобретают опыт работы в команде, учатся использовать с систему контроля версий, багтрекер, общую инфраструктуру, им делают пристальный Code Review. Пример такого проекта – поиск по википедии, в котором есть все те же подсистемы и подпроекты, из которых состоит поиск в интернете. Можно будет засчитать в качестве работы над таким проектом стажировку в хорошей компании.

Ну и, конечно, куда деваться от спортивного программирования. Никуда от него деваться не нужно: это то, в чем мы впереди планеты всей, и что можно использовать для повышения качества образования. Этим займется Центр Студенческих Олимпиад факультета, которым будет руководить Михаил Густокашин. Я очень надеюсь применить и развить то, что уже многие годы существует как Яндекс.Тренировки, надеюсь, что Миша вдохнет новую жизнь в проект и что студенческая олимпиадная тусовка в Москве сконцентрируется вокруг этого центра.

Набор на нашу образовательную программу составит 100 человек. Мы будем объединять сильных студентов по результатам тестирования в группы, и учить их будут наши лучшие семинаристы по продвинутой программе. И – да, в Вышке и так уже все довольно прогрессивно: никаких «ничего не делал весь семестр – к сессии заботал – через неделю забыл». На каждом курсе будут регулярные домашние, и от оценок по ним будет зависеть как минимум 60% вашей итоговой оценки, остальное – за экзамен. Нагрузка будет большая – если хотите работать, добро пожаловать к нам, халявы не будет :)

Третий отборочный раунд и его разбор были подготовлены Chmel_Tolstiy, aropan, Romka, SobolS, Ra16bit, snarknews и Gassa.

В третьем раунде турнира «Яндекс.Алгоритм» хотя бы одну попытку сделало 265 участников, хотя бы одну задачу из них решило 177. По задаче A было сделано 559 попыток, из них 137 успешных, по задаче B — 127 попыток (47 успешных), по задаче C — 111 попыток (64 успешных), по задаче D — 64 попытки (15 успешных), по задаче E — 45 попыток (20 успешных) и по задаче F — 606 попыток (129 успешных).

Задачи третьего раунда в среднем оказались проще, чем задачи первых двух раундов, и по ходу тура стало понятно, что победитель, по всей видимости, решит все задачи. Действительно, на 72-й минуте шесть задач сдал Petr, правда, все задачи были сданы «в открытую». За пять минут до конца турнира на второе место с шестью задачами выходит KADR, у которого также все задачи сданы «в открытую». Но практически сразу шестую задачу сдаёт nkurtov (Николай Куртов, Швейцария) и выходит на первое место, так как у него сданы «втёмную» три задачи. За две минуты до конца турнира на второе место выходит winger, у которого две задачи в начале турнира были сданы «втёмную», а остальные — «в открытую». И наконец на последней минуте задачу Е «втёмную» сдаёт s.quark (s-quark) из Китая и выходит на первое место: из шести решённых задач у него «в открытую» сдана только B. Итого до системных тестов все задачи решили пятеро участников. Лидирует s.quark, за ним — nkurtov, за ним — winger, Petr — на четвёртом месте, KADR — на пятом.

После системных тестов выясняется, что у s.quark не прошла задача F, которую он сдавал «втёмную» на 25-й минуте, у nkurtov не прошли сразу две задачи — С и D. У winger прошли обе сданные «втёмную» задачи, таким образом, он занял первое место в третьем раунде. Второе место занял Petr, который уже обеспечил себе выход в финал по итогам первого раунда. KADR остался на третьем месте, ainu77 (ainu7) из Южной Кореи переместился на четвёртое, а s.quark даже после того, как у него не прошла задача, оказался на пятом месте и попал в число четырёх финалистов по итогам раунда.

Задача A (Конфетное настроение)

Подсчитаем количество невкусных конфет. Пусть их будет M. Тогда если M = 0, то ответ равен . Иначе рассмотрим, какой ожидаемый вклад в изменение настроения даст i-я конфета, если она вкусная. Она может находиться равновероятно в M + 1 позиции относительно невкусных конфет, и только в одной из них вкусная конфета будет съедена. Значит, ожидаемый вклад в изменение настроения от одной вкусной конфеты A_i равен . Для невкусных конфет ожидаемый вклад в изменение настроения равен , так как первой невкусной конфетой может оказаться равновероятно любая из невкусных. В итоге математическое ожидание изменения настроения равно .

Задача B (Шарики)

Для определенности будем считать, что N ≤ M.

Рассмотрим случай, когда N = 1. Пусть на фото находится k шариков. Заметим, что можно оставить любые k шариков. Однако не любое их относительное расположение может быть получено, потому как невозможно поменять их относительный порядок. Но при этом на любых k позициях можно разместить оставшиеся шарики. Следовательно, всего различных фото можно получить .

Пусть N ≥ 2. Тогда если на фото k = N·M шариков, то такое фото можно получить только одно, так как мы не делали ни одного хода (первый ход обязательно убирает один шарик с поля). Если k = N·M - 1, то после первого хода можно ходить только в свободную клетку на поле — это эквивалентно известной головоломке «Пятнашки»; в этом случае ровно половина перестановок будет достижима (см. ссылку выше). Если k < N·M - 1, то рассмотрим две любые пустые клетки, первым делом получим конфигурацию, в которой пустые клетки стоят рядом. Тогда относительно одной из них головоломка «Пятнашки» разрешима (требуется четность суммы количества инверсий в перестановке с номером строки и столбца, а у выбранных пустых клеток сумма номеров строки и столбца отличается на 1). Далее, выбрав в качестве пустой клетки подходящую, остается только собрать головоломку.

Таким образом, общее количество фотографий .

Задача C (Размещение болельщиков)

Наиболее простой способ решения этой задачи заключался в генерации всех возможных относительных перестановок болельщиков. Зафиксируем некоторый порядок болельщиков, к примеру, снизу вверх, и пусть i-й по счёту болельщик имеет исходный номер p_i. Понятно, что если каждому болельщику не мешает тот, кто сидит непосредственно перед ним, то все болельщики видят поле. Рассмотрим все пары подряд идущих болельщиков. Если h_pi ≤ h_pi + 1, то никаких ограничений на рассадку эта пара болельщиков не накладывает: где бы ни сидел болельщик с номером p_i + 1, ему никогда не будет мешать сидящий перед ним болельщик номер p_i, поскольку он меньше ростом. Если же h_pi > h_pi + 1, то появляется следующее ограничение: болельщик с номером p_i + 1 не может занимать следующие h_pi - h_pi + 1 мест после болельщика с номером p_i, иначе ему не будет видно поля. Соответственно, эти h_pi - h_pi + 1 рядов нужно убрать из рассмотрения для данного зафиксированного порядка болельщиков. Проделав эту операцию для всех пар болельщиков, сидящих друг за другом, нужно прибавить к ответу количество сочетаний из оставшегося количества мест по K, где K — это общее количество болельщиков. Для того чтобы быстро выполнять эту операцию, нужно заранее рассчитать таблицу значений C_n^k для n и k, не превосходящих 1000.

Сложность решения: O(n² + k!·k).

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

Задача D (Интересный язык)

Сначала опишем переборное решение. Найдём все пары слов, для которых одно слово является началом другого. Удалим меньшее слово из большего, оставив только суффикс. Если для каждого суффикса посчитать, сколько раз его можно получить такой операцией, и обозначить это число через cnt_suff, то отсюда получаем ответ на задачу: это , где суммирование ведётся по всем суффиксам.

Для того чтобы посчитать для каждого суффикса такое количество пар, воспользуемся бором (для справки см. алгоритм Ахо-Корасик на сайте e-maxx, раздел «Бор. Построение бора»). Построим по входному набору слов два бора: один будет содержать все слова, как они заданы во входных данных, а другой будет содержать перевёрнутые слова. Обойдём бор, содержащий перевёрнутые слова. Каждый раз, когда мы будем заходить в терминальную вершину, поднимемся из этой вершины вверх до корня, параллельно спускаясь по таким же символам в боре, содержащем исходные слова. Если в процессе этого подъёма/спуска мы попадаем в терминальную вершину в боре с исходными словами, то мы должны увеличить на один счётчик для суффикса, в котором сейчас находимся в боре с перевёрнутыми словами. Если в процессе подъёма мы вышли из бора с исходными словами, подъём можно прекратить.

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

Сложность решения: O(sumL), где sumL — суммарная длина всех слов.

Задача E (Дорожный вопрос)

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

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

После того как новый граф построен, нужно найти в нём кратчайший путь между теми вершинами, которые соответствуют сильно связным компонентам, содержащим вершины 1 и n исходного графа. Это можно сделать либо алгоритмом Дейкстры, либо методом динамического программирования, учитывая то, что полученный в результате сжатия сильно связных компонент граф не имет циклов. Также отдельно нужно рассмотреть начало путешествия, поскольку налог можно по условию задачи платить только в момент въезда в какой-то город.

Задача F (Место под столицу)

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

Остаётся просто аккуратно провести все вычисления; использование функции atan2() позволяет обойти большинство «подводных камней». Без использования atan2() проблемы с точностью возникают в случае двух близких точек с большими радиусами; в этом случае помогает вместо арккосинуса во избежание потерь точности использовать арксинус.

Второй отборочный раунд и его разбор были подготовлены rng_58, snuke, snarknews и Gassa.

Во втором раунде турнира «Яндекс.Алгоритм» хотя бы одну попытку сделало 495 участников, хотя бы одну задачу из них решило 425. По задаче A было сделано 503 попытки, из них 73 успешных, по задаче B — 11 попыток (2 успешных), по задаче C — 472 попытки (76 успешных), по задаче D — 846 попыток (386 успешных), по задаче E — 42 попытки (16 успешных) и по задаче F — 624 попытки (182 успешных).

Результаты тестового прорешивания позволяли надеяться на то, что количество участников, сдавших 5 задач, будет выше, чем в первом раунде, и что победители сдадут по 6 задач. Однако оценка оказалась завышенной. Ближе к середине раунда определились двое лидеров — tourist и eatmore, сдававшие все задачи «втёмную». Далее шла целая группа преследователей, у каждого из которых было сдано не более двух задач «втёмную». Первым сдал 5 задач cgy4ever из Китая, у которого задача C была сдана «втёмную»; на 75-й минуте по 5 задач сдали maciej.klimek (maciejk) из Польши, Jedi_Knight (ivan.popelyshev) и burunduk3. На 77-й минуте пятую задачу сдаёт tourist и выходит на первое место с пятью задачами «втёмную». На 80-й минуте свою пятую задачу, причём также «втёмную» сдаёт eatmore; это оказывается задача B, которую до этого не сдал ни один участник. Тем не менее, tourist удерживает лидерство. За минуту до завершения контеста задачу E, ставшую для неё пятой, сдаёт natalia и с четырьмя задачами «втёмную» из пяти выходит на третье место.

После системных тестов выясняется, что в первой тройке сумел удержаться только tourist, у которого прошли все 5 «тёмных» попыток. Впрочем, он уже обеспечил себе участие в финале по итогам первого отборочного раунда, так что «проходным» становилось пятое место. У eatmore не прошла задача E, которую он сдавал предпоследней; у natalia — задача F, которую она также сдавала предпоследней. Зато последние отправленные задачи — решённая только двумя участниками (кроме eatmore, это s-quark из Китая) B для eatmore и отправленная на 1:39 E для natalia — системное тестирование прошли.

В результате второе место занял vepifanov, третье — yeputons, сдавшие «втёмную» только задачу D на 5-й минуте. Все последующие участники сдавали все задачи «в открытую». Четвёртое место занял Jedi_Knight (ivan.popelyshev), пятое, последнее из «проходных»,— peter50216 из Тайваня.

Задача A (Степени вершин)

Заметим, что если сумма всех d_i не равна 2(N - 1), то d не может быть последовательностью степеней вершин дерева, поэтому нужно вывести «None». В противном случае, несложно доказать, что всегда существует дерево, для которого d является последовательностью степеней вершин.

Пусть c — количество таких i, что d[i] ≥ 2. Есть несколько случаев:

1. c = 0. В этом случае d = {1, 1}. Очевидно, ответ — «Unique».
2. c = 1. Дерево должно быть «звездой». Ответ снова «Unique».
3. c = 2. Есть две вершины степени  ≥ 2. Обозначим их s и t. Должно быть ребро, соединяющее s и t, а все остальные ребра соединяют одну из вершин {s, t} с листом. Таким образом, ответ снова «Unique».
4. c = 3. Есть три вершины степени  ≥ 2. Обозначим их s, t и u. Рассмотрим три пары вершин {s, t}, {t, u} и {u, s}. Ровно две из них должны быть соединены ребром (если все три соединены ребром, то в графе образуется цикл; если одна или менее пар соединены ребром, то граф становится несвязным), поэтому есть три способа их соединить. Если степени вершин s, t, u все совпадают, все три получающихся дерева изоморфны, поэтому ответ — «Unique». Иначе ответ — «Multiple».
5. c ≥ 4. Если последовательность степеней, отсортированная по возрастанию, имеет вид {1, 1, 2, ..., 2}, то дерево должно быть цепочкой, поэтому ответ — «Unique». Иначе есть хотя бы одна вершина степени  ≥ 3. Можно построить два неизоморфных дерева, используя эту вершину: один способ — это составить цепочку вершин степени >=2 и прикрепить к ним листья, а другой — соединить три цепочки в одной общей вершине. В этом случае ответ — «Multiple».

Задача B (Лягушки)

Пусть f(t) — позиция лягушки k в момент времени t. Нас просят найти минимальное такое t, что t - f(t) ≥ d. Заметим, что t - f(t) — неубывающая функция, так как для любого t значение f(t + 1) - f(t) — это 0 или 1. Так как t - f(t) монотонно, мы можем использовать бинарный поиск. Основная часть решения состоит в подсчете f(t).

Предположим для простоты, что k = 2 (в противном случае мы можем повторить аналогичный алгоритм k - 1 раз). Назовем число n хорошим, если сумма высот между кочками 1 и n делится на m. «Хорошесть» имеет период m(p - 1), то есть n — хорошее тогда и только тогда, когда — хорошее. Рассчитаем и запомним в таблице для каждого n ≤ m(p - 1), является ли оно хорошим. Получается, что f(t) — это (количество хороших чисел между 1 and t), поэтому мы можем быстро вычислить его, используя таблицу.

Задача C (Зеленый треугольник)

Мы хотим посчитать сумму ориентированных площадей треугольников pqr для всех троек (p, q, r), перечисленных по часовой стрелке. Если зафиксировать точки p и q, ориентированная площадь треугольника pqr будет линейной функцией координат точки r, поэтому нам достаточно знать сумму всех абсцисс и сумму всех ординат всех точек в одной полуплоскости относительно прямой pq.

Зафиксируем точку p. Отсортируем все остальные точки по часовой стрелке относительно точки p и обозначим их в этом порядке p₀, ..., p_n - 2. Тогда мы можем использовать алгоритм двух указателей: будем поддерживать два индекса i и j. Здесь j — это наибольший индекс, удовлетворяющий условию «три точки p, p_i, p_j перечислены по часовой стрелке». Мы растим i от 0 до n - 2 и поддерживаем j. Когда мы увеличиваем i, j никогда не уменьшается, поэтому суммарное количество изменений i и j ограничено O(n). Суммарно алгоритм работает за время .

При указанных в задаче ограничениях на координаты возникают проблемы с точностью во время вычисления площади: точности double в случае треугольников малой площади, но большого периметра не хватает. Особенно эта проблема актуальна для Java, где тип long double отсутствует, а при использовании встроенного типа BigInteger решение не укладывается в Time Limit.

В качестве варианта рекомендуется при вычислении хранить сумму площадей для фиксированного основания треугольника как в double, так и в 64-битном целом: тогда по double определяются старшие 52 бита результата, а в 64-битном целом хранятся младшие 64 бита.

Задача D (MathWorlds)

Это самая простая задача. Нужно перебрать все операторы и посчитать количество операторов, удовлетворяющих условию «x <оператор> y = z». Особо надо рассмотреть случай y = 0, например, вообще исключив при y = 0 проверку оператора деления. Вариант «привести деление к умножению» не работает, например, для теста 0 0 1, который создал проблемы многим участникам.

Задача E (Маленькие циклы)

Свойства в условии задачи эквивалентны следующему:

1. У G есть остовное дерево. Зафиксируем какое-нибудь остовное дерево T и назовем ребра T «ребрами дерева», а остальные — «внешними ребрами».
2. Если e = {u, v} — внешнее ребро, то расстояние между u и v в T равно двум.
3. Для каждого внешнего ребра e = {u, v} покрасим путь между u и v в T. Тогда никакое ребро не покрашено дважды..

Исходная задача сводится к следующей: дано дерево, и некоторые ребра в нем покрашены. На каждом шаге можно выбрать путь длины 2 и покрасить его (при этом нельзя красить ребро, если оно уже покрашено). Какое максимальное количество шагов можно сделать?

Эта задача может быть решена жадно. «Подвесим» дерево за какую-нибудь вершину и найдем самое глубокое неокрашенное ребро e. Если у ребра e нет соседних неокрашенных ребер, то его покрасить невозможно — проигнорируем его. Если у ребра e есть соседнее неокрашенное ребро (обозначим его e₂) из той же вершины-родителя, то нужно покрасить e и e₂ одновременно, иначе мы не сможем покрасить оба ребра. Если у ребра e есть только соседнее ребро, ведущее в вершину-родителя e в свою очередь из ее вершины-родителя, то нужно покрасить e и родительское ребро одновременно. После того, как мы либо покрасили e, либо проигнорировали e, снова находим самое глубокое неокрашенное ребро и повторяем процесс.

Задача F (Шарообмен)

Если ответ для (p, q, r, s) — «Yes», то ответ для (p + 2, q, r, s) — тоже «Yes». Это верно, потому что если выполнить одну и ту же операцию два раза подряд, то ничего не изменится. Интуитивно понятно, что если p достаточно большое, то ответы для (p, q, r, s) и (p + 2, q, r, s) совпадают. На самом деле можно доказать, что если p ≥ 48, то это верно. Используя эти наблюдения, можно предполагать, что p, q и r малы, поэтому можно использовать динамическое программирование для решения задачи (dp[p][q][r][s]: можно ли переделать s в «RGB», используя операции p, q, r раз соответственно?).

Вот формальное доказательство. Построим граф из 48 вершин. Каждая вершина соответствует набору значений: (четность p, четность q, четность r, s). Последовательность операций соответствует пути в этом графе. Если этот путь достаточно длинный, то в нем есть циклы. Если цикл содержит p', q' и r' раз соответсвтующие операции, то эти числа четны, и мы можем удалить цикл и показать, что ответ для (p - p', q - q', r - r', s) — «Yes». Мы можем повторять этот процесс, пока p, q и r не станут не более 48.

Оказывается, можно заменить число 48 на число 3, если поэкспериментировать на компьютере.

В первом отборочном раунде 609 участников послали хотя бы одно решение и 396 послали хотя бы одно правильное решение. Задачи Неквадраты и Раздел королевства были довольно простыми, по обеим было примерно 300 правильных решений. Задача Столбики монет была относительно простой, ее решило 145 участников. Три оставшиеся задачи оказались сложнее. Задача Стикеры могла бы быть очень сложной задачей на строки, но маленький размер входных данных позволял решать задачу с помощью динамического программирования — задачу сдали 22 участника. Задачу Ассистенты решило 13 участников; в ней требовалось использование бинарного поиска, жадности и некоторых известных структур данных. Никто не смог решить за время соревнования задачу Государственные дороги, которая была изящной задачей на теорию графов с решением, которое было легко запрограммировать, но сложно придумать.

Поздравляем Kenny_HORROR, единственного участника, решившего 5 задач. Также поздравляем Petr, tourist и eatmore, которые решили 4 задачи с отрицательным штрафным временем и прошли в финал.

Задачи этого раунда подготовлены польской командой: Tomasz Idziaszek ( Раздел королевства ), Jakub Łącki ( Государственные дороги ), Marcin Pilipczuk ( Ассистенты ), и Jakub Radoszewski ( Неквадраты, Столбики монет ). Отдельное спасибо профессору Costas Iliopoulos за идею задачи Стикеры.

Решения, тесты и разбор были подготовлены marek.cygan, monsoon и jakubr.

Задача A (Ассистенты)

В этой задаче нам нужно найти минимальное количество дней, за которые можно завершить n исследовательских задач. Профессор может выполнить i-ю задачу за p_i последовательных дней, либо передать ее ассистенту, который выполнит ее за a_i последовательных дней. Каждый ассистент может выполнить только одну задачу, и профессору требуется один день на поиск ассистента.

Мы покажем, как проверить, можно ли завершить весь проект за k дней. Затем остается только использовать бинарный поиск по ответу.

Легко видеть, что существует оптимальное расписание, в котором профессор сначала ищет ассистентов, а потом выполняет задачи, которые никому не передал. Кроме того, это означает, что нам не нужно беспокоиться о том, чтобы профессор выполнял свои задачи в последовательные дни. Формально говоря, если есть некоторое оптимальное расписание, в котором профессор передает подмножество задач ассистентом и выполняет остальные задачи сам (но необязательно в последовательные дни), то существует оптимальное расписание, в котором профессор передает задачи из подмножества T в течение первых #T дней, а потом выполняет все оставшиеся задачи сам, каждую задачу — в непрерывную последовательность дней. Таким образом, если профессор передаст задачи из T, он закончит оставшиеся задачи в срок тогда и только тогда, когда .

Теперь приведем алгоритм, который будет проверять, существует ли такое T. Рассмотрим дни d = k, k - 1, ..., 1 в обратном хронологическом порядке, и в некоторые из этих дней мы будем передавать задачи ассистентам. Предположим, что на день d мы уже передали подмножество задач за дни после d. Пусть — множество задач, которые могут быть переданы в день d таким образом, что ассистент успеет выполнить их в срок. Главное наблюдение состоит в следующем: если непусто, то мы можем в день d жадным образом передать задачу , которая максимизирует значение p_i.

Теперь докажем, что алгоритм работает правильно. Предположим, что существует расписание S, которое в течение дней после d совпадает с нашим. Если в расписании S задача i передается ассистенту в день d, то все хорошо. Иначе в расписании S в день d профессор либо передает задачу j ≠ i ассистенту, либо выполняет задачу j сам (в последнем случае, возможно, j = i).

В первом случае профессор передает асистенту задачу j ≠ i. Тогда (так как ассистент выполнит задачу в срок) и (мы предполагаем, что расписание S совпадает с нашим планом после дня d). Благодаря нашему жадному выбору имеем p_i ≥ p_j. Если в S профессор передает ассистенту задачу i в день d', то d' ≤ d (так как и S совпадает с нашим планом в последующие дни), и мы можем в S переставить дни, в которые мы передаем ассистентам задачи i и j. Иначе, если в S профессор выполняет задачу i самостоятельно, мы можем изменить S следующим образом: мы передаем ассистенту задачу i в день d и выполняем задачу j в те дни, в которые профессор ранее выполнял задачу i (мы можем так сделать, потому что p_i ≥ p_j).

Во втором случае профессор выполняет задачу j в день d. Если j = i, профессор может вместо этого передать ассистенту эту задачу в день d (так как ). Иначе, если j ≠ i, профессор может передать задачу i в день d и вернуть пропущенный день, выполнив задачу j в момент, в который профессор работал над задачей i (передавая или выполняя ее) в расписании S.

Во всех случаях мы получаем оптимальное расписание, в котором профессор делеигрует задачу i в день d, таким образом основное наблюдение доказано.

Как быстро мы можем реализовать данный алгоритм? Выбор максимума в множестве может быть реализован с помощью бинарной кучи, отсортированной по p_i. Переходя от дня d + 1 к дню d, мы добавляем элементы из в кучу (то есть задачи с a_i = k - d; для этого нужно отсортировать задачи по a_i) и удаляем максимальный элемент (и добавляем его в T).

Заметим, что нам не нужно проходить по всем дням, мы можем начать с дня d = min(k, n), так как нет нужды передавать задачи ассистентам после n-го дня. Таким образом, все решение (с фиксированным k) работает за время .

Мы можем улучшить его, если будем перебирать не дни, а задачи, отсортированные по невозрастанию p_i. Каждый раз мы будем пытаться передать задачу i в самый последний день из {1, 2, ..., d_i}, где d_i = min(k - a_i, n)}, в который еще ни одна задача не передается. Несложно видеть, что полученное множество T будет таким же, как в предыдущем алгоритме. Эта операция выбора последнего свободного дня может быть выполнена за почти линейное время, используя структуру леса непересекающихся множеств. Каждое множество содержит свободный день d и все дни после него, в которые какие-то задачи передаются. Теперь выбор последнего свободного дня сводится к нахождению множества, которое содержит d_i, получения минимального элемента d' в этом множестве, передаче задачи i ассистенту в день d' и объединению данного множества с множеством, содержащим элемент d' - 1.

Давайте теперь оценим окончательную временную сложность. Так как одним из решений является передача всех задач ассистентам, ответ всегда будет меньше, чем n + A, где A = max_iai. Добавляя бинарный поиск, мы получаем решение, работающее за время .

Задача B (Раздел королевства)

В этой задаче нам нужно разделить сетку n × m на максимальное количество частей различных размеров, являющиеся связными компонентами, состоящими из единичных квадратов. Мы должны представить пример такого разделения, используя буквы из множества для обозначения получающихся частей. Решение этой задачи получается в три шага.

На первом шаге мы забудем на время про требование связности и определим, какие размеры частей приведут к максимальному результату. Ответ прост: части должны иметь размеры 1, 2, 3, ... Если последняя часть меньше требуемого, мы объединяем ее с предпоследней частью.

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

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

Одно из возможных правильных решений состоит в том, чтобы пометить каждую часть наименьшей буквой из тех, что еще не встречаются среди пометок ее соседей (и помечать части змейки по порядку). Другая идея состоит в том, чтобы помечать части в первом ряду буквами A и B, во втором ряду использовать C и D, в третьем — E и F, в четвертом снова A и B и так далее (см. картинку справа). Начиная с момента, когда каждая часть покрывает хотя бы один ряд целиком, мы можем начать использовать только две буквы, A и B. Во втором способе мы используем только 6 различных букв.

Интересная задача — определить, каково минимальное количество букв, достаточное для того, чтобы разметить любую сетку.

Вышеприведенный алгоритм может быть легко реализован с временной сложностью O(nm).

Задача C (Неквадраты)

В этой задаче нам нужно проверить, может ли данное положительное целое число n быть представлено в виде произведения k положительных целых чисел, ни одно из которых не является квадратом целого числа. Давайте назовем такое представление неквадратным представлением.

Общий подход к задаче — динамическое программирование по множеству делителей n. Все делители n можно найти за время . Пусть D(n) — число делителей n. Оказывается, для n ≤ 10⁹ верно D(n) ≤ 1344.

Мы вычислим двумерную булеву матрицу , где — истина если и только если делитель d может быть представлен в виде произведения j неквадратов. При вычислении используется следующая булева формула, которяа работает при j ≥ 1 и :

Временная сложность этого решения составляет (логарифм появляется из-за использования структуры map или аналогичной для хранения делителей n. Сложность по памяти составляет O(D(n)k).

Можно улучшить время работы этого решения, если заметить, что параметр k ограничен сверху числом , что в нашем случае не более 29. Действительно, для ответ всегда «NO» (доказательство следует из следующего решения).

Есть также гораздо более простое решение, которое рассматривает разложение n на простые множители. Пусть n = p₁^α₁p₂^α₂... p_m^α_m, где p_i — различные простые числа. Тогда решение состоит в следующем:

1. Если α₁ + α₂ + ... + α_m < k, вывести «NO».
2. Иначе, если m > 1, вывести «YES».
3. В оставшемся случае m = 1. Если k - α₁ четно, вывести «YES», иначе вывести «NO».

Обоснуем это решение. Ответ в случае (1) следует из того факта, что у любого делителя-неквадрата есть простой делитель. Для m = 1 нам нужно просто проверить, может ли α₁ быть представлено как сумма k нечетных целых чисел, что возможно тогда и только тогда, когда четность k и α₁ совпадает. Это дает пункт (3) алгоритма.

Наконец, рассмотрим пункт (2). Нам нужно показать, что, если α₁ + α₂ + ... + α_m ≥ k и m > 1, то существует неквадратное представление n. Давайте возьмем в качестве первых k - 1 неквадратов простые делители n: сначала α₁ раз делитель p₁, затем α₂ раз делитель p₂ и так далее. В качестве последнего делителя, d, мы возьмем произведение оставшихся простых делителей. Если d не является квадратом целого числа, мы построили требуемое представление. Иначе мы заменим последний делитель на d / p_m, а первый делитель — на p₁ p_m, таким образом получая требуемое представление.

Это решение требует только найти разложение n на простые множители и работает за время .

Задача D (Столбики монет)

В этой задаче m золотых и серебряных монет разложены в n кучек разной высоты. Нам нужно перераспределить монеты таким образом, чтобы образовалось максимальное количество одноцветных кучек (в одноцветной куче либо все монеты золотые, либо все монеты серебряные). Нам разрешается выполнить сколько угодно операций перестановки двух монет, которые находятся на одинаковой высоте в разных кучках.

Пусть k — ответ, то есть максимальное количество одноцветных кучек, которого можно достичь. Выполним бинарный поиск по k. С этого момента нам остается научиться отвечать на следующий вопрос: для данного k проверить, можно ли получить k одноцветных кучек. Очевидно, оптимально попытаться сделать k самых маленьких кучек одноцветными.

Так как количество операций не ограничено, нашу задачу можно переформулировать следующим образом. Пусть h — высота k-й минимальной кучки. Для каждого уровня высоты 1, ..., h мы знаем общее количество золотых и серебряных монет на этом уровне. Нам нужно проверить, достаточно ли этих чисел, чтобы сформировать k одноцветных кучек. Эта задача будет сведена к подсчету пересечения O(h) отрезков.

Для начала рассмотрим каждый уровень по отдельности. Предположим, что нам этом уровне есть g_i золотых и s_i серебряных монет, а k минимальных кучек содержат в сумме t_i монет на этом уровне. Используя эти числа, мы можем рассчитать отрезок [a_i, b_i] такой, что тогда и только тогда, когда возможно добиться того, чтобы на i-м уровне выбранных кучек оказалось в сумме x золотых и t_i - x серебряных монет. Отметим, что отсюда будет следовать, что аналогичный отрезок для возможного количества серебряных монет на i-м уровне — это [t_i - b_i, t_i - a_i].

Теперь нам нужно убедиться, что отрезки для разных уровней позволяют нам найти корректное решение. Мы пройдем от самого нижнего к самому верхнему уровню. На уровня i нам нужно пересечь отрезок [a_i, b_i] с [a_i - 1, b_i - 1] и аналогично отрезки для количества серебряных монет. Таким образом мы получим один обновленный отрезок [a_i, b_i], который мы далее будем использовать для обновления отрезков на более высоких уровнях.

Это решение работает за время .

У этой задачи также есть решение за линейное время. Пусть g_i — общее количество золотых монет, которые находятся на i-м уровне. Пусть g'_i — максимальное количество кучек, которые можно сформировать таким образом, чтобы у них у всех были только золотые монеты на i-м уровне и ниже. Можно легко вычислить g'_i при помощи следующего рекуррентного соотношения:

Аналогично мы определяем s_i и s'_i для серебряных монет.

Пусть h_i — высота i-й кучки, и предположим, что кучки отсортированы по невозрастанию высоты, то есть h₁ ≥ h₂ ≥ ... ≥ h_n. Мы пройдем по кучкам и «раскрасим» их (делая их одноцветным), когда это возможно. Пусть мы рассматриваем i-ю кучку, и мы уже раскрасили кучки с номерами 1, 2, ..., i - 1 таким образом, что всего есть G золотых кучек и S серебряных.

Мы можем сделать i-ю кучку золотой, если и только если g'_hi > G. В таком случае мы покажем, что существует оптимальное решение, в котором эта кучка сделана золотой, а кучки 1, 2, ..., i - 1 раскрашены так же, как в нашем решении. Рассмотрим произвольное оптимальное решение, в котором кучки 1, 2, ..., i - 1 раскрашены так же, как в нашем решении. Пусть j ≥ i — самая высокая золотая кучка в этом оптимальном решении (она должна существовать, иначе мы можем добавить i-ю кучку и получить решение лучше). Можно поменять местами монетки из j-й кучки и i-й кучки и, так как g'_hj + 1 ≥ g'_hi > G, у нас есть достаточно много золотых монет, чтобы поместить их в i-ю кучку выше уровня h_j.

Аналогично, если мы не можем сделать i-ю кучку золотой, но можем сделать ее серебряной (то есть s'_hi > S), существует оптимальное решение, в котором мы так и делаем.

Иначе g'_hi + s'_hi ≤ G + S, что означает, что мы не можем «раскрасить» более чем G + S кучек высоты не менее h_i.

Так как мы можем отсортировать кучки по высоте с помощью сортировки подсчетом, описанный алгоритм работает за время O(n + m).

Задача E (Государственные дороги)

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

Мы представим рандомизированное решение этой задачи, которое легко запрограммировать, но довольно сложно придумать. Для каждого ребра, добавляемого в граф, мы выберем случайный целый вес. Для каждой вершины мы храним в ячейке массива результат операции , примененной к весам всех ребер, инцидентных этой вершине. Заметим, что такие значения можно обновлять за время O(1) при добавлении и удалении ребер.

Главное наблюдение состоит в том, что множество вершин {u₁, u₂, ..., u_k} представляет собой набор связных компонент тогда и только тогда, когда каждое ребро графа инцидентно либо двум, либо ни одной из вершин u_i. Таким образом, чтобы ответить на запрос, мы вычисляем:

где обозначает операцию . Если полученное значение не равно нулю, мы знаем, что ответ — «NO». Иначе с высокой вероятностью ответ — «YES». Вероятность неправильного положительного ответа — , где M — максимальный вес ребра. Эта вероятность оказывается достаточно мала при M = 2³² или M = 2⁶⁴.

Все решение работает за линейное время от размера входных данных.

Задача F (Стикеры)

В этой задаче нам дано n видов сткеров s₁, ..., s_n, где каждое s_i является словом длины d. Нас просят найти минимальное количество стикеров, которые нужны, чтобы составить данное слово t длины m.

Мы предложим простое решение, основанное на динамическом программировании. Обозначим как dp[i] минимальное количество стикеров, необходимое для того, чтобы составить ровно суффикс t[i..m], а как такое же число, но при этом разрешим стикерам выходить за границу и накрывать позиции из t[i - d..i - 1] (но не обязательно при этом правильными буквами). Ответ к задаче — это dp[1].

Как посчитать dp[i]? Ясно, что i-я позиция t должна быть в какой-то момент покрыта стикером, который начинается в этой позиции. Так как все стикеры имеют одинаковую длину, мы можем ограничить себя тем, чтобы положить этот стикер самым первым или самым последним. Это дает нам два случая:

1. Для некоторого j имеем s_j = t[i..i + d - 1]. Тогда мы можем составить суффикс t[i + d..m], возможно накрывая некоторые буквы из t[i..i + d - 1], и затем положить стикер s_j, начиная с позиции i. В этом случае мы используем стикеров.
2. Имеем s_j[1..d'] = t[i..i + d' - 1] для некоторого j и некоторого d' ≤ d. Тогда мы можем положить s_j, начиная с позиции i, затем составить t[i + d'..m] с ограничением, что нам нельзя изменять буквы перед позицией i + d'. В этом случае мы используем 1 + dp[i + d'] стикеров.

Если для каждого i мы знаем максимальное l[i], такое что t[i..i + l[i] - 1] является префиксом некоторого стикера, то случай (1) возможен, когда d = l[i], и результат случая (2) равен min_{1 ≤ j ≤ l[i]}(1 + dp[i + j]).

Мы вычисляем аналогично, но теперь вместо множества всех стикеров мы рассмотрим множество всех суффиксов стикеров. Таким образом мы вычисляем l[i] как максимальное число, такое что t[i..i + l[i] - 1] является подстрокой некоторого стикера.

Это решение может быть реализовано с временной сложностью O(mnd²). Интересно, что эта задача может быть решена за линейное время от размера входа, даже с использованием стикеров разной длины, но это решение гораздо сложнее.

Квалификационный раунд и его разбор были подготовлены Chmel_Tolstiy, aropan, Romka, SobolS, Ra16bit, snarknews и Gassa.

В квалификационном раунде турнира Яндекс.Алгоритм стартовало виртуальный контест 1732 участника, хотя бы одну попытку сделало 1606 участников. Из них 1558 решили хотя бы одну задачу. Отметим, что количество зарегистрировавшихся для участия в турнире — а это 3397 участников — практически вдвое превосходит количество участников, стартовавших контест. С чем это связано — непонятно.

Так как квалификационный раунд проводился в виде виртуального контеста, то участники могли выбрать наиболее удобное для себя время. Наибольшее количество участников онлайн (около 280) было в момент старта раунда, наименьшее — в районе между 3 и 4 часами ночи по Московскому времени (около 20 участников).

Первым хронологически все 6 задач сдал Scott.Ai из Китая; при этом все задачи были сданы «в открытую». Стартовавший почти в 22:00 по Москве i.metelsky (Иван Метельский, Беларусь) сдал задачи A-D «втёмную», E «в открытую» со второй попытки и F «в открытую» с первой и возглавил таблицу с очень неплохим результатом. Однако стартовавший через 4 с половиной часа vepifanov (Владислав Епифанов, Россия) сдал «втёмную» A, B, C, F и «в открытую» D и E с первой попытки, выйдя на первое место по штрафному времени. Уже во вторник утром первую строчку захватывают чемпионы мира из СПб НИУ ИТМО: сначала eatmore (Евгений Капун, победитель финалов ACM ICPC 2009 и 2012), стартовавший около 11 утра, сдаёт все 6 задач «втёмную»... но и он находится на этой строчке всего несколько часов: с той же стратегией, но с лучшим временем его обходит действующий чемпион мира tourist (Геннадий Короткевич, Беларусь). Через сутки после старта квалификации первая тройка выглядит так: Короткевич — Капун — Епифанов. При этом Геннадий Короткевич занял второе место в тестовом раунде, Владислав Епифанов — третье. А победитель тестового раунда — Антон Лунёв (Украина) — стартовал уже ближе к концу времени квалификации. Он сдал «втёмную» задачи A, B, F, D, затем сдал «в открытую» задачу E со второй попытки, затем сдал «втёмную» задачу C и вышел на итоговое третье место, сместив Епифанова на четвёртое. Таким образом, все три победителя тестового раунда оказались в Top4, но в другом порядке. Евгений Капун также получил право участия в отборочных раундах по результатам тестового, так что лучшим из тех, кто ещё не имел права участия в отборочном раунде, оказался занявший в итоге пятое место Иван Метельский. Всего по 6 задач решили 34 участника, при этом наилучший результат участника, сдававшего все задачи «в открытую», — 9-10 место.

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

Задача A (Древний баскетбольный матч)

В этой задаче требовалось просто сделать то, что написано в условии. Достаточно завести две переменные для подсчёта очков каждой команды и, считывая записи о бросках, увеличивать соответствующую переменную на необходимое количество очков. Узнать, какую переменную нужно увеличивать, можно с помощью оператора if.

Задача B (Простая задача)

Перенесём 1 в левую часть — получим k² - 1 = p₁·p₂, или, раскладывая левую часть на множители, (k - 1)(k + 1) = p₁·p₂. Так как k по условию задачи больше двух, то оба сомножителя в левой части не равны единице, а раз так, то (k - 1) = p₁ и (k + 1) = p₂ (без ограничения общности считаем, что p₂ > p₁). Действительно, левая часть должна делиться и на p₁, и на p₂, то есть если k - 1 = a·p₁, а k + 1 = b·p₂, то (k - 1)(k + 1) = ab·p₁·p₂ = p₁·p₂, так как a и b — целые положительные, то a = b = 1, что и требовалось доказать. Если бы k - 1 делилось на p₂, то оказалось бы, что k - 1 = p₂, k + 1 = p₁, но это противоречит тому, что p₂ > p₁.

Таким образом, задача сводится к поиску таких k, что k - 1 и k + 1 — простые (так называемые «простые числа-близнецы»; интересно, что задача о том, конечно или бесконечно количество пар таких чисел, в настоящий момент так и не решена).

С предложенными во время тура ограничениями это можно сделать любым способом, даже перебирая все (а не только чётные) k и при проверке числа на простоту перебирая все делители до данного числа. Учитывая, что n ≥ 4, «пустой ответ» невозможен, так как k = 4 удовлетворяет условию задачи.

Ещё вариант — раскладывать k² - 1 на простые множители и проверять, что таких множителей ровно два.

Задача C (Настольная игра)

Ответ на первый вопрос посчитать очень просто. Это сумма количеств атомов по всем кучкам. Она равна .

Для того чтобы ответить на второй вопрос, давайте сперва несколько переформулируем его. Из теории игр известно, что позиция в такой игре является проигрышной, если количеств атомов по всем кучкам равен 0. Соответственно, нам нужно найти количество первых ходов таких, что после любого из них количеств атомов по всем кучкам будет равен 0. Обозначим . Существует быстрый способ посчитать x. Для этого можно воспользоваться фактом, что для любого неотрицательного целого k справедливо . Значит, .

Если мы зафиксируем номер кучки i, из которой будем производить первый ход, то количество атомов, которые должны будут в ней остаться после этого хода, определяется однозначно. Оно равно количеств атомов по всем остальным кучкам, то есть . Значит, чтобы из кучки i можно было сделать правильный первый ход, i должно быть строго больше, чем . Это возможно, только если в позиции p, в которой в числе x стоит старший единичный бит, в числе i также стоит единичный бит. Нужно посчитать количество таких i, не превосходящих N. Среди чисел, меньших , их ровно половина. Если в p-м бите числа N стоит единица, то нужно также добавить к ответу .

Задача D (Бесконечная сумма)

Применим несколько преобразований к исходному выражению:

Обозначив , имеем

Теперь нужно только посчитать искомое рекуррентное соотношение и вывести ответ.

Задача E (Лабораторная работа)

Случаи X = 0 или K = 0 являются тривиальными и рассматриваются отдельно.

Понятно, что выгодно, чтобы Гена каждый день решал максимальное количество задач, которое может, а остальных студентов можно распределять по темам, и они могут подстроиться под работу Гены. Если в какой-то теме ещё осталось решить не меньше X задач, то Гена в этот день работает на максимум и решает X задач. Если такой темы нет, то он берет тему с наибольшим количеством задач и решает их, полностью закрывая тему. Таким образом, становится очевидным, какое минимальное количество задач останется после Гены по прошествии некоторого количества дней. Тогда можно двоичным поиском перебирать количество дней, т. е. ответ, затем проверять, успеют ли студенты за этот срок решить оставшиеся после Гены задачи.

Сложность такого решения . Также следует учесть, что нужно предварительно отсортировать темы по значению для поиска тем с максимальным количеством задач, когда у Гены уже нет возможности решать по X. Итоговая асимптотика с учётом того факта, что , и свойств логарифма, получается .

Альтернативное решение заключается в рассмотрении оптимальной стратегии для студентов. Зная, как оптимально действует Гена, можно предположить, как должны действовать студенты: вначале они должны решать тему с наименьшим значением и решать эту тему, пока не станет равным нулю. Когда такие темы закончатся, а задачи ещё останутся, то они могут выбирать любую тему и решать её, пока в ней не закончатся задачи. Таким образом, надо рассмотреть что произойдет первым: либо у Гены раньше закончатся темы с A_i ≥ X, либо у студентов закончатся темы с .

Сложность .

Задача F (Атомы: туда и обратно)

Количество кучек при каждом разделении удваивается. Из этого следует, что если N не является степенью двойки, то заданное состояние никак не получится и ответ «NO».

Если посмотреть последнее разделение, то есть разделение состояния, предшествующего заданному, то из каждой кучки была получена кучка размера X. Значит, как минимум половина кучек будет одинакового размера X. Тогда эти кучки можно отбросить и перейти к такой же задаче с N / 2 кучками. Если на каком-то шаге среди кучек нет хотя бы половины одинаковых, то ответ «NO».

Для решения задачи можно сгруппировать заданные кучки по размеру. Затем можно, используя кучу (приоритетную очередь), просимулировать вышеописанный процесс. Также можно жадно разбивать каждую группу одинаковых по размеру кучек на кучки, размеры которых являются степенями двойки, так, чтобы каждая степень получилась ровно один раз, кроме нулевой степени (с нулевой степенью должно быть две части).

Сложность .

Тестовый раунд и его разбор были подготовлены snarknews и Gassa. Задачи тестового раунда уже использовались ранее в других соревнованиях. Все последующие раунды будут состоять из новых оригинальных задач, и вы все еще можете зарегистрироваться и поучаствовать в квалификационном раунде.

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

На момент окончания раунда первое место занимал tourist, сдавший все задачи, кроме B, «втёмную». Второе место занимал vepifanov, сдавший A, C и D «втёмную», а B и F — «в светлую» (причём каждую из них — с одной штрафной попыткой), третье — Anton_Lunyov, сдавший «втёмную» только задачу C. У остальных участников было сдано менее пяти задач. После системных тестов выяснилось, что у tourist было неверное решение по A, а у vepifanov — по D; тем самым, единственным участником, сдавшим 5 задач, стал Anton_Lunyov. У tourist — второе место, у vepifanov — третье.

Несколько странно, что задачи B и E (несмотря на не требующие особых знаний элементарные решения как в B, так и в E) остались в значительной степени «невостребованными»: все решившие эти задачи участники вошли в первую тройку, причём tourist решил E, а Anton_Lunyov и vepifanov — B.

Определённую сложность для участников, как оказалось, представляет работа со входными и выходными файлами: с этим было связано более 90% всех заданных жюри вопросов. Так что в последующих раундах Яндекс.Алгоритма файловый ввод-вывод решено не использовать.

Задача A (Окружности)

Данная задача является усложнённым вариантом задачи с нулевого («пилотного») Открытого Кубка, проходившего в мае 2004 года, или же упрощённым до двумерного случая вариантом задачи с Гран-При Москвы 2005 года.

Из формулы для площади треугольника S = abc / 4R получаем, что R = abc / 4S, где a, b и c — длины сторон треугольника. Учитывая, что координаты вершин целые, квадраты длин сторон являются целыми числами, равно как и удвоенная площадь треугольника, и можно вычислить R² точно, представив в виде отношения двух целых a²·b²·c² и 16S².

Так как координаты не превосходят 1400, то максимальное произведение сторон не превосходит 1400⁶·2, что меньше, чем , и вычисления можно производить в беззнаковых 64-битных целых. При этом при сравнении дробей потребуется или использовать встроенные типы для работы с длинными числами (в тех языках, в которых они есть), либо использовать модулярную арифметику, либо вычислять НОД, либо хранить старшую часть числа отдельно...

Отметим, что обычного double недостаточно даже без учёта погрешности вычислений: существует пример двух треугольников, радиусы описанных окружностей для которых различаются менее, чем на 2^- 52. Например, это треугольники с вершинами (0, 0), (1312, 164), (134, 1372) и (0, 0), (1351, 169), (106, 1317).

Вышеприведённый пример был построен при помощи следующего перебора: закрепляем одну вершину в начале координат, другие две — в точках (1400, 0) и (0, 1400), перебираем координаты этих двух точек в некоторой окрестности, вычисляя при этом радиусы описанных окружностей для всех треугольников, сортируем их и находим минимальную разность соседних радиусов после сортировки.

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

Задача B (Три дроби)

Эта задача впервые была предложена на Гран-При Москвы в 2005 году в более простой формулировке (без мультитеста).

Проще всего эту задачу решить предрасчётом.

Для заданных ограничений на n и количества запросов имеет смысл перед обработкой запросов построить полную таблицу ответов. Учитывая, что если n — составное число, и для всех простых чисел, меньших n, задача решена, то, представив n в виде произведения a·p, где p — простое, получаем решение . Таким образом, достаточно сначала предпросчётом построить таблицу для всех простых чисел и для n = 4, а затем вычислить вышеуказанным способом значения для остальных чисел.

Берём самую грубую оценку. Так как , то . Так как a > b > c, то , а значит , тем самым ; из аналогичных соображений и . Соответственно, перебираем для всех простых n значения в указанных диапазонах и проверяем, делится ли nbc на 4bc - nb - nc нацело. Если делится, — требуемая тройка получена.

Построенный таким образом предрасчёт даже на очень медленном CoreDuo 1.6Ghz занимает менее минуты. В коде достаточно хранить только b и c, вычисляя оставшееся число по формуле . При этом размер кода не будет превосходить 50k, что меньше, чем source limit.

Кроме того, можно перебрать значения c и попытаться разложить разность в сумму двух «египетских» дробей, использовав алгоритм Фибоначчи; в этом случае решение укладывается в Time Limit без предрасчёта (именно такие решения и сдали оба участника, решивших задачу).

Эта задача представляет собой частный случай известной математической проблемы — гипотезы Эрдёша-Штрауса. В общем случае проблема на данный момент не решена, однако для всех n ≤ 10¹⁴ соответствующее разложение существует.

Для любителей конструктивных решений — несколько формул.

• Если n = 3k + 2, то получаем ,
• Если n = 4k, то получаем ,
• Если n = 4k + 2 и k > 1, то ,
• Если n = 4k + 3, то получаем ,
• Если n = 8k + 5, то получаем .

То есть конструктивной формулы не существует только при n = 24k + 1.

Задача C (Выбери цифры)

Данная задача была впервые предложена на школьном кружке в Санкт-Петербургском ДТЮ в 2006 году.

Эта задача проста и допускает множество различных способов решения. Остановимся на некоторых из них. Далее мы считаем, что s — это заданная строка, а res — искомый результат.

Решение 1

Можно просто перебрать четвёрки позиций, которые мы выберем. Вот примерный код на языке Pascal:

res := 9999;
for i := 1 to 5 do
  for j := i + 1 to 6 do
    for k := j + 1 to 7 do
      for l := k + 1 to 8 do
        res := Min (res, StrToInt (s[i] + s[j] + s[k] + s[l]));

Решение 2

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

res = "".join (min (itertools.combinations (s, 4)))

Решение 3

Перебор можно организовать рекурсивно. Вот функция на языке Java с двумя параметрами: позицией p в строке s и количеством цифр q, которые осталось взять. Она вызывается из основной программы как recur (8 - 1, 4) и идёт по позициям строки с конца.

int recur (int p, int q) {
  if (q < 0 || p + 1 < q) return 9999;
  if (p < 0) return 0;
  return Math.min (recur (p - 1, q),
    recur (p - 1, q - 1) * 10 + s.charAt (p) - '0');
}

Решение 4

Можно решать эту задачу методом динамического программирования. Два параметра — количество просмотренных позиций i и количество выбранных позиций j. Значение целевой функции f(i, j) — минимальное число, которое можно получить. Из каждого состояния можно пойти вперёд двумя способами: либо выбрать, либо пропустить текущую позицию, после чего переместиться на следующую позицию в строке. Ниже представлен код на языке C/C++. Ответ находится в ячейке таблицы f[8][4].

memset (f, 0x3F, sizeof (f));
f[0][0] = 0;
for (i = 0; i < 8; i++) {
  for (j = 0; j <= 4; j++) {
    f[i + 1][j] = min (f[i + 1][j], f[i][j]);
    f[i + 1][j + 1] = min (f[i + 1][j + 1],
      f[i][j] * 10 + (s[i] - '0'));
  }
}

Задача D (Различные сомножители)

Данная задача была впервые предложена на школьном кружке в Санкт-Петербургском ДТЮ в 2009 году.

Начнём разбор с теста, который имел номер 15: n = 112 500 = 2²·3²·5⁵. Его сложность заключается в том, что нельзя выбирать делитель 2·3 = 6: в противном случае всего делителей получится не больше шести. Вместо этого следует выбрать следующее разложение на семь сомножителей: 112 500 = 1·2·3·5·10·15·25.

Это минимальный тест, на котором не работают некоторые простые, но неправильные решения. Одно из таких решений — жадно выбирать делители, начиная с самых маленьких, пока после добавления очередного делителя d оставшееся число строго больше d. На этом тесте оно находит делители 1·2·3·5·6, и остаётся разложить на делители 625 = 5⁴, но ни 5, ни 25 = 5² взять нельзя.

Авторское решение — перебор. Тривиальный рекурсивный перебор делителей до корня в порядке возрастания успевает отработать менее чем за секунду. Следующая функция на языке C/C++, будучи запущена как recur (n, 1, 0), записывает в res количество делителей, а в массив best — сами делители. Параметры имеют следующий смысл: n — число, которое осталось разбить на множители, k — минимальный следующий делитель, а cur — количество уже выбранных делителей.

void recur (int n, int k, int cur) {
  if (res < cur + 1) {
    res = cur + 1;
    now[cur] = n;
    memmove (best, now, sizeof (best));
  }
  for (int d = k; d * (d + 1) <= n; d++)
    if (n % d == 0) {
      now[cur] = d;
      recur (n / d, d + 1, cur + 1);
    }
}

Как оценить, насколько быстро работает такой алгоритм? Можно заметить, что ответ не очень большой: поскольку произведение первых 13 натуральных чисел больше, чем 10⁹, ответ не превосходит 12. Это означает, что первый if сработает не более 12 раз. Также полезно знать, что у чисел, не превосходящих 10⁹, не более 1344 различных делителей (http://oeis.org/A066150).

Проще всего написать программу для грубой оценки, которая посчитает количество вызовов рекурсивной функции (язык C/C++). Здесь n — число, которое осталось разложить на множители, а k — минимально возможный следующий множитель.

int count (int n, int k) {
  int res = 0;
  for (int d = k; d * (d + 1) <= n; d++)
    res += 1 + count (n / d, d + 1);
  return res;
}

Эта программа отличается от нашего перебора тем, что в recur мы будем заходить внутрь рекурсии не на каждой итерации цикла по d, как в count, а только тогда, когда n делится нацело на d. Зато она позволяет нам использовать максимально возможное n для оценки (хоть и грубой) худшего случая, а не искать то большое число с большим количеством делителей, на котором реальная программа работает дольше всего.

При вызове count (1000000000, 1) результат равен 151 631 365. Если мы учтём, что единицу можно всегда взять отдельно и искать делители, начиная с двойки, то оценка сверху на количество делений будет равна результату count (1000000000, 2) — это число 75 815 682 (в два раза меньше). На самом же деле, поскольку корень из числа порядка 10⁹ имеет порядок 30 000, а делителей до корня не больше 1344 / 2 = 672, понятно, что делений будет в разы меньше. Максимальное число делений и/или взятий остатка от деления по всем тестам жюри оказалось равно 15 395 811.

Есть и более быстрые варианты перебора. Например, можно перебирать не все числа до корня, а только делители числа n, которые можно заранее найти за . Можно также изначально разложить число n на простые множители и искать делители в виде наборов степеней для каждого из этих множителей.

Задача E (Таблица чемпионата)

Данная задача является адаптированным под memory limit=64 MiB вариантом задачи с Гран-При Москвы 2005 года. В первоначальной задаче ограничение по памяти было равно 3Mb, а длины названий команд не превышали 15 символов.

Существует два принципиально различных случая: когда все три утерянных числа относятся к одной команде и когда как минимум одно число относится к другой команде (или же утеряно меньше трёх чисел).

Обозначим количество матчей, сыгранных i-й командой, за P_i, количество побед — за W_i, количество ничьих — за D_i, количество поражений — за L_i и количество очков — за S_i.

Тогда верны следующие соотношения: W_i + D_i + L_i = P_i и 3W_i + D_i = S_i. В случае, если не все три утерянных числа относятся к одной команде, получаем, что надо решить несколько систем из двух линейных уравнений с не более чем двумя неизвестными.

В случае, если все три утерянных числа относятся к одной команде, третье уравнение получаем из того факта, что суммарное количество побед у всех команд равно суммарному количеству поражений, то есть W_i + W_- i = L_i + L_- i, где W_- i — суммарное количество побед у всех команд, кроме i-й, а L_- i — суммарное количество поражений у всех команд, кроме i-й.

Так что однозначное восстановление возможно всегда.

Основная проблема в данной задаче заключается в том, что таблица целиком в память не помещается.

Так что входной файл надо читать по строкам два раза: в первый раз — для того, чтобы построить соответствующую систему уравнений (при чтении суммируются W_i и L_i для составления системы во втором случае), во второй раз — чтобы найти содержащую ответ строку.

Задача F (Электротакси)

Данная задача была предложена польскими авторами и впервые была использована на первом этапе Всепольской школьной олимпиады по информатике сезона 2012-2013.

Очевидно, что или участок от таксопарка до точки назначения можно проехать без пересадок, или добраться до точки назначения невозможно (так как такси, которое доедет до точки назначения, обязано проехать участок от таксопарка до точки назначения полностью). Поэтому «зарезервируем» машину с минимальным запасом хода, которая может доехать от таксопарка до точки назначения, а также построим самую удалённую от точки назначения точку Z, из которой эта машина сможет забрать пассажира и доставить в точку назначения. Если таксопарк находится в точке назначения, то «резервирование» не производится.

Далее отсортируем «незарезервированные» машины по убыванию запаса хода и будем всякий раз выбирать машину с наибольшим запасом хода. Покажем, что этот алгоритм даёт как минимум не худшее решение по сравнению с каким-либо другим. Пусть сначала используется машина с запасом хода X₁, а затем — машина с запасом хода X₂, при этом пассажир изначально находится на расстояни a от таксопарка (и по другую сторону от точки назначения). Тогда пассажир проедет (X₁ - a) + (X₂ - (2a - X₁)) = 2X₁ + X₂ - 3a километров. Если X₂ > X₁, то, поменяв местами X₂ и X₁, увидим, что расстояние, которое проехал пассажир, увеличилось. Если машина с наибольшим запасом хода уже не может доехать (или «незарезервированные» машины закончились до того, как пассажир проехал точку Z), то добраться до точки назначения невозможно.

Если после очередного выбора пассажир оказался в точке Z или ближе к точке назначения, то он уже может доехать на отложенной машине. Также следует отдельно проверять случай, когда при выборе очередной машины пассажир сразу (без использования отложенной машины) может доехать до пункта назначения.

Всем привет!

Это первая запись в официальном блоге финала чемпионата мира по программированию ACM ICPC 2013. В этом году партнером организаторов финала чемпионата (НИУ ИТМО) выступила компания Яндекс. В Яндексе работают многие финалисты ICPC прошлых лет. Некоторые из них, включая меня, будут освещать это событие. Позвольте представить моего друга, Егора Куликова из Санкт-Петербургского офиса Яндекс. Он будет вести блог об ICPC. Я более чем уверен, что он превосходно осветит различные аспекты финала, и вот почему.

Oн был со мной в команде Московского государственного университета на чемпионате мира в Токио в 2007 году, где мы взяли бронзу — он не понаслышке знаком с чемпионатом. Мы пять лет готовились к этому чемпионату. В МГУ всегда неслабый конкурс, так что в нашем случае надо было одержать победу в NEERC 2006 года для того, чтобы обогнать главных университетских соперников. Они к тому моменту уже участвовали в финале чемпионата мира и были общепризнанными фаворитами. Для нас финал стал почти что целью жизни — и мы в него прошли.

Будучи школьниками мы оба участвовали в олимпиадах по математике. Неоднократно становились призерами Всероссийской олимпиады по математики, были кандидатами в национальную сборную на Международную математическую олимпиаду (IMO), но не попали в шестерку лучших в России. Тем не менее, это поражение было одним из наших главных стимулов выйти в финал. Так как организованной системы студенческих олимпиад по математике не существовало, мы увлеклись программированием. Участие в олимпиадах, сборах, лекции и тренировки оказались основой нашего образования в области Computer Science.

Последним по списку, но не по значению является тот факт,что Егор дважды стал чемпионом мира, победив на Google Code Jam в 2010 году и на TopCoder Open в 2012 году. В мире только еще один человек достиг таких же результатов, и вы его знаете – это Петр Митричев, наш однокурсник из МГУ :) Они оба — мои друзья, так что, если вы хотите узнать о них больше, можете почитать мои ответы в Quora про Егора и Петра.

Ждите наших отчетов о чемпионате мира ACM ICPC за 2013 год!

Поздравляем победителей турнира трех четвертьфиналов:

1. SPb NRU ITMO 1
2. Petr
3. SPb SU 4
4. msu-st
5. SJTU Mithril

Спасибо Олегу Христенко (snarknews) за идею турнира и за его проведение! Спасибо жюри четвертьфиналов за интересные задачи и за то, что поделились ими! Спасибо команде Яндекс.Contest за оперативное допиливание системы!

И главное — спасибо всем участникам! Спасибо за ваш feedback. Надеемся, что для многих это была полезная, интересная тренировка и fun. Удачи всем на ваших полуфиналах и на финале в Санкт-Петербурге!

Кажется, многие участники могли не заметить важное обновление поста про турнир трех четвертьфиналов, поэтому продублирую его отдельным постом:

Опубликован объединенный монитор двух прошедших туров по системе Гран При 30. В случае равенства очков по системе Гран При 30 мы дополнительно ранжируем команды по суммарному рейтингу по системе ИТМО, как на Открытом Кубке. Приносим свои извинения, что система разрешения ничьих не была опубликована изначально. Обращаем внимание команд, что склейка результатов производится по отображаемому имени. Команды, у которых не склеились результаты, отписывайтесь в комментариях. В третьем раунде проставьте себе ровно такое же отображаемое имя, как имя в объединенном мониторе. Мы даже собираемся с началом третьего раунда (точнее, как только хотя бы одна команда совершит посылку) в объединенный монитор добавить и третий раунд и надеемся, что объединенный монитор после этого будет показывать текущую ситуацию в каждый момент времени с учетом положения команд в третьем раунде турнира. Ясно, что для команд, участвующих в официальном четвертьфинале в Санкт-Петербурге, изменятся отображаемые имена, и потребуется некоторое время на их склейку.

Также сообщаем, что появилась возможность до начала контеста отменить регистрацию (если зарегистрировали не ту команду) или поменять состав команды — на вкладке "Регистрация". После начала контеста этого сделать будет уже нельзя.

Всем привет!

Проект Яндекс.Contest вышел на тот уровень, когда мы можем проводить публичные контесты достаточно большого объема, а также вся Школа анализа данных Яндекса в Москве, Санкт-Петербурге, Минске, Екатеринбурге и Харькове сдает курс "Алгоритмы и структуры данных" на этой системе. Теперь проект нужно развивать дальше, и мы хотим делать это еще быстрее, поэтому ищем Java-разработчика и разработчика интерфейсов. Обращаюсь к сообществу на Codeforces, т.к. надеюсь, что многие участники ACM-сообщества могут быть заинтересованы в участии в таком проекте. Проект Яндекс.Contest с самого начала делали с участием нескольких ACMщиков и по заказу от бывших ACMщиков, так что есть все шансы почувствовать себя в "своей" среде :)

UPD. Как всегда, рассматриваются иногородние кандидаты (не из Москвы) с возможностью переезда.

Приглашаем вас поучаствовать в турнире трех четвертьфиналов — командном онлайн-соревновании, которое будет проводиться параллельно с четвертьфиналами ACM в Москве, Минске и Санкт-Петербурге в конце октября. Турнир будет организован совместными усилиями команды Яндекс.Contest, Олега Христенко (snarknews) и жюри перечисленных четвертьфиналов ACM ICPC. Даты и времена проведения: Московский ЧФ (регистрация) — 21 октября, 14:00 по Москве, Минский ЧФ (регистрация) — 28 октября, 11:00 по Москве, ЧФ в Санкт-Петербурге (регистрация) — 3 ноября в 12:00 по Москве.

Команды, участвующие в официальной версии одного из четвертьфиналов, могут поучаствовать в онлайн-версиях остальных четвертьфиналов. Команды, не участвующие ни в одном из официальных четвертьфиналов, могут принять участие онлайн во всех трех раундах. Результаты каждой команды на всех соревнованиях, официальных и неофициальных, будут учтены, итоговый зачет турнира будет производиться по системе Гран При 30.

Регистрация на онлайн-версию каждого четвертьфинала идет непрерывно вплоть до старта соревнования. Создать команду в системе Яндекс.Contest вы можете по ссылке «Мои команды». Все приглашенные в команду участники должны подтвердить своё участие в соревновании. После успешного создания команды необходимо зарегистрироваться на соревнование, указав вашу команду.

Правила отдельных раундов совпадают с правилами официальных четвертьфиналов.

Потренироваться сдавать задачи в системе Яндекс.Contest можно, приняв участие в A + B virtual.

На ваши вопросы и комментарии к этому посту могут отвечать несколько человек, кроме меня: Владимир Тен (vtenity), Лев Толмачев (lev.tolmachev), Виталик Гольдштейн (goldvitaly), Олег Христенко (snarknews).

Следите за обновлениями!

UPD. Онлайн раунд московского четвертьфинала стартует 21 октября в 14:00 по Москве, чтобы все могли поучаствовать в Codeforces Round 146 и CodeChef cook-off.

UPD.2 Появились ссылки для регистрации на все три ЧФ и точные времена их проведения:

1. Московский ЧФ — 21 октября, 14:00 по Москве.
2. Минский ЧФ — 28 октября, 11:00 по Москве.
3. ЧФ в Санкт-Петербурге — 3 ноября в 12:00 по Москве.

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

UPD.4 Опубликован объединенный монитор двух прошедших туров по системе Гран При 30. В случае равенства очков по системе Гран При 30 мы дополнительно ранжируем команды по суммарному рейтингу по системе ИТМО, как на Открытом Кубке. Приносим свои извинения, что система разрешения ничьих не была опубликована изначально. Обращаем внимание команд, что склейка результатов производится по отображаемому имени. Команды, у которых не склеились результаты, отписывайтесь в комментариях. В третьем раунде проставьте себе ровно такое же отображаемое имя, как имя в объединенном мониторе. Мы даже собираемся с началом третьего раунда (точнее, как только хотя бы одна команда совершит посылку) в объединенный монитор добавить и третий раунд и надеемся, что объединенный монитор после этого будет показывать текущую ситуацию в каждый момент времени с учетом положения команд в третьем раунде турнира. Ясно, что для команд, участвующих в официальном четвертьфинале в Санкт-Петербурге, изменятся отображаемые имена, и потребуется некоторое время на их склейку.

Мы рады пригласить вас поучаствовать в первом тестовом раунде Яндекс.Contest. Соревнование пройдет в пятницу 17 августа 2012 года с 20:00 до 22:30 по московскому времени. Для решения задач разрешено использовать такие языки программирования как C++, Java, FreePascal, Delphi, Python 2 и 3.

Правила тестового раунда — экспериментальные и во многом отличаются от правил, привычных для подобных соревнований (ACM ICPC, TopCoder, Codeforces, IPSC). Просим вас внимательно с ними ознакомиться.

Для ознакомления с системой Яндекс . Contest вы можете поучаствовать в виртуальном пробном соревновании A+B virtual.

Ваши отзывы, пожелания по системе и багрепорты нам очень нужны — вы можете оставить комментарий к этому посту или воспользоваться формой обратной связи. На ваши вопросы по раунду здесь могут отвечать несколько человек, кроме меня, в их числе Владимир Тен (vtenity) и Лев Толмачев (lev.tolmachev).

Поздравляем Петю Митричева (Petr), ставшего чемпионом Яндекс.Алгоритм 2011!

Также поздравляем Диму Джулгакова (dzhulgakov), Makoto Soejima (rng_58), Ивана Метельского (ivan.metelsky), Алексея Левина (levlam) и Гену Короткевича (tourist), занявших, соответственно, 2, 3, 4, 5 и 6 места и решивших столько же задач, сколько и победитель! Полные результаты раунда можно посмотреть здесь

Задачи оказались не на шутку сложными: никто из финалистов не смог решить более 3 задач за отведенные 2 часа. А задача A, про которую авторы считали, что она намного проще всех остальных, поддалась менее чем половине наших финалистов, и даже чемпиону не хватило 30 секунд, чтобы исправить свое решение. Задачу E смог за весь контест сдать только кореец Xhark. 

Придумал задачу E Илья Корнаков (ilyakor), по совместительству разработчик в моей группе в Яндексе :) Задача A про домино и некоего Гену - powered by Ваня Попелышев (ivan.popelyshev). Задача B — Стас Пак, C — Денис Ярец. Все трое — также наши сотрудники. С задачей D нам помог Артем Рипатти. Мою задачу в последний момент решили не брать, и она будет ждать вас в Петрозаводске, готовьтесь :)

Спасибо всем финалистам, авторам задач, участникам вне зачета, организаторам контеста, МФТИ за предоставленную площадку и, конечно, главному спонсору мероприятия — компании Яндекс!

Удачи всем, кто сегодня пишет онсайт OpenCup!

Петю окружили :)

ivan.metelsky, MikeMirzayanov и pieguy

Всем привет!

Участники финала Яндекс.Алгоритм постепенно собирались в Долгопрудном... Каждый делал это по-своему :)

dzhulgakov, pieguy, levlam и Progger оказались самыми организованными и приехали к самому началу Летней Школы, успели подружиться с остальными участниками и начали соревноваться в практической задаче по биоинформатике с использованием кластера Hadoop — молодцы! Двое дружных японцев rng_58 и wata приземлились в Шереметьево 13 июля в 17.55 и уже через час получали свои беджики. Их земляк LayCurse перепутал дату и взял билеты ровно на тот же рейс, только 14 июля :) tourist с папой приехали с утра 14 июля, а dolphinigle прилетел вчера поздним вечером и сказал мне, что я первый человек в России, которого он встретил, кто говорит по-английски :) ivan.metelsky "ворвался" сегодня в комнату организаторов, отсыпавшихся от вчерашней тусовки, в 8 утра; добрался сам, без всяких указаний :) e-maxx подъехал в Москву в 10.38 утра и направился прямиком на соревнование вместе с другими нашими саратовскими друзьями — не без приключений: ведь электрички до Долгопрудного идут с перерывом в расписании с 11.10 до 13.40. ktuan в последний момент решил, что последние универские каникулы он лучше не будет тратить на поездку к нам на финал, а Burunduk1, судя по всему, заработался, обучая школьников, и не отвечает на письма и телефонные звонки (ай-яй-яй, Сережа) — интересно, приедет ли он в последний момент? Petr подрулит к нам на машине из Москвы чуть перед обедом, а мой стажер zeliboba учится в МФТИ и постоянно проживает в том же здании, что и все участники летней школы — наверно придет последним :)

Участвовать в раунде, как всегда, могут все зарегистрировавшиеся. Все, кто не участвует в онсайт-туре, будут писать вне конкурса. При этом соревнование рейтинговое для всех участников Div-1.

Напоминаем, что время контеста сегодня необычное: начало в 16.00 Задачи сегодня непростые, посложнее обычных Div-1 — ждем захватывающей схватки!

Update: Полные результаты

Мы рады сообщить, что 4 мая начнётся открытый турнир Яндекса по программированию "Яндекс.Алгоритм". В этом году он будет проходить на платформе и по правилам Codeforces. Участников ждут два квалификационных, два отборочных онлайн-раунда и финальный онсайт-раунд, который состоится во время Летней школы Яндекса по распределенным вычислениям в МФТИ. Некоторые раунды целиком подготовлены сотрудниками Яндекса.

Соревнование международное, участвовать могут все зарегистрированные на Codeforces. Всего будет 5 раундов. Продолжительность каждого раунда — 2 часа. В финал пройдут 15 победителей отборочных раундов, они будут приглашены на Летнюю школу. 70 лучших участников получат сувениры с символикой соревнования.