Просмотр кода страницы Состоялся Demidov Open IT Cup 2022

{{Публиковать}}
{{дата|28 мая 2022}}
[[21 мая 2022 года|21 мая]] в [[Ярославский государственный университет|Ярославском Государственном университете им. П. Г. Демидова]] прошло соревнование по спортивному программированию [[Demidov Open IT Cup 2022]]. Победу одержала команда из НИТУ «МИСиС», оформив «тотал»<ref>Решили все 11 задач.</ref> за 2 часа до конца контеста.

<gallery mode="packed" heights="400" style="margin:auto">
Demidov Open IT Cup 2022 (2022-05-21) 02.jpg|Каждый шарик - решённая задача до «заморозки»<ref>За час до конца соревноваия таблица результатов замораживается и неизвестны чужие успешные посылки. Свои видны.</ref>.
</gallery>

Соревнование проходило по правилам [[Международная студенческая олимпиада по программированию|ICPC]]: 5 часов, 11 задач, команды из 3 людей за одним компьютером<ref>При этом команды могут состоять из меньшего числа участников. Например, MAI #41827 участвовал на соревнование в составе двух человек.</ref>. Каждая идея имеет под собой легенду и ограничения по памяти и времени. Как правило, они вынуждают придумывать более эффективный алгоритм, не допускающий решение в лоб. Однако в некоторых может встретиться простая реализация.

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

Полный список призёров:
{|
|
# Диплом 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).
|}

<gallery mode="packed" heights="400" style="margin:auto">
Demidov Open IT Cup 2022 (2022-05-21) 01.jpg|Соревнование проходило в актовом зале.
</gallery>

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

В задаче A рассказывается n историй, для каждой предлагается k различных напитков, каждый имел крепкость <math>b_i</math>, причём для каждой истории есть ограничение на принимаемый напиток: <math>l \leq b_{i+1} - b_{i} \geq r</math>. В этой задаче нужно составить путевую матрицу <math>k\times k</math>, то есть можно ли от одного напитка перейти к другому или нет. И возвести эту матрицу в степень числа историй<ref>Это нужно делать через [https://e-maxx.ru/algo/binary_pow бинарное возведение матрицы в степень] {{Wayback|url=https://e-maxx.ru/algo/binary_pow |date=20220702174354 }}.</ref>.

В задаче B нужно было пройтись по графу, из заданной вершины в данную вершину<ref>Это [https://e-maxx.ru/algo/dijkstra классическая задача на] {{Wayback|url=https://e-maxx.ru/algo/dijkstra |date=20220618170745 }} [[алгоритм Дейкстры]].</ref>.

Задача C на «реализацию»<ref>Задачи, где нужно просто написать код, того что просят в условии.</ref>: узнать сколько в данном году было пятниц тринадцатого. С этой задачей справились почти все участники турнира.

В задаче D надо было написать «рюкзак», с условием, что можно класть предмет нулевой массы<ref>[[Задача о рюкзаке]] это [https://neerc.ifmo.ru/wiki/index.php?title=Задача_о_рюкзаке типичная задача об оптимизации]. Есть ограничение по массе «сколько можно положить в рюкзак» и каждый предмет имеет «стоимость» и свой «вес» хотим унести как можно больше ценных предметов.</ref>.

В E нужно было отвечать на n запросов: «сколько простых чисел между двумя включительно»<ref>В этой задаче [https://e-maxx.ru/algo/eratosthenes_sieve нужно сначала составить] {{Wayback|url=https://e-maxx.ru/algo/eratosthenes_sieve |date=20220502232729 }} [[решето Эратосфена]] до максимального числа, а потом с помощью него записать для каждого числа префиксный массив, запоминая сколько простых чисел было до него. После этого можно отвечать на каждый запрос, просто обращаюсь к массиву за константное время.</ref>.

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

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

В задаче H был задан граф списком рёбер и стартовая вершина. Суть вопроса задачи в существовании цикла в этом графе<ref>[https://e-maxx.ru/algo/finding_cycle Существование цикла в графе] {{Wayback|url=https://e-maxx.ru/algo/finding_cycle |date=20220702180023 }} можно легко установить через [[Поиск в глубину|DFS]].</ref>.

Задача I была интерактивная<ref>Вид задач в котором пользователь в программе задаёт запросы и на основе их ищет ответ.</ref>, в ней нужно найти k самых тяжёлых арбузов. На каждом запросе разрешается либо сравнить два арбуза, либо вывести ответ<ref>Авторское решение было реализовать сравнение арбузов через турнирную сортировку.</ref>.

В задаче J спрашивалась длина минимального маршрута по сетке <math>N\times M</math> улиц, если нужно проехаться по каждой и вернуться в исходную точку<ref>Задача [https://acmp.ru/index.asp?main=task&id_task=162 с точно таким же условием есть] на ACMP.</ref><ref>В задаче нужно было найти [[Гамильтонов граф|гамильтоновский цикл]] и добавить к ответу вершины с нечётными степенями, поделёнными на 2. Также её можно было решить, перебрав случаи с разной чётностью длин прямоугольника и подобрать формулу</ref>.

В последней задаче K нужно было отсортировать N строчек с K параметров по сумме их попарных произведенией<ref>Сумму попарных произведений k чисел можно найти посчитав произведение каждого на сумму ряда без него и поделить попалам. Это легко заметить если выписать все попарные произведения и сгруппировать их.</ref>.

{{-}}

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://youtu.be/7T8gDM9DvV8?t=29199 Трансляция церемонии награждения и разбора задач].

== Источники ==
{{Оригинальный репортаж 3}}

{{Подвал новости}}

{{Категории|Demidov Open IT Cup|Demidov Open IT Cup 2022|Алгоритм Дейкстры|Архангельск|Гамильтонов граф|Задача о рюкзаке|Иваново|Ковров|Международная студенческая олимпиада по программированию|Москва|Олимпиады по программированию|Петрозаводск|Поиск в глубину|Программирование|Решето Эратосфена|Рыбинск|Санкт-Петербург|Соревнования|Спортивное программирование|Тула|Ярославль|Ярославский государственный университет}}