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

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

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

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

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

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

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

В задаче A рассказывается n историй, для каждой предлагается k различных напитков, каждый имел крепкость , причём для каждой истории есть ограничение на принимаемый напиток: . В этой задаче нужно составить путевую матрицу , то есть можно ли от одного напитка перейти к другому или нет. И возвести эту матрицу в степень числа историй[4].

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

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

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

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

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

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

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

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

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

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

ПримечанияПравить

  1. Решили все 11 задач.
  2. За час до конца соревноваия таблица результатов замораживается и неизвестны чужие успешные посылки. Свои видны.
  3. При этом команды могут состоять из меньшего числа участников. Например, MAI #41827 участвовал на соревнование в составе двух человек.
  4. Это нужно делать через бинарное возведение матрицы в степень.
  5. Это классическая задача на алгоритм Дейкстры.
  6. Задачи, где нужно просто написать код, того что просят в условии.
  7. Задача о рюкзаке это типичная задача об оптимизации. Есть ограничение по массе «сколько можно положить в рюкзак» и каждый предмет имеет «стоимость» и свой «вес» хотим унести как можно больше ценных предметов.
  8. В этой задаче нужно сначала составить решето Эратосфена до максимального числа, а потом с помощью него записать для каждого числа префиксный массив, запоминая сколько простых чисел было до него. После этого можно отвечать на каждый запрос, просто обращаюсь к массиву за константное время.
  9. Авторское решение предполагало полный перебор.
  10. Существование цикла в графе можно легко установить через DFS.
  11. Вид задач в котором пользователь в программе задаёт запросы и на основе их ищет ответ.
  12. Авторское решение было реализовать сравнение арбузов через турнирную сортировку.
  13. Задача с точно таким же условием есть на ACMP.
  14. В задаче нужно было найти гамильтоновский цикл и добавить к ответу вершины с нечётными степенями, поделёнными на 2. Также её можно было решить, перебрав случаи с разной чётностью длин прямоугольника и подобрать формулу
  15. Сумму попарных произведений k чисел можно найти посчитав произведение каждого на сумму ряда без него и поделить попалам. Это легко заметить если выписать все попарные произведения и сгруппировать их.

СсылкиПравить

ИсточникиПравить

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

Комментарии

Викиновости и Wikimedia Foundation не несут ответственности за любые материалы и точки зрения, находящиеся на странице и в разделе комментариев.