Задачки «полуфинала» соревнования МТС (True Tech Arena 2024) — обзор, разбор
Немного неожиданно что этот уровень назвали «полуфинал» — участники попадали в него сразу после квалификации, проходившей в первой половине октября. И в квалификации задачки были «не бей лежачего» (коротко упомянем их тоже). В «полуфинале» же предложили 5 задач с тем чтобы решить их за 5 часов, но время можно было выбрать любое в течение нескольких дней. Я решил две, ещё две понимаю как решать и по одной кажется без идей. На решённые задачи затратил минут 20, на нерешенные часа полтора. Давайте посмотрим на них вместе — вдруг вам будет интересно обсудить, поправить или подсказать.
Оговорюсь: я не имею отношения к МТС и не занимаюсь «спортивным/олимпиадным» программированием. Обычный мидл-девелопер из обычной конторы. Отчасти поэтому мне как и большинству из вас подобные задачки в излишних количествах кажутся немного скучными :)
Здесь речь про «алгоритмический трек» -, а насчет параллельного соревнования по «роботам» можно посмотреть мою предыдущую статью.
Задачки Отборочного Раунда
Эти были явно просто чтобы выбрать тех кто хочет участвовать и хоть немного умеет программировать:
На новом тарифном плане за первые 100 GiB интернет-трафика абонент платит a рублей, за каждый последующий GiB трафика — по b рублей. Если абонент потратил менее 100 GiB за месяц, он всё равно платит a рублей. Определить оплату по израсходованному трафику. В общем, нечто тривиальное на один if-else и деление.
Назовём строку MTS-строкой, если из неё можно удалить все символы, кроме трёх так, чтобы оставшиеся три буквы образовывали слово MTS. Дана строка, проверьте, является ли она MTS-строкой. Короче, проверить что в строке есть буквы M, T, S с учётом порядка, но возможно разделенные другими буквами. Наверное во времена Паскаля и Бейсика это было чуть сложнее писать -, но сейчас конечно загадки не представляет. Можно и регэкспом проверить (строка до 10000 символов).
В мобильной сети базовые станции считают сколько соединений выполнено с их территории. Для упрощения каждый звонок абонента обрабатывается (и учитывается) всегда только одной станцией. Ну и поскольку звонок это всегда соединение между парой абонентов — соединение сосчитается и на той станции рядом с которой находится вызываемый абонент. Если оба абонента на территории одной станции, конечно, её счётчик увеличивается на 2. Дан массив счетчиков соединений с базовых станций (скажем, за месяц) и нужно проверить есть ли в нём ошибка, или такой набор счетчиков действительно мог появиться как результат правильной работы оборудования. Очень длинно описано в оригинале, но смысл просто проверить сумму на чётность.
Теперь перейдём к задачам «Полуфинала». Я решил сначала прочесть все условия и поэтому выполнять задачи стал не по порядку.
Задача #1 — Статистика Соединений
Опять про эти базовые станции. Принцип увеличения счётчиков точно такой же как в 3й задаче из отбора (см абзац выше), но теперь нужно по массиву счётчиков посчитать: какое могло быть минимальное количество соединений между двумя абонентами находящимися на территории одной станции. Гарантируется что в этот раз оборудование работало без сбоев.
Скрытый текст
Сперва может показаться странно-непонятно, но если подумать, то мы можем посчитать требуемый результат только в одном случае — когда на одной из базовых станций счётчик больше чем на всех остальных вместе взятых. Дальше наверное догадаетесь :)
Эту задачу я сначала побоялся трогать, но в конце вернулся к ней и сдал, разумеется за 5 минут.
Задача #2 — MTS-строки
Опять речь о строках в которых есть подпоследовательность букв M, T, S (по порядку, но необязательно по соседству). Нужно посчитать вероятность что такая последовательность найдётся в строке длины N < 100000 сгенерированной случайно из букв латинского алфавита. Довольно мудрёное пожелание по представлению результата:
Можно показать, что вероятность можно единственным способом представить в виде дроби p/q, где p и q взаимно просты, а знаменатель взаимно прост с 998 244 353. Выведите значение p⋅q−1 по модулю 998 244 353, то есть такое число 0 ≤ x ≤ 998 244 353, что q⋅x даёт при делении на 998 244 353 такой же остаток, что и p.
Скрытый текст
Чтобы избежать мудрёных-непонятных терминов, представим что мы последовательно вычисляем требуемую вероятность для строки длиной K если перед этим уже сосчитали какие-то данные для строки длиной K-1. Есть три варианта:
в строке K-1 ещё не было буквы M, с вероятностью 25/26 она такой и останется при добавлении следующего символа, а с вероятностью 1/26 новая буква окажется как раз M.
в строке К-1 была буква М, но не было Т — и с теми же 25/26 она таковой и останется, а с вероятностью 1/26 (придёт Т) перейдёт в третье состояние.
в строке К-1 были буквы М и Т с учетом порядка, и мы ждём только S. Она либо не придёт (25/26) либо придёт (1/26).
Насчет представления результата — речь о неких популярных операциях из модульной арифметики, вероятно ключевой момент здесь — найти в стандартной библиотеке modular inverse (но можно и самому написать — это, кажется, чуть более продвинутая версия «алгоритма Евклида»).
С этой задачей я поборолся немного да и плюнул — из-за формы представления результата невозможно понять в какую сторону ошибся :), а я скорее всего неправильно учитывал вероятности из-за строк которые уже содержат MTS на длине меньшей чем N.
Задача #3 — Просто, значит красиво
В МТС придумали новую фишку с красивыми номерами. В номере из 11 цифр первые четыре задаются (некий фиксированный префикс, вроде »8916») -, а остальные абонент может выбрать по желанию — лишь бы всё число целиком (11-значное) было простым.
Дополнительная VIP-фишка — среди таких «простых» номеров — номера в которых префикс содержится ещё раз (только среди последних 7 цифр).
Требуется по заданному префиксу сосчитать сколько всего возможно с ним «красивых» (т.е. простых) номеров, а сколько VIP.
Эту задачу я не знаю как решать — в смысле, решение-то я попробовал написать, даже два -, но перебрать 5 млн чисел с проверкой на простоту — это у меня не укладывается в требуемую 1 секунду. Хотя правильный результат получить несложно.
Задача #4 — Королевская жизнь
Довольно длинное описание — речь идёт о шахматной доске размером 1001×1001 клеток, на которой расставлены до 100000 пешек. Требуется найти за какое минимальное количество ходов король, оказавшийся в некой заданной клетке, может добраться до ближайшей пешки и съесть её (нужно помнить что король ходит на 1 клетку в любом из 8 направлений). Решить задачу для 100000 заданных позиций короля.
Скрытый текст
Количество ходов короля от одной клетки до другой равно максимуму из расстояний между этими клетками по горизонтали и по вертикали.
Эту задачку я решил первой, на Go (и видимо на любом языке с быстродействием приближающимся к нативному коду) она «зашла» втупую — с перебором всех пешек для каждой позиции короля и выбором минимального расстояния. Кажется что если бы среди данных был максимальный тест (на 100000 пешек и столько же позиций короля) то этот наивный вариант не укладывался бы в 1 секунду, можно было бы немного пооптимизировать, м.б. поделив пространство пешек на сектора и т.п. Но это не понадобилось. Возможно на оптимизированный вариант можно было бы придумать ломающий тест т.к. пешки разрешалось ставить в одну и ту же клетку больше одной.
Задача #5 — Аэросамокаты
Неплохая задачка на графы (даже больше чем на одну тему из них). Условие длинное, но придётся его переписать полностью:
В городе X введён экспериментальный режим работы сервиса проката самокатов МТС-Юрент.
В городе есть N перекрёстков, соединённых N−1 велодорожками с двусторонним движением так, чтобы между любыми двумя перекрёстками можно было добраться по сети велодорожек. i-я велодорожка соединяет перекрёстки ai и bi, а стоимость проезда по ней на самокате равна ci. Расстояние между площадями определяется как минимальное количество велодорожек, которые надо проехать, чтобы добраться от одной площади до другой.
Кроме того, появились специальные аэросамокаты. Используя аэросамокат, вы можете переместиться с любого перекрёстка i > 1 на некоторый перекрёсток k, затратив сумму di, если выполняются следующие условия:
Расстояние между перекрёстками i и k не превосходит mi.
Расстояние между перекрёстком 1, где находится диспетчерская, и перекрёстком k равно расстоянию между перекрёстком 1 и перекрёстком i (так как аэросамокат должен на всём пути следования поддерживать постоянное расстояние до диспетчерской — это условие службы безопасности воздушного движения).
По информации о расположении самокатов и аэросамокатов определите минимальную стоимость проезда с перекрёстка s до перекрёстка f с помощью самокатов и аэросамокатов МТС-Юрент.
Входные данные
Первая строка входных данных содержит три целых числа — количество перекрёстков n, стартовый перекрёсток s и перекрёсток f, до которого надо доехать (2 ≤ n ≤105, 1 ≤ s, f ≤ n). i-я из последующих n−1 строк содержит по три целых числа ai, bi и ci и задаёт i-ю велодорожку, соединяющую площади ai и bi, проезд по которой на обычном самокате стоит ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 109). Гарантируется, что образованный на множестве площадей и велодорожек граф является деревом.
В последующих n−1 строках заданы параметры аэросамокатов. j-я из этих строк задаёт параметры аэросамокатов, стартующих с перекрёстка j+1, и содержит два целых числа dj и mj — стоимость полёта на аэросамокате и максимальное расстояние от перекрёстка j+1 соответственно (1 ≤ dj ≤ 109, 1 ≤ mj ≤ 2⋅105).
Скрытый текст
В общем, мы ищем самый дешевый путь в графе. Если бы не было «аэросамокатов», граф был бы просто деревом (по условию) это было бы совсем тривиально (много решений, даже «волновой» алгоритм зайдёт т.к. дерево)
Нам в общем-то надо к описанию графа добавить ребра создаваемые аэросамокатами. У них очень мудрёное описание как видите, но зато их получается не очень много (не полный граф): ребра могут соединять только «одинаковые уровни» дерева и есть предел длины полёта (в рёбрах «основного» дерева).
Ну и после этого посчитать самый дешевый путь (предположительно, Дейкстра). Есть опасение что максимальный тест с заданными ограничениями (на графе с 100000 вершинами и сопоставимым количеством «аэромаршрутов») может представить трудности с учётом ограничения времени в 1 секунду -, но не знаю был ли подобный тест использован в проверке.
Эту задачу я не стал решать — с одной стороны вроде понятно что делать — с другой она меня точно на часок бы заняла. Не очень интересно возиться. Но может я её недооценил?
Заключение
В общем, если вы от скуки решаете типовые задачки на каком-то из нижне-середнячковых уровней CodeForces (синий, фиолетовый) хотя бы несколько раз в год — скорее всего этот «полуфинал» не показался бы вам сложным.
С другой стороны МТС явно позиционировал это мероприятие в том числе для маркетинга в IT-сообществе и пополнения базы для своих HR-ов (там было много подробностей при регистрации) -, а ценность подобных задач в «промышленной» разработке не очень большая. (и наоборот, «топы» которые щёлкают такие задачи как орешки, откровенно скучают на рутинной разработке).
Догадываюсь что для большинства обычных программистов (ну, как и для меня) мотивация ковыряться с этими задачами была довольно низкой — большинство из нас не всегда может выделить, скажем, 5 часов времени подряд (у меня было максимум 2 с утра, пока не проснулись домашние) даже в течение нескольких дней — и в то же время целиться на главный приз (не будучи «спортсменом») — немного наивно -, а каких-нибудь памятных футболок, скажем, за выход в финал — не обещали :)
P.S. отмечу низкий технический и организационный уровень организации контеста — о проблемах с «роботами» я уже писал — здесь вроде получше, но страница с отправкой задач зависала раза 3 сама собой — и по-моему блочилась при отправке. Грузится интерфейс прямо скажем не мгновенно. Go версии 1.19.13 (на дворе 1.23 уже с функциями min/max например) Всё это конечно несколько отбивает охоту решать задачи :)
