Зимняя Школа Looksery 2022

[Александр Сергеевич Антоненко]

Уважаемые участники факультатива!

Как Вы уже знаете, что и в этом году ОНУ им. И. И. Мечникова, ОНПУ и Ришельевский лицей при поддержке Snap Inc. (Looksery) организовывает Зимнюю Школу Looksery 2022 по олимпиадному программированию. Школа будет проведена в основном онлайн (некоторые занятия оффлайн с прямой онлайн трансляцией).

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

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

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

Также для студентов младших курсов ОНУ им. Мечникова (по крайней мере, студентов 1 курса специальностей ПМ и КИ) результаты будут учтены при выставлении оценок по программированию или курсов подобной направленности.

Планируется, базовыми днями школы будут понедельники, среды и субботы. Даты и время могут быть уточнены, в зависимости от удобства лекторов и участников школы - следите за обновлениями в этой теме, а также в группе telergam - https://t.me/AlgoSaturdayGroup. Ориентировочно школа будет продолжаться до середины февраля - но это зависит от количества лекторов и других факторов.

Первая лекция в базовом уровне будет в понедельник, 17 января в 17:00 через систему Zoom и её проводит доцент ОНУ им. И. И. Мечникова  Александр Сергеевич Антоненко , тема:  "Динамическое программирование" . 

Хотя это лекция базового уровня, но т.к. студенты-первокурсники ОНУ уже разбирали тему динамическое программирование, то если Вы это пропустили, не лишним будет послушать хотя бы первый час этой лекции: https://youtu.be/KvVQGEj-AOA - Антоненко, Петров, Максимов - Динамическое программирование 

Из лекторов подтвердили участие:
доценты ОНУ им. Мечникова и тренеры команд ОНУ А. С. Антоненко и И. Е. Мазурок
студенты ОНУ и участники команды ONU_PRIMATES, неоднократные финалисты чемпионата Украины (он же полуфинал мира SEERC) Руслан Масальский и Константин Григорян
 участник и тренер команды - финалиста чемпионата мира ONU 1 2/3 Олег Петров (Snap Inc.)
победитель всеукраинской олимпиады по программированию и финалист чемпионата мира ICPC Евгений Задорожний (команды ZNTU SetUp и UzhNU push –force) (Snap Inc.)
студент Иван Фекете (из KNU_COPYPASTE, одной из сильнейших команд КНУ им Шевченко)
студенты ОНПУ Алексей Кульбий (команда ONPU_BrainDead) и Валерия Фекете (команда ONPU_Rabotyagi)

Среди тем намечены:
Динамическое программирование (базовый уровень) / Динамическое программирование на деревьях (продвинутый уровень)
Дерево отрезков + Дерево Фенвика (базовый + продвинутый уровень)
Поиск в глубину, топологическая сортировка (базовый уровень)
Кратчайшие расстояния в графе (Дейкстра, Фл-Орш, Беллм-Форда, базовый уровень)
Остовное дерево, СНМ, Алгоритмы Прима и Крускала (базовый и продвинутый уровень)
Теория игр (базовый и продвинутый уровень)
Корневая оптимизация (продвинутый уровень)
и другие...

Если есть желание быть лекторами на базовом и продвинутом уровне - пишите мне на почту asantonenko [at] gmail [dot] com.

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

Для решения задач школы Вам понадобятся аккаунты e-olymp и codeforces .

Регистрация на школу доступна по ссылке: https://forms.gle/6iyMDDpWP3EJirt39

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

Регламент занятий: лекция 1 - 1,5 часа (в крайнем случае - 2 часа), тренировочное соревнование 3 - 4 часа сразу после лекции (точнее небольшого перерыва).

Если кто хочет себе представить себе как проходила раньше эта школа, можете заглянуть в ветку Зимней Школы 2018 - https://groups.google.com/d/topic/acm-onu-facult/xeMFV2-Z0pQ/discussion - в ней представлена вся информация о прошлогодней школе, так же, как в этой ветке будет вся информация о школе этого года и в ветку Зимней Школы 2019 https://groups.google.com/d/topic/acm-onu-facult/ogCqBcWN7Iw/discussion , а также ветку Зимней Школы 2020 https://groups.google.com/g/acm-onu-facult/c/gcPmYBpLWng/m/zYoUUr8zAAAJ и Зимней Школы 2021 https://groups.google.com/g/acm-onu-facult/c/PdxzRm576Tw/m/zRuxeZbBBwAJ 

С уважением,

Антоненко Александр

[Александр Сергеевич Антоненко]

Уважаемые участники Школы,

Сегодня в среду, 19.01.2022, в 17:00 состоится вторая онлайн лекция по теме Поиск в глубину, топологическая сортировка (лектор, Антоненко А.С., базовый уровень)

 Oleksandr Antonenko приглашает вас на запланированную конференцию: Zoom.

Тема: Поиск в глубину, топологическая сортировка - Oleksandr Antonenko
Время: 19 янв. 2022 05:00 PM Киев

Подключиться к конференции Zoom
https://us02web.zoom.us/j/83046408338?pwd=MkVQU2JIV1gySFFhVk40SGwwM3EzUT09

Идентификатор конференции: 830 4640 8338
Код доступа: 12345

Поздравляю Руслана Масальского и команду ONU_PRIMATES со всеми решенными задачами в контесте базового уровня "Динамическое программирование". Впрочем, они участвовали вне конкурса в туре базового уровня, а среди конкурсных команд базового уровня первое место заняла команда ONU_Секта приматов (Хромов Євгеній Олександрович, Мармалюк Олександр Валерійович, Кавалеров Володимир Володимирович, Лазаренко Дар'я Геннадіївна) с 5-ю решенными задачами.

Видео-запись лекции:  https://youtu.be/dcDuNI_keV4
Контест — https://www.eolymp.com/ru/contests/23771 Cлайды лекции — https://docs.google.com/presentation/d/1sBiUt_aE6xZGKQGz0SkAgXmBTs2lR4Wm/edit?usp=sharing&ouid=108608925754217069258&rtpof=true&sd=true

Также приведу мои заметки по задаче "Максимальный подпалиндром"

L-R динамика.
Максимальный подпалиндром

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

Пример ввода: МАТЕМАТИКА
Максимальная длина подпалиндрома: 5
Сам подпалиндром максимальной длины: например, АТАТА

Решение:
     L R
.....X......X.....

S - исходная строка длины N
M[L][R] - длина максимального подпалиндрома в строке S[L..R] - находится динамическим программированием...

изначально в матрице M нули

M[L][L] = 1

M[L][R] =
1) S[L] == S[R] => 2 + M[L+1][R-1]
2) S[L] != S[R] => max (M[L+1][R], M[L][R-1])

Реализация:

for (int L = 0; L < N; L++)
{
    M[L][L] = 1;
}
for (int len = 2; len <= N; len++)
{
    for (int L = 0, R = len - 1; R < N; L++, R++)
    {
       if (S[L] == S[R]) ...
    }
}

Длина максимального подпалиндрома будет в элементе M[0][N-1]

С уважением,

Антоненко Александр

воскресенье, 16 января 2022 г. в 21:26:53 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Уважаемые участники школы,

Результаты второго дня школы в целом совпали с результатами первого дня. Руслан Масальский лично и команда ONU_PRIMATES в целом решили все задачи в туре (вне конкурса). Среди конкурсных команд базового уровня первое место опять заняла команда ONU_Секта приматов (Хромов Євгеній Олександрович, Мармалюк Олександр Валерійович, Кавалеров Володимир Володимирович, Лазаренко Дар'я Геннадіївна) с 11-ю решенными задачами (отличный результат).
Хочу отметить также отличный результат ученицы Ришельевского лицея Анастасии Григорьянц - 10 задач.

Выложил видеозапись лекции Обход в в глубину, топологическая сортировка:
https://youtu.be/z65RZRVEbWs

Сегодня, в воскресенье, 23 января 2022, начиная с 13:00 состоится параллельно две лекции Зимней школы:
на базовом уровне:
Валерия Фекете (Григорянц) (НУОП, команда ONPU_Rabotyagi)
Bit manipulation (різні трюки з бітовими операціями)
на продвинутом уровне:
Іван Фекете (студент УжНУ, із команди UzhNU_OLDS, топ-15 на останньому півфіналі ICPC)
SQRT декомпозиція

Лекция продвинутого уровня будет проводиться в ауд. 38а - 1 этаж главного корпуса ОНУ им Мечникова, адрес: Дворянская, 2
Лекция базового уровня будет проходить неподалеку, скорее всего 39 ауд., какую удастся заполучить.

Собираемся в холле университета (без меня Вас возможно не пропустят, я буду примерно в 12:45)...

После лекций будут параллельно проходить два очных контеста в ауд. университета (но можно будет и домой пойти писать контест при желании).

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

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

Для участия в контесте Вам понадобится аккаунт codeforces.com

С ув.
Антоненко Александр

среда, 19 января 2022 г. в 13:26:50 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Большое спасибо Ивану и Валерии!

Контесты находятся в группе codeforces "Зимняя школа Looksery" по адресу https://codeforces.com/group/j3uuUV7Hld/contests
Bit manipulation (базовый уровень) воскресенье, 23.01.2022 в 15:00 (сейчас идет)

Корневые оптимизации (продвинутый уровень) понедельник, 24.01.2022 в 15:45

В помощь решающим задачи Bit manipulation (базовый уровень)

1. Программирование на языках C и C++ 3.5 Побитовые операции https://stepik.org/lesson/419562 (особенно шаги 3 и 4)
2. Побитовые операции — Викиконспекты Университета ИТМО https://neerc.ifmo.ru/wiki/index.php?title=Побитовые_операции 

В помощь решающим задачи Корневые оптимизации (продвинутый уровень)

1. Корневая оптимизация https://algorithmica.org/ru/sqrt

С ув.

Антоненко Александр

воскресенье, 23 января 2022 г. в 08:49:49 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Уважаемые участники школы,

Раз не поступило возражений, то завтра, в среду, 26 января 2022, начиная с 14:00 состоится очная лекция Зимней школы:
Руслан Масальский (из ONU_PRIMATES) с темой "Дерево отрезков" (базовый уровень).

Лекция будет на первом этаже главного корпуса ОНУ им Мечникова, либо в 47-й аудитории (где уже была лекция в воскресенье), либо рядом в 45-й аудитории.

После лекции можно будет написать контест в университете. Запись лекции будет выложена завтра же.

С уважением,
Антоненко Александр

воскресенье, 23 января 2022 г. в 17:20:02 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Уважаемые участники школы,
В расписании работы произошли некоторые изменения. Завтра, в субботу, в 11:30 вместо лекции по теории игр состоится разбор задач школы (онлайн), а лекция Алексея Кульбия по теории игр состоится в воскресенье, ориентировочно в 13:30.

Приглашение в зум конференцию осталось по сути тем же, только вывеска изменилась:

 Oleksandr Antonenko приглашает вас на запланированную конференцию: Zoom.

Тема: Разбор задач - Зимняя Школа 2022
Время: 29 янв. 2022 11:30 AM Киев

Подключиться к конференции Zoom
https://us02web.zoom.us/j/83011279400?pwd=dkFZQzRheTFlQUVZdWJLRkt1Sm9uQT09

Идентификатор конференции: 830 1127 9400
Код доступа: 12345
Очередная лекция школы состоится в воскресенье, 30 января 2022 года, онлайн через зум (см. приглашение ниже)... лектор: Алексей Кульбий, студент НУОП, команда ONPU_BrainDead, неоднократный участник нашей школы в прошлых годах, тема: Теория игр (базовый уровень), лекция начнется в 13:30.

В качестве подготовительных материалов можете посмотреть видео из плейлиста (естественно, это не обязательно, но для начинающих я бы сказал, что желательно, впрочем первое видео можно и пропустить - т.к. это совсем введение)
https://www.youtube.com/playlist?list=PLuKEIL5ZUv-XbGknXq6YlwcoC7j8BxK7b

Также наконец я составил Таблицу результатов Зимней Школы 2022 https://docs.google.com/spreadsheets/d/1LY38AHNgLWU1xbCmIU6doookrtjBlSI5BrmHszR4z_g/edit?usp=sharing
поясню обозначения:
у нас есть всего 4 команды достаточно опытных - ONU_PRIMATES, LNU_KPD, ONU_VKB, ONPU_Rabotyaga - они участвуют в конкурсе продвинутого уровня (обозначение П) и вне конкурса в базовом уровне (Б), есть пока 2 команды участвующие в конкурсе и продвинутого и базового уровня - ONU_Секта приматов и RL_UTFG - т.е. по опыту они проходят в базовый уровень, но уже решили хотя бы одну задачу продвинутого, остальные команды пока участвуют только в базовом уровне (но это не исключает, что кто-то из них решит задачу продвинутого уровня). Вообще, чтобы попасть в данную таблицу нужно решить хотя бы 1 задачу из нашей школы.

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

Немного по статистике, пока что у нас есть 6 команд в зачете продвинутого уровня и 21 команда в зачете базового уровня, всего 25 команд из них 15 команд ОНУ, 5 команд НУОП (ОНПУ), 3 команды Ришельевского лицея, 1 команда ЛНУ, и одна смешанная ОНУ + ОНПУ (по крайней мере так изначально зарегистрирована).
С уважением,

Антоненко Александр

вторник, 25 января 2022 г. в 21:08:07 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Следующее занятие пройдет первого февраля в 10:00 и продолжит тему теории игр.
Занятие проведет Олег Петров, один из создателей стартапа Looksery, тренер команды дважды успешно участвовавшей в финале чемпионата мира по программированию.
https://us02web.zoom.us/j/85315803768?pwd=bEFnbU1TTU9NSXlTS3llc25VaTh4Zz09
Идентификатор конференции: 853 1580 3768
Код доступа: 221410  

Контест по базовой теории игр — https://www.eolymp.com/uk/contests/23983

Выкладываю очередную часть видео-записей нашей Школы:

Зимняя школа 2022: Алексей Кульбий: Теория игр https://youtu.be/FJj2NxuSGEk

Зимняя школа 2022: Александр Антоненко: Разбор задач на динамическое программирование
https://youtu.be/sVpB9UsahSo

Зимняя школа 2022: Руслан Масальский: Краткий разбор задач на Дерево отрезков
https://youtu.be/0cpdS6abcRs

С уважением,

Антоненко Александр

пятница, 28 января 2022 г. в 23:44:43 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Уважаемые участники школы!

Очередная лекция школы состоится в субботу, 5 февраля 2022 года, очно в университете с онлайн трансляцией через зум (попробуем этот формат)... лектор: Константин Григорян, студент ОНУ, команда ONU_PRIMATES, неоднократный участник и победитель нашей школы в прошлых годах, тема: "Задачи на строках или как применять хеши", лекция начнется в 14:30 одновременно в ОНУ им Мечникова в ауд. 38а и через зум (если технически всё получится, на что очень надеюсь).

Oleksandr Antonenko приглашает вас на запланированную конференцию: Zoom.

Тема: Константин Григорян "Задачи на строках или как применять хеши" / Зимняя школа
Время: 5 февр. 2022 02:30 PM Киев

Подключиться к конференции Zoom
https://us02web.zoom.us/j/82510980207?pwd=dWhWRm9HMVNTR0lpQUdpaTh2ZHp5QT09

Идентификатор конференции: 825 1098 0207
Код доступа: 12345

С ув.
Антоненко Александр

понедельник, 31 января 2022 г. в 22:26:18 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Уважаемые участники Зимней Школы и сборов ко всеукраинской олимпиаде!

Сегодня, в среду, 16.02.2022 в 17:00 будет очередная лекция Зимней Школы базового уровня (онлайн, через зум). Она будет посвящена алгоритмам поиска кратчайшего маршрута в графах - Дейкстра, Беллмана-Форда, Флойда-Уоршалла.
Лектор: Антоненко А.С.

Еще раз отмечу - это будет относится и к сборам школьников и к Зимней Школе базового уровня. После лекции будет контест по регламенту Зимней Школы.

 Oleksandr Antonenko приглашает вас на запланированную конференцию: Zoom.

Тема: Зимняя Школа / Сборы - Кратчайшие расстояния в графе - Oleksandr Antonenko
Время: 16 февр. 2022 05:00 PM Киев

Подключиться к конференции Zoom
https://us02web.zoom.us/j/83075296194?pwd=SHRqVExyRkw2K21xc1hPZkdlT2dldz09

Идентификатор конференции: 830 7529 6194

Код доступа: 12345

С ув.
Антоненко Александр

суббота, 5 февраля 2022 г. в 07:40:43 UTC+2, Александр Сергеевич Антоненко:

[Александр Сергеевич Антоненко]

Выкладываю видео-записи:

Сборы к Всеукраинской олимпиаде 2022. Графы. Обход в глубину, ширину, топологическая сортировка https://youtu.be/cifRCGF1YBI

Сборы к Всеукраинской олимпиаде: Разбор задач на графы, обход в глубину и топологическую сортировку
https://youtu.be/Y1PlySh6IiI

Зимняя школа 2022: Александр Антоненко: Алгоритм Дейкстры и Беллмана-Форда. Алгоритм Флойда-Уоршелла
https://youtu.be/b1H9GETy7jw

среда, 16 февраля 2022 г. в 11:29:34 UTC+2, Александр Сергеевич Антоненко: