Состоялся 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]