Состоялся Demidov Open IT Cup 2022

28 мая 2022 года
21 мая в Ярославском Государственном университете им. П. Г. Демидова прошло соревнование по спортивному программированию Demidov Open IT Cup 2022. Победу одержала команда из НИТУ «МИСиС», оформив «тотал»^[1] за 2 часа до конца контеста.

Каждый шарик - решённая задача до «заморозки»^[2].

Соревнование проходило по правилам ICPC: 5 часов, 11 задач, команды из 3 людей за одним компьютером^[3]. Каждая идея имеет под собой легенду и ограничения по памяти и времени. Как правило, они вынуждают придумывать более эффективный алгоритм, не допускающий решение в лоб. Однако в некоторых может встретиться простая реализация.

В нём поучаствовали команды из Архангельска, Иваново, Коврова, Москвы, Петрозаводска, Рыбинска, Санкт-Петербурга, Тулы и Ярославля.

Полный список призёров:

Диплом 1-й степени (11 задач) NUST MISIS: All Cats Are Beautiful (Akmanov, Kolodin, Piskevich).
Диплом 1-й степени (10 задач) NUST MISIS: Flip phone, telefon (Bikmetov, Levshin, Fedorov).
Диплом 2-й степени (9 задач) NArFU (Asjutchenko, Grishin, Lodygin).
Диплом 2-й степени (9 задач) YaroslavISU: posledniy zaezd (Voronin, Medvedev, Chirkov).
Диплом 2-й степени (9 задач) SPb ETU: Dzhavissimo (Ignat’ev, Mironchik, Skiba).
Диплом 2-й степени (9 задач) TulSU: tulula (Ivlev, Perezjabov, Savin).
Диплом 2-й степени (9 задач): PetrSU: Chars (Rejkenen, Rojtburd, Husnutdinova)
Диплом 3-й степени (8 задач): PetrSU: Bykva Yu (Al’shanin, Ermakov, Potapova)
Диплом 3-й степени (8 задач): PetrSU: NaN (Anisimov, Lavrov, Sobjanina)
Диплом 3-й степени (8 задач): RSATU #4 (Krylov, Rastorguev, Rastorgueva)
Диплом 3-й степени (7 задач): YaroslavISU: LigaDravena (Genneke, Krasnoschekov, Sokolov).
Диплом 3-й степени с 7 решёнными задачами: MAI #41827 (Barsov, Krasotkin, Chuvilin).

Соревнование проходило в актовом зале.

Задачи и основная идея

Всего было 11 задач. Приведём для читателей Викиновостей суть задач и главные идеи решения, не излагая легенду условия.

В задаче A рассказывается n историй, для каждой предлагается k различных напитков, каждый имел крепкость $b_{i}$ , причём для каждой истории есть ограничение на принимаемый напиток: $l\leq b_{i+1}-b_{i}\geq r$ . В этой задаче нужно составить путевую матрицу $k\times k$ , то есть можно ли от одного напитка перейти к другому или нет. И возвести эту матрицу в степень числа историй^[4].

В задаче B нужно было пройтись по графу, из заданной вершины в данную вершину^[5].

Задача C на «реализацию»^[6]: узнать сколько в данном году было пятниц тринадцатого. С этой задачей справились почти все участники турнира.

В задаче D надо было написать «рюкзак», с условием, что можно класть предмет нулевой массы^[7].

В E нужно было отвечать на n запросов: «сколько простых чисел между двумя включительно»^[8].

Ещё одна задача на «реализацию» F, в ней по записям в блокноте нужно было определить будет ли Луна расти на следующий день, если известны замеры по прошлым дням от 0 до 15. Причём каждый день Луна либо растёт либо убывает.

Задача G представляла собой описание настольный игры. Даны ингридиенты и их компоненты и что происходит при их смешивании. Есть m записей о резульататах смешивания, нужно установить из каких компонентов состоят ингридиенты, если это возможно^[9]. С этой задачей справились мало участников из-за объёмного решения и неочевидных условий перебора.

В задаче H был задан граф списком рёбер и стартовая вершина. Суть вопроса задачи в существовании цикла в этом графе^[10].

Задача I была интерактивная^[11], в ней нужно найти k самых тяжёлых арбузов. На каждом запросе разрешается либо сравнить два арбуза, либо вывести ответ^[12].

В задаче J спрашивалась длина минимального маршрута по сетке $N\times M$ улиц, если нужно проехаться по каждой и вернуться в исходную точку^[13]^[14].

В последней задаче K нужно было отсортировать N строчек с K параметров по сумме их попарных произведенией^[15].

Примечания

↑ Решили все 11 задач.
↑ За час до конца соревноваия таблица результатов замораживается и неизвестны чужие успешные посылки. Свои видны.
↑ При этом команды могут состоять из меньшего числа участников. Например, MAI #41827 участвовал на соревнование в составе двух человек.
↑ Это нужно делать через бинарное возведение матрицы в степень (Архивная копия от 2 июля 2022 на Wayback Machine).
↑ Это классическая задача на (Архивная копия от 18 июня 2022 на Wayback Machine) алгоритм Дейкстры.
↑ Задачи, где нужно просто написать код, того что просят в условии.
↑ Задача о рюкзаке это типичная задача об оптимизации. Есть ограничение по массе «сколько можно положить в рюкзак» и каждый предмет имеет «стоимость» и свой «вес» хотим унести как можно больше ценных предметов.
↑ В этой задаче нужно сначала составить (Архивная копия от 2 мая 2022 на Wayback Machine) решето Эратосфена до максимального числа, а потом с помощью него записать для каждого числа префиксный массив, запоминая сколько простых чисел было до него. После этого можно отвечать на каждый запрос, просто обращаюсь к массиву за константное время.
↑ Авторское решение предполагало полный перебор.
↑ Существование цикла в графе (Архивная копия от 2 июля 2022 на Wayback Machine) можно легко установить через DFS.
↑ Вид задач в котором пользователь в программе задаёт запросы и на основе их ищет ответ.
↑ Авторское решение было реализовать сравнение арбузов через турнирную сортировку.
↑ Задача с точно таким же условием есть на ACMP.
↑ В задаче нужно было найти гамильтоновский цикл и добавить к ответу вершины с нечётными степенями, поделёнными на 2. Также её можно было решить, перебрав случаи с разной чётностью длин прямоугольника и подобрать формулу
↑ Сумму попарных произведений k чисел можно найти посчитав произведение каждого на сумму ряда без него и поделить попалам. Это легко заметить если выписать все попарные произведения и сгруппировать их.

Ссылки

Трансляция церемонии награждения и разбора задач.

Источники

Эта статья создана группой авторов специально для Русских Викиновостей и содержит ранее не публиковавшиеся материалы или исследования, источником которых являются сами авторы. Вы можете свободно без согласования и выплаты вознаграждения копировать, распространять и изменять эту статью в любых целях, включая коммерческие, однако вы обязаны указать автора, источник и лицензию. Например, так: Викиновости (авторы); CC BY 2.5. Вы также должны обозначить изменения, если таковые были сделаны. Лицензии изображений уточняйте на их страницах на Викискладе.

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

Несколько советов по оформлению реплик:

Новые темы начинайте, пожалуйста, снизу.
Используйте символ звёздочки «*» в начале строки для начала новой темы. Далее пишите свой текст.
Для ответа в начале строки укажите на одну звёздочку больше, чем в предыдущей реплике.
Пожалуйста, подписывайте все свои сообщения, используя четыре тильды (~~~~). При предварительном просмотре и сохранении они будут автоматически заменены на ваше имя и дату.

Обращаем ваше внимание, что комментарии не предназначены для размещения ссылок на внешние ресурсы не по теме статьи, которые могут быть удалены или скрыты любым участником. Тем не менее, на странице комментариев вы можете сообщить о статьях в СМИ, которые ссылаются на эту заметку, а также о её обсуждении на сторонних ресурсах.

Добавить комментарий

	Имеете своё мнение на этот счёт?
Оставьте свой комментарий

	Поделитесь новостью с друзьями
Телеграм Фейсбук Твиттер ВК ОК ЖЖ

[1] Решили все 11 задач.

[2] За час до конца соревноваия таблица результатов замораживается и неизвестны чужие успешные посылки. Свои видны.

[3] При этом команды могут состоять из меньшего числа участников. Например, MAI #41827 участвовал на соревнование в составе двух человек.

[4] Это нужно делать через бинарное возведение матрицы в степень (Архивная копия от 2 июля 2022 на Wayback Machine).

[5] Это классическая задача на (Архивная копия от 18 июня 2022 на Wayback Machine) алгоритм Дейкстры.

[6] Задачи, где нужно просто написать код, того что просят в условии.

[7] Задача о рюкзаке это типичная задача об оптимизации. Есть ограничение по массе «сколько можно положить в рюкзак» и каждый предмет имеет «стоимость» и свой «вес» хотим унести как можно больше ценных предметов.

[8] В этой задаче нужно сначала составить (Архивная копия от 2 мая 2022 на Wayback Machine) решето Эратосфена до максимального числа, а потом с помощью него записать для каждого числа префиксный массив, запоминая сколько простых чисел было до него. После этого можно отвечать на каждый запрос, просто обращаюсь к массиву за константное время.

[9] Авторское решение предполагало полный перебор.

[10] Существование цикла в графе (Архивная копия от 2 июля 2022 на Wayback Machine) можно легко установить через DFS.

[11] Вид задач в котором пользователь в программе задаёт запросы и на основе их ищет ответ.

[12] Авторское решение было реализовать сравнение арбузов через турнирную сортировку.

[13] Задача с точно таким же условием есть на ACMP.

[14] В задаче нужно было найти гамильтоновский цикл и добавить к ответу вершины с нечётными степенями, поделёнными на 2. Также её можно было решить, перебрав случаи с разной чётностью длин прямоугольника и подобрать формулу

[15] Сумму попарных произведений k чисел можно найти посчитав произведение каждого на сумму ряда без него и поделить попалам. Это легко заметить если выписать все попарные произведения и сгруппировать их.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]