Задачки «полуфинала» соревнования МТС (True Tech Arena 2024) — обзор, разбор

Немного неожиданно что этот уровень назвали «полуфинал» — участники попадали в него сразу после квалификации, проходившей в первой половине октября. И в квалификации задачки были «не бей лежачего» (коротко упомянем их тоже). В «полуфинале» же предложили 5 задач с тем чтобы решить их за 5 часов, но время можно было выбрать любое в течение нескольких дней. Я решил две, ещё две понимаю как решать и по одной кажется без идей. На решённые задачи затратил минут 20, на нерешенные часа полтора. Давайте посмотрим на них вместе — вдруг вам будет интересно обсудить, поправить или подсказать.

Оговорюсь: я не имею отношения к МТС и не занимаюсь «спортивным/олимпиадным» программированием. Обычный мидл-девелопер из обычной конторы. Отчасти поэтому мне как и большинству из вас подобные задачки в излишних количествах кажутся немного скучными 🙂

Здесь речь про «алгоритмический трек» — а насчет параллельного соревнования по «роботам» можно посмотреть мою предыдущую статью.

Задачки Отборочного Раунда

Эти были явно просто чтобы выбрать тех кто хочет участвовать и хоть немного умеет программировать:

1. На новом тарифном плане за первые 100 GiB интернет-трафика абонент платит a рублей, за каждый последующий GiB трафика — по b рублей. Если абонент потратил менее 100 GiB за месяц, он всё равно платит a рублей. Определить оплату по израсходованному трафику. В общем, нечто тривиальное на один if-else и деление.

2. Назовём строку MTS-строкой, если из неё можно удалить все символы, кроме трёх так, чтобы оставшиеся три буквы образовывали слово MTS. Дана строка, проверьте, является ли она MTS-строкой. Короче, проверить что в строке есть буквы M, T, S с учётом порядка, но возможно разделенные другими буквами. Наверное во времена Паскаля и Бейсика это было чуть сложнее писать — но сейчас конечно загадки не представляет. Можно и регэкспом проверить (строка до 10000 символов).

3. В мобильной сети базовые станции считают сколько соединений выполнено с их территории. Для упрощения каждый звонок абонента обрабатывается (и учитывается) всегда только одной станцией. Ну и поскольку звонок это всегда соединение между парой абонентов — соединение сосчитается и на той станции рядом с которой находится вызываемый абонент. Если оба абонента на территории одной станции, конечно, её счётчик увеличивается на 2. Дан массив счетчиков соединений с базовых станций (скажем, за месяц) и нужно проверить есть ли в нём ошибка, или такой набор счетчиков действительно мог появиться как результат правильной работы оборудования. Очень длинно описано в оригинале, но смысл просто проверить сумму на чётность.

Теперь перейдём к задачам «Полуфинала». Я решил сначала прочесть все условия и поэтому выполнять задачи стал не по порядку.

Задача #1 — Статистика Соединений

Опять про эти базовые станции. Принцип увеличения счётчиков точно такой же как в 3й задаче из отбора (см абзац выше), но теперь нужно по массиву счётчиков посчитать: какое могло быть минимальное количество соединений между двумя абонентами находящимися на территории одной станции. Гарантируется что в этот раз оборудование работало без сбоев.

Эту задачу я сначала побоялся трогать, но в конце вернулся к ней и сдал, разумеется за 5 минут.

Задача #2 — MTS-строки

Опять речь о строках в которых есть подпоследовательность букв M, T, S (по порядку, но необязательно по соседству). Нужно посчитать вероятность что такая последовательность найдётся в строке длины N < 100000 сгенерированной случайно из букв латинского алфавита. Довольно мудрёное пожелание по представлению результата:

Можно показать, что вероятность можно единственным способом представить в виде дроби p/q, где p и q взаимно просты, а знаменатель взаимно прост с 998 244 353. Выведите значение p⋅q⁻¹ по модулю 998 244 353, то есть такое число 0 ≤ x ≤ 998 244 353, что q⋅x даёт при делении на 998 244 353 такой же остаток, что и p.

С этой задачей я поборолся немного да и плюнул — из-за формы представления результата невозможно понять в какую сторону ошибся 🙂 а я скорее всего неправильно учитывал вероятности из-за строк которые уже содержат 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-я велодорожка соединяет перекрёстки a_i и b_i, а стоимость проезда по ней на самокате равна c_i. Расстояние между площадями определяется как минимальное количество велодорожек, которые надо проехать, чтобы добраться от одной площади до другой.

Кроме того, появились специальные аэросамокаты. Используя аэросамокат, вы можете переместиться с любого перекрёстка i > 1 на некоторый перекрёсток k, затратив сумму d_i, если выполняются следующие условия:

• Расстояние между перекрёстками i и k не превосходит m_i.

• Расстояние между перекрёстком 1, где находится диспетчерская, и перекрёстком k равно расстоянию между перекрёстком 1 и перекрёстком i (так как аэросамокат должен на всём пути следования поддерживать постоянное расстояние до диспетчерской — это условие службы безопасности воздушного движения).

По информации о расположении самокатов и аэросамокатов определите минимальную стоимость проезда с перекрёстка s до перекрёстка f с помощью самокатов и аэросамокатов МТС-Юрент.

Входные данные

Первая строка входных данных содержит три целых числа — количество перекрёстков n, стартовый перекрёсток s и перекрёсток f, до которого надо доехать (2 ≤ n ≤10⁵, 1 ≤ s, f ≤ n). i-я из последующих n−1 строк содержит по три целых числа a_i, b_i и c_i и задаёт i-ю велодорожку, соединяющую площади a_i и b_i, проезд по которой на обычном самокате стоит c_i  (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ c_i ≤ 10⁹). Гарантируется, что образованный на множестве площадей и велодорожек граф является деревом.

В последующих n−1 строках заданы параметры аэросамокатов. j-я из этих строк задаёт параметры аэросамокатов, стартующих с перекрёстка j+1, и содержит два целых числа d_j и m_j — стоимость полёта на аэросамокате и максимальное расстояние от перекрёстка j+1 соответственно (1 ≤ d_j  ≤ 10⁹, 1 ≤ m_j ≤ 2⋅10⁵).

Эту задачу я не стал решать — с одной стороны вроде понятно что делать — с другой она меня точно на часок бы заняла. Не очень интересно возиться. Но может я её недооценил?

Заключение

В общем, если вы от скуки решаете типовые задачки на каком-то из нижне-середнячковых уровней CodeForces (синий, фиолетовый) хотя бы несколько раз в год — скорее всего этот «полуфинал» не показался бы вам сложным.

С другой стороны МТС явно позиционировал это мероприятие в том числе для маркетинга в IT-сообществе и пополнения базы для своих HR-ов (там было много подробностей при регистрации) — а ценность подобных задач в «промышленной» разработке не очень большая. (и наоборот, «топы» которые щёлкают такие задачи как орешки, откровенно скучают на рутинной разработке).

Догадываюсь что для большинства обычных программистов (ну, как и для меня) мотивация ковыряться с этими задачами была довольно низкой — большинство из нас не всегда может выделить, скажем, 5 часов времени подряд (у меня было максимум 2 с утра, пока не проснулись домашние) даже в течение нескольких дней — и в то же время целиться на главный приз (не будучи «спортсменом») — немного наивно — а каких-нибудь памятных футболок, скажем, за выход в финал — не обещали 🙂

P.S. отмечу низкий технический и организационный уровень организации контеста — о проблемах с «роботами» я уже писал — здесь вроде получше, но страница с отправкой задач зависала раза 3 сама собой — и по-моему блочилась при отправке. Грузится интерфейс прямо скажем не мгновенно. Go версии 1.19.13 (на дворе 1.23 уже с функциями min/max например) Всё это конечно несколько отбивает охоту решать задачи 🙂