С 1-го по 11-е августа прошла международная летняя студенческая школа по программированию — в живописном месте, на базе отдыха «Домостроитель» на берегу Волги. В ней приняло участие около 60 участников. В этом году школа проводилась Центром олимпиадной подготовки Саратовского государственного университета в 7-й раз. Руководитель — известный здесь Михаил Мирзаянов.
Мне посчастливилось побыть два дня на школе в качестве репортера.
Меня встречает Михаил MikeMirzayanov Мирзаянов.
— Сейчас идет тренировка, в два часа будет обед.
— Как проходит обычный день?
— Завтрак, лекция, контест с перерывом на обед, разбор, дорешивание. Вечером отдых — сегодня по плану ЧГК, завтра сауна с арбузами и забегами в Волгу.
На лекциях MikeMirzayanov прочитал следующие темы:
Паросочетания и смежные задачи. Теорема Бержа. Паросочетания в двудольных графах. Алгоритм Куна и его свойства.
Оптимизационные трюки для алгоритма Куна. Паросочетания в произвольных графах: рандомизированный алгоритм, матрица Татта и её приложения.
Деревья отрезков. Персистентные структуры данных. Персистентное дерево отрезков.
Декартово дерево. Структура данных Treap.
Декартово дерево по неявному ключу.
Потоки в графах. Теорема Форда-Фалкерсона. Алгоритмы Эдмондса-Карпа и масштабирования. Приложения потоков.
На каждую тему участники решали тематическую тренировку. Из десяти тренировок 4 были нетематическими, а 6 — на тему прошедшей лекции.