Состоялся Demidov Open IT Cup 2022
Соревнование проходило по правилам ICPC: 5 часов, 11 задач, команды из 3 людей за одним компьютером. Каждая идея имеет под собой легенду и ограничения по памяти и времени. Как правило, они вынуждают придумывать более эффективный алгоритм, не допускающий решение в лоб. Однако в некоторых может встретиться простая реализация.
В нём поучаствовали команды из Архангельска, Иваново, Коврова, Москвы, Петрозаводска, Рыбинска, Санкт-Петербурга, Тулы и Ярославля.
Полный список призёров:
Всего было 11 задач. Приведём для читателей Викиновостей суть задач и главные идеи решения, не излагая легенду условия.
В задаче A рассказывается n историй, для каждой предлагается k различных напитков, каждый имел крепкость , причём для каждой истории есть ограничение на принимаемый напиток: . В этой задаче нужно составить путевую матрицу , то есть можно ли от одного напитка перейти к другому или нет. И возвести эту матрицу в степень числа историй.
В задаче B нужно было пройтись по графу, из заданной вершины в данную вершину.
Задача C на «реализацию»: узнать сколько в данном году было пятниц тринадцатого. С этой задачей справились почти все участники турнира.
В задаче D надо было написать «рюкзак», с условием, что можно класть предмет нулевой массы.
В E нужно было отвечать на n запросов: «сколько простых чисел между двумя включительно».
Ещё одна задача на «реализацию» F, в ней по записям в блокноте нужно было определить будет ли Луна расти на следующий день, если известны замеры по прошлым дням от 0 до 15. Причём каждый день Луна либо растёт либо убывает.
Задача G представляла собой описание настольный игры. Даны ингридиенты и их компоненты и что происходит при их смешивании. Есть m записей о резульататах смешивания, нужно установить из каких компонентов состоят ингридиенты, если это возможно. С этой задачей справились мало участников из-за объёмного решения и неочевидных условий перебора.
В задаче H был задан граф списком рёбер и стартовая вершина. Суть вопроса задачи в существовании цикла в этом графе.
Задача I была интерактивная, в ней нужно найти k самых тяжёлых арбузов. На каждом запросе разрешается либо сравнить два арбуза, либо вывести ответ.
В задаче J спрашивалась длина минимального маршрута по сетке улиц, если нужно проехаться по каждой и вернуться в исходную точку.
В последней задаче K нужно было отсортировать N строчек с K параметров по сумме их попарных произведенией.