gKseni's blog

By gKseni, 8 years ago, In Russian

С 1-го по 11-е августа прошла международная летняя студенческая школа по программированию — в живописном месте, на базе отдыха «Домостроитель» на берегу Волги. В ней приняло участие около 60 участников. В этом году школа проводилась Центром олимпиадной подготовки Саратовского государственного университета в 7-й раз. Руководитель — известный здесь Михаил Мирзаянов.

Мне посчастливилось побыть два дня на школе в качестве репортера.

Меня встречает Михаил MikeMirzayanov Мирзаянов.

— Сейчас идет тренировка, в два часа будет обед.
— Как проходит обычный день?
— Завтрак, лекция, контест с перерывом на обед, разбор, дорешивание. Вечером отдых — сегодня по плану ЧГК, завтра сауна с арбузами и забегами в Волгу.

На лекциях MikeMirzayanov прочитал следующие темы:

  1. Паросочетания и смежные задачи. Теорема Бержа. Паросочетания в двудольных графах. Алгоритм Куна и его свойства.

  2. Оптимизационные трюки для алгоритма Куна. Паросочетания в произвольных графах: рандомизированный алгоритм, матрица Татта и её приложения.

  3. Деревья отрезков. Персистентные структуры данных. Персистентное дерево отрезков.

  4. Декартово дерево. Структура данных Treap.

  5. Декартово дерево по неявному ключу.

  6. Потоки в графах. Теорема Форда-Фалкерсона. Алгоритмы Эдмондса-Карпа и масштабирования. Приложения потоков.

На каждую тему участники решали тематическую тренировку. Из десяти тренировок 4 были нетематическими, а 6 — на тему прошедшей лекции.



Участники сборов на лекции

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



Михаил MikeMirzayanov Мирзаянов объясняет псу декартово дерево. Пес сопротивляется.

Команды пишут контест в холле, в комнатах, в беседках на улице. Лица сосредоточенны или растеряны, когда видят фотоаппарат, смеются — надо лицо по-умнее сделать!



Мозговой штурм

Контест проходит с получасовым перерывом на обед. В столовой каждый сидит на определенном месте — где привык.



Приятного аппетита!

Нахожу свободное место, за столом приветливо улыбаются Артём temich Носов и Никита ShadowGorn Пенской из Волгоградского ГТУ, Владимир Waldis Петров из Южно-Уральского ГУ, Владислав vlad8 Мац и Андрей AStepanov Степанов из Харьковского Политехнического Института. За едой участники обсуждают задачи — рассказывают свои догадки по способу решения задач, смеются над багами

После окончания контеста прошел турнир ЧГК. Участники собрали команды, придумали остороумные названия — «Астральные кабачки», «Дровосеки», «Нет». После озвучивания вопроса, давалась минута на обсуждение, свой вариант ответа команды писали на бумажке и должны были до окончания времени положить ее на стол в центре зала. Вопросы оказались интересными, разнообразными по сложности, варианты ответа часто вызывали улыбку у команд.



Главное успеть!

По результатам двух туров победу одержала команда «Чеганрог». Второе место взяла команда «Слово пастырям», а третье разделили команды «Друзь и я» и «Да».



Команда «Чеганрог»


gKseni и турнирная таблица

Александр 19Archangel95 Рыбалко и Алексей pyloolex Слуцкий из Саратовского ГУ делятся впечатлениями:

— Как вам сборы?
— Это круто, здесь успеваешь заниматься и отдыхать. После десятого числа поедем на сборы в «Березку», а 23 снова вернемся сюда. Но будет уже не так познавательно, думаю.
— На лекциях много нового узнали?
— Кстати да, все новое узнали и задачи раньше подобные не решали.



Александр 19Archangel95 Рыбалко и Алексей pyloolex Слуцкий

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

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

В другие дни ребята отдыхали в сауне — грелись, играли в парилке в игру «крокодил» — жестами объясняли слова — в условиях высокой температуры это оказалось нелегко, кушали арбузы и мороженное — и бежали дорешивать задачи. Обсуждение пройденного материала и задач не останавливается ни на минуту. И, конечно, гитара — спасибо, Настя crazysun Ярунина!



С легким паром!

Среди деревьев висят гирлянды — а в беседках — компания с гитарой — меняют струны, настраивают, играют по очереди Анастасия crazysun Ярунина и Дмитрий Кленов — ветеран саратовского олимпиадного движения. Он признается:

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

У воды любуется ночной Волгой участник из Питера Александр lll Лысов из СПбГУ.

— Совсем как Нева, — говорит он.

Ближе к часу ночи Михаил MikeMirzayanov Мирзаянов проходит по территории и призывает участников сборов отправляться ко сну.

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

Вставать к завтраку в 8:20 оказалось действительно тяжеловато — я смогла подойти только через 15 минут, однако была не последняя — постепенно подтягивались участники сборов — одни бодры и свежи, по другим сразу видно, что ранним подъем дался им не легко … как и мне.

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

Лекция закончилась — несколько парней с разбегу забегают в Волгу.

— Ааа, нормальная! Третий раз на Волгу выбрались. — кричат они.

Но в воде пробыли недолго — сразу после лекции начинается пятичасовой контест.

В сторону корпуса направляется Михаил Мирзаянов.
— Как прошла лекция?
— Сложно, материал объемный, часа три читал. Посмотрю как справляются ребята — нужно убедиться, что они все поняли.

Я с неохотой уезжаю со школы. Вечером ребят ждет закрытие и шашлычная вечеринка. Говорят, 22 килограмма мяса уже замаринованы.

Результаты контестов (команды со звездочками — дорешивание):

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

Фото со сборов:

  • Vote: I like it
  • +126
  • Vote: I do not like it