Всем привет! Это Анна Крюкова и Алексей Малеев, мы курировали организацию алгоритмического трека на True Tech Champ. Участники боролись за главные призы в двух треках — алгоритмическом и программировании роботов. Очный финал и награждение победителей состоялись 8 ноября в МТС Live Холл в Москве — гости чемпионата не только поддерживали участников, но и слушали доклады на ИТ-конференции, знакомились с единомышленниками и заряжались новыми идеями в неформальном лектории — True Tech Garage. А еще проверяли свои суперспособности в «айтивностях» — например, кодили, попутно преодолевая натяжение троса, гоняли робомышей по лабиринту (прямо как финалисты), собирали серваки и вскрывали двери на скорость по гайду от белого взломщика.
Сегодня вспомним, как проходил чемпионат, и разберем задачи алгоритмического трека. Три финалиста покажут свои решения, которые привели их к победе, а заодно расскажут, почему им вообще нравится участвовать в соревнованиях. Погнали!
True Tech Champ: два соревновательных трека и сильная конкуренция
В 2024 году чемпионат проходил во второй раз — об этом моя коллега писала здесь, тогда заявки на участие подали около 8 тысяч человек. В этот раз мы получили больше 12 тысяч заявок, в том числе от ребят из сборной России по информатике и победителей международных соревнований по программированию. Когда мы просили финалистов поделиться впечатлениями об участии в True Tech Champ, они подчеркивали, что конкуренция была очень сильной. Пройти в финальные этапы смогли 250 участников — школьники, студенты, ребята, которые уже работают в ИТ. Отборочный этап и полуфинал, как и в прошлом году, проходил онлайн, а финал — очно, 8 ноября в МТС Live Холл. Общий призовой фонд чемпионата превысил 10 млн рублей.
Как я уже сказала в подводке к посту, на True Tech Champ было два трека:
Алгоритмический — это классический олимпиадный формат. Ребята решали алгоритмические задачи и соревновались в индивидуальном зачете.
Программирование роботов — участники собирались в команды и программировали робомышей на скоростное прохождение лабиринта. Достичь финиша было не так просто: роботам мешали подвижные препятствия, дым и вспышки света. Как мы разрабатывали этот трек, подробно рассказали в посте «Спасти робомышь от киберминотавра».
В финале ребята соревновались на глазах у зрителей, шоу-гонку роботов комментировал блогер-миллионник Yuri The Professional.
А вот и победители алгоритмического трека:
первое место — Александр Бабин (Москва);
два вторых места — Владимир Звездин (Санкт-Петербург), Иван Пискарев (Москва);
три третьих места — Алексей Михненко (Москва), Гимран Абдуллин (Казань), Роман Первутинский (Сургут).
Победители трека «Программирование роботов»:
первое место — «Котята и роботы» (Санкт-Петербург) — Дмитрий Титов и Максим Попов;
второе место — ClosedCV (Республика Татарстан) — Николай Ростов, Андрей Растопшин, Евгений Шломов;
третье место — «Микромыши» (Ленинградская область и Санкт-Петербург) — Глеб Прохоров, Денис Логашов, Дмитрий Чупров.
В True Tech Champ интересно не только участвовать — для гостей мы тоже подготовили много активностей. На протяжении всего дня можно было слушать доклады от экспертов.
Преподаватель Сколтеха Алексей Зайцев рассказал, как обмануть нейросеть, доктор биологических наук Вячеслав Дубынин — как соревновательность и увлечения формируют наш характер, Research Engineer Артем Якимчук — как обучать роботов в виртуальной среде, чтобы они ничего не сломали в реальной. В интерактивном лектории True Tech Garage можно было пройти стресс-воркшоп «Плохой собес», узнать новое на мастер-классе «Как логика помогает избавиться от лишней работы», сыграть в бизнес-игру The CODE и обменяться контактами с единомышленниками. Для тех, кто устал получать новые знания, работали зоны с кодерскими и фановыми «айтивностями». Гости покоряли скалодром по маршруту, который создал ИИ, писали код под натяжением троса, проходили мастер-класс от белого взломщика, паяли платы и даже делали татуировки на память о чемпионате. Завершился вечер выступлением хедлайнеров.
Как это было:
Дальше познакомимся с финалистами и посмотрим решения задач.
Роман Первутинский
Место силы
С олимпиадной информатикой я познакомился в девятом классе, когда проходил отбор на смену «Сириуса», и меня сразу затянуло. Это почти как математика, но вдобавок ты еще пишешь код — казалось, интереснее этого в принципе уже ничего не может быть. Те самые первые смены, без преувеличения, стали одними из лучших событий моей жизни. Я получал огромный кайф от знакомства с такими же увлеченными людьми. Встречался с действительно крутыми ребятами и преподавателями, они меня вдохновляли — и мне очень хотелось к ним приобщиться. С тех пор в «Сириусе» я был около пяти раз, в прошлом году — уже в качестве преподавателя.
В девятом классе я не только впервые попал в «Сириус», но и поехал на Всероссийскую олимпиаду школьников по информатике в Москву. Тогда даже не мечтал победить, ведь мой опыт был нулевым. Все, что я знаю сейчас, мне только предстояло освоить. За два дня я набрал только 85 баллов из 800 и был, кажется, десятым с конца. Но зато я смог увидеть своими глазами, как проводятся крупные олимпиады. И, главное, у меня появились амбиции. Мне захотелось подготовиться, вернуться и показать крутой результат.
С тех пор такие события стали для меня местом силы. Ты приезжаешь, видишь огромный зал, несколько сотен компьютеров, вокруг много талантливых людей — потрясающе!
Легче всего давалась математика
Не могу сказать, что я с детства мечтал участвовать в олимпиадах. Меня интересовали разные вещи, но такого, чтобы я ощущал свое призвание в чем-то, не было.
Дальше все само собой завертелось: так вышло, что в школе математика давалась мне легче остальных предметов. Я и сам не заметил, как постепенно нарабатывал навыки, которые потом привели меня к олимпиадам. То есть все получилось гармонично. Не было такого, что кто-то убедил меня погрузиться в математику или я вдохновился кем-то из этой сферы. Мне кажется, «хардовость» в целом редко начинается с того, что ты хочешь стать в конкретной области лучшим из лучших. Это работает по-другому: сначала тебе интересна база, какие-то простые вещи, и ты осваиваешь именно их. А со временем переходишь к действительно сложным задачам, просто потому, что развиваешься и растешь. Это наглядно прослеживается на олимпиадах: те, кто, казалось бы, только вчера занимали первые места с конца списка, через какое-то время — уже в его начале.
Проверка сил на True Tech Champ
Помню, в 2023 мы с друзьями поехали преподавать информатику в Воронеж. И тут на почту мне упало письмо с приглашением поучаствовать в True Tech Champ 2023. Тогда я немного удивился: впервые увидел, что МТС проводит такие соревнования. Это в 2024 году про True Tech Champ уже все знали, а тогда мы не представляли, что нас ждет. Дальше у кого-то из ребят не хватило времени на отборочные этапы, кто-то не смог их пройти, но у меня все получилось. Тогда в финале только один человек решил все задачи без исключения. Я оказался на десятом месте — если бы был чуточку побыстрее, возможно, вошел бы в топ-6. Победить не получилось, но мне понравилась организация, поэтому я решил вернуться через год.
Задачи на отборочном туре True Tech Champ 2024 оказались для меня довольно привычными: они были как на студенческих олимпиадах. А вот в финале некоторые очень удивили. Запомнилась задача С на двойной запуск: тебе дается информация, ты должен ее как-то закодировать, потом твоя программа запускается второй раз — и нужно восстановить эту информацию. Помню, сначала перепрыгнул через эту задачу, потому что другие ребята уже сдавали D и E. Когда я вернулся к ней в конце, она уже не показалась мне такой сложной, и я быстро ее решил.
Как только сдал D и E, увидел, что поднялся в топ-3. Остальное доделывал трясущимися руками — очень волновался.
В 2024 году на True Tech Champ были сильные ребята: сборная России, которая участвовала в Международной олимпиаде по информатике, в полном составе, победители студенческого чемпионата мира по программированию, много других знакомых ребят. До последнего казалось, что мои шансы войти в топ-6 невелики. Даже когда вышел на сцену на награждение, я по-прежнему не верил в победу.
Мысль в форме кода
Я буду продолжать участвовать в олимпиадах, потому что мне нравится соревновательность. У меня нет цели стать заметным или получить, например, крутой оффер. А вот опыт и развитие очень важны. На олимпиадах учишься облекать свои мысли в форму кода, быстро находить ответы в сложных ситуациях, генерить идеи. Ты быстрее растешь. А еще решение задач — про креативность, и это всегда пригодится в жизни.
Возможно, скоро я начну двигаться в сторону стажировки — мне интересны research, backend. Хочу посмотреть, как работают цепочки в компании, на что нужно обращать внимание, какие проекты у меня могут быть. Но пока я сконцентрирован на нелегкой учебе на Физтехе и олимпиадах.
Задача C. Веселая реклама
Имя входного файла: стандартный ввод.
Имя выходного файла: стандартный вывод.
Ограничение по времени: 3 секунды.
Ограничение по памяти: 1 024 мебибайта.
Это задача с двойным запуском. Первый запуск — интерактивный.
Недавно вышла новая линейка тарифов МТС. У каждого — свое название и свой слоган. Тарифов в линейке очень много, так что даже с помощью слоганов перечислить клиенту все будет сложно.
Сотрудники Отдела рекламы придумали неожиданный вариант решения проблемы: предложили составить из слоганов стихотворные тексты. Их заказали специалисту по стихотворной рекламе. Но он потребовал уточнить техническое задание — сообщить схему рифмовки.
Как строится схема рифмовки? Пусть в одном куплете рекламы будет l строк. Тогда схема рифмовки — строка из l заглавных латинских букв с таким свойством:
первая буква строки всегда равна A и соответствует первой строке;
если строка рифмуется с уже существующей, она обозначается такой же буквой;
если строка не рифмуется ни с одной из существующих, она обозначается лексикографически наименьшей неиспользованной буквой.
Например, в четверостишии, где рифмуется первая строка с третьей, а вторая — с четвертой, схема рифмовки будет ABAB. Если все строки рифмуются между собой — схема будет AAAA. А вот, например, в японском танка из пяти не рифмующихся строк схема рифмовки будет ABCDE.
Проблема была в том, что у специалиста стоял очень старый мессенджер «Морзянка» с максимальным уровнем защиты. В качестве сообщений он принимает только наборы из не более чем 50 попарно взаимно простых целых чисел, больших единицы и меньших 1018. Сеанс связи состоит из нескольких таких сообщений. При этом наименьшее общее кратное всех передаваемых за сеанс связи чисел не должно превосходить 1018.
Вам дается набор схем рифмовок для разных l. Нужно написать программу, которая передает строки через мессенджер по одному сообщению на строку за один сеанс связи, а потом декодирует полученную информацию, восстанавливая схемы рифмовок. При первом запуске вы получаете схемы и эмулируете сеанс связи, отправляя закодированные сообщения по очереди. При втором — получаете информацию, переданную при первом запуске (с точностью до перестановки чисел внутри одного сообщения). Вы должны восстановить переданные схемы рифмовки.
Протокол взаимодействия
При работе в режиме передачи первая строка входных данных содержит слово encode. Дальше сообщается количество t схем рифмовки, которые нужно передать в текущем сеансе связи (1 ≤ t ≤ 2 · 105).
Потом t раз взаимодействие происходит по следующему сценарию: вы получаете строку длиной не менее двух и не более 15 символов, состоящую из заглавных латинских букв и задающую схему рифмовки. Потом генерируете сообщение в виде k попарно взаимно простых целых чисел ai, больших единицы (1 ≤ k ≤ 50). Выводите в первой строке k, а во второй — требуемые k чисел в правильном порядке.
Не забывайте после вывода k и после вывода строки с ai выводить команду перевода строки. А еще — сбрасывать буфер вывода вызовом функции flush языка программирования, который вы используете.
Обратите внимание, что ограничение на НОК всех передаваемых чисел работает на весь сеанс. То есть на все числа, передаваемые во всех сообщениях.
Формат входных данных
При работе в режиме приема первая строка входных данных содержит слово decode. Вторая строка содержит количество сообщений t. Дальше следуют сами сообщения в том же формате, в котором они были переданы в режиме передачи: на первой строке количество сообщений k, дальше — k целых чисел ai. При этом порядок чисел ai внутри строки может быть изменен.
Формат выходных данных
Для каждого из t сообщений выведите схему рифмовки, которая была закодирована этим сообщением.
Примеры
Решение
Какое максимальное количество взаимно простых чисел больше 1 можно взять, прежде чем их наименьшее общее кратное превысит 10^18? Каждое новое число добавляет в НОК простой множитель. Произведение первых 15 простых чисел (от 2 до 47) примерно равно 6*10^17. Значит, ответ — 15.
Нам нужно закодировать строки длины не более 15 символов со следующим свойством: первая «A» встречается в ней раньше первой «B», первая «B» раньше первой «C» и так далее. Следовательно, если мы знаем, на каких позициях стоят одинаковые буквы, то можем восстановить, какие именно.
Сопоставим позиции i i-ое простое число и передадим для каждой буквы, которая встречается в строке, произведение простых чисел. Эти числа соответствуют позициям, на которых стоит буква. Очевидно, что все эти числа взаимно просты.
Чтобы восстановить исходную строку, факторизуем все полученные числа, упорядочим их по наименьшему простому делителю и заполним позиции соответствующими буквами.
Например, в строке ABACB одинаковые буквы стоят на позициях {1, 3}, {2, 5} и {4}. То есть она будет закодирована как {10, 33, 7}.
Задача A. Абстракционист и треугольники
Имя входного файла: стандартный ввод.
Имя выходного файла: стандартный вывод.
Ограничение по времени: 1 секунда.
Ограничение по памяти: 1 536 мебибайт.
Это задача с двойным запуском.
Абстракционист Калевич хочет переслать несколько неравнобедренных треугольников на выставку, которую организовали в офисе МТС. Но так как почта Берляндии берет оплату за периметр треугольника, Калевич хочет сэкономить.
Калевич попросил вас закодировать треугольник ненулевой площади с целыми сторонами и периметром p, никакие две стороны которого не равны, треугольником ненулевой площади и периметром p — 6. А потом по закодированному треугольнику восстановить исходный.
Формат входных данных
Первая строка входных файлов содержит режим работы:
encode — если требуется закодировать треугольники;
decode — если требуется восстановить исходные.
Вторая строка содержит одно целое число t (1 ≤ t ≤ 25 000) — количество тестовых примеров.
Дальше следуют тестовые примеры по одному на строку.
В режиме кодирования каждый тестовый пример содержит три целых числа a, b и c — стороны исходного треугольника. Гарантируется, что 3 ≤ a + b + c ≤ 1 000, что a, b и c попарно не равны. И что треугольник со сторонами a, b и c существует, и у него ненулевая площадь.
В режиме декодирования каждый тестовый пример содержит три целых числа a′, b′ и c′ — переставленные в каком-то порядке стороны, выведенные вашей программой в режиме кодирования.
Формат выходных данных
В режиме кодирования выведите для каждого тестового примера в произвольном порядке три целых числа a′ , b′ , c′ . Такие, что треугольник со сторонами a′ , b′ , c′ существует, у него ненулевая площадь и a′ +b′ + c′ = a + b + c − 6.
В режиме декодирования для каждого тестового примера выведите три стороны исходного треугольника. Порядок вывода сторон внутри одного тестового примера произвольный.
Примеры
Решение
Нам нужно по неравнобедренному треугольнику с периметром p получить треугольник с периметром p — 6 (и потом восстановить исходный). Логичная идея — отнять от сторон 1, 2 и 3, но при этом нельзя нарушить неравенство треугольника.
Пусть исходные стороны — a, b и c (a < b < c), при этом a + b > c. Проверим неравенства треугольника для a - 1, b - 2, c - 3: (a - 1) + (b - 2) > (c - 3), (a - 1) + (c - 3) > (b - 2), (b - 2) + (c - 3) > (a - 1). Первое выполняется сразу, для второго и третьего нужно заметить, что самый маленький неравнобедренный треугольник — это (2, 3, 4).
Чтобы восстановить исходный треугольник, нужно просто прибавить 1, 2 и 3 к сторонам в порядке возрастания.
Владимир Звездин
Удивился, когда увидел себя в лидерборде вторым
В олимпиадах я начал участвовать летом между 6 и 7 классом. Помню, поехал в Челябинскую летнюю компьютерную школу и именно там узнал об алгоритмических задачах. Оказалось, у меня хорошо получается их решать. Поэтому, когда я вернулся домой, продолжил занятия в школьном кружке. Постепенно такие задачи превратились в хобби: я просто тонул в них. Развиваться подстегивал не только интерес, но и соревновательный дух. Как мы все знаем, главное, конечно, это участие — но и победа тоже важна.
В 2024 году я победил на Всероссийской олимпиаде школьников (ВСОШ), и меня пригласили на True Tech Champ. Так я тут и оказался.
В финале на все задачи у меня ушло полтора часа. Мне казалось, я решал их медленно. Поэтому удивился, когда в лидерборде увидел себя на второй строчке. Победить до последнего не рассчитывал: соперники были очень сильными. Сдав решения, я просто отдыхал, слушал лекции — о награждении не думал.
Когда понял, что победил, был в шоке.
Задача Б. Больше MTS-строк
Имя входного файла: стандартный ввод.
Имя выходного файла: стандартный вывод.
Ограничение по времени: 3 секунды.
Ограничение по памяти: 1 536 мебибайт.
Назовем МТS-строкой строку, составленную из заглавных букв латинского алфавита, если в ней можно удалить какое-то (возможно, нулевое) количество букв так, чтобы получилась строка MTS.
Назовем строку k-устойчивой MTS-строкой, если при любом разбиении этой строки на k непрерывных подстрок хотя бы одна строка будет MTS-строкой.
Для заданных n и k найдите остаток от деления количества k-устойчивых MTS-строк длины n на 998 244 353.
Формат входных данных
Первая строка входных данных содержит два целых числа n и k (1 ≤ n, k ≤ 3 · 104).
Формат выходных данных
Выведите одно целое число — остаток от деления количества k-устойчивых MTS-строк длины n на 998 244 353.
Примеры
Решение
Вариант 1
Пусть мы знаем строку. Найдем самую длинную подпоследовательность вида MTSMTSMTS….MT (необязательно заканчивается на S). Тогда по принципу Дирихле строка k-устойчивая тогда и только тогда, когда длина такой подпоследовательности >= 3k.
Теперь посчитаем количество таких строк. Пусть самая длинная подпоследовательность описанного выше вида — s. Тогда количество вариантов построить такую строку — C(n, s) * 25^(n - s), C(n, s) — количество вариантов выбрать позиции, на которых будет стоять соответствующий символ MTSMTS… 25 — количество символов, которое можно поставить на позицию, не состоящую в подпоследовательности. Значит, количество способов расставить символы вне под подпоследовательности — 25^(n - s).
Ответ: sum[s=3k…n](C(n, s) * 25^(n - s))
Забавный факт: чтобы дополнительно убедиться в корректности решения, можно написать эту формулу для k = 0 и получить sum[s=0..n](C(n, s) * 25^(n - s)) = 26^n по биному Ньютона, что сходится с ответом.
Решение 2
Заметим, что авторы поставили лояльные ограничения: n, k <= 3e4, TL = 3s, так что напишем решение за O(nk).
dp_i, j — количество строк таких, что максимальная подпоследовательность вида MTSMTSM…. равна j. База — dp_0, 0 = 1, переход — dp_i, j = dp_i - 1, j - 1 + 25 * dp_i - 1, j.
Такое решение просто так не заходит, поэтому сделаем пару неасимптотических оптимизаций. Первая — 3 k > n => ответ = 0. Вторая — если 3 k > n / 2, то во втором измерении будем хранить количество элементов, которые не входят в подпоследовательность, иначе во втором измерении храним min (3 * k, количество элементов в подпоследовательности). Таким образом, константа уменьшилась в два раза. Третья — решение может не зайти по памяти. Заметим, что для пересчета i-го слоя необходим только (i-1)-й слой, поэтому храним только его.
Иван Пискарев
Математика со мной с детства
В школе родители отправили меня в математический класс — и не потому, что желали для меня какой-то определенной карьеры, а потому, что мне всегда легко давались примеры. Еще до школы я любил складывать и вычитать. Так и продолжилось: моим любимым предметом в школе стала математика, потом — информатика.
В седьмом классе я записался на кружок по информатике и много занимался. Тогда же мне удалось пройти на ВСОШ — можно сказать, это был тест-драйв. Потом все закрутилось: меня стали приглашать на сборы, подготовительные мероприятия — все это позволило прокачаться еще больше. В следующем году на ВСОШ я уже стал победителем. Потом готовился к отбору на Международную олимпиаду школьников и в 10–11 классе попал в сборную.
Задачи на True Tech Champ: легко найти решение, но долго его описывать
О True Tech Champ от МТС я услышал от друзей. Плюс на ВСОШ в прошлом году мне дали приглашение сразу на финал, но я все равно прошел отборочный этап — из интереса. Для меня он оказался несложным.
А вот в финале было не так просто. Решения я придумывал быстро, но на то, чтобы их реализовать, то есть набрать на компьютере и сдать, уходило много времени. Сейчас я понимаю, что мне стоило поискать более простую реализацию, которую я бы быстрее напечатал. Но тогда в голову приходили сложные пути, и я долго их описывал — в общем, пришлось попотеть.
Свои шансы на победу я оценивал 50 на 50. С одной стороны, знал: мой уровень неплохой. С другой — конкуренты очень сильные, они уже обгоняли меня на других соревнованиях. А еще я точно не надеялся, что мне удастся набрать самый маленький штраф. Тут поясню: он складывается из времени, которое ты тратишь на решение, и количества допущенных ошибок. Чем дольше сдаешь ответ и чем больше неправильных попыток, тем выше штраф. Как я уже писал, мой оказался самым низким, и это было неожиданностью. Обычно ситуация у меня ровно обратная.
Помню, в финале решил задачи быстрее остальных и ждал, пока другие участники тоже сдадут свои ответы и поднимутся на лидерборде выше меня. Но шло время, а я оставался в списке на первом месте. Потом оказалось, что одному участнику из всех удалось решить последнюю задачу, и он поднялся выше меня. Я занял второе место.
Занимаюсь по настроению
Не могу сказать, что подготовка к олимпиадам отнимает все мое свободное время и в целом утомляет. Обычно действую так: если сегодня не хочется решать задачи, то и пересиливать себя не буду. У меня нет расписания, когда, допустим, я занимаюсь четыре дня в неделю по три часа. При этом иногда увлекаюсь и провожу за задачами весь день — просто потому, что мне это интересно. Кто-то, например, подкасты слушает или сериалы смотрит, а я ухожу в математику.
Что касается планов, пока собираюсь продолжать участвовать в олимпиадах, в том числе в студенческих — это уже больше командный формат. В будущем хотел бы работать в крупной технической компании на позиции, связанной с информатикой и разработкой. Надеюсь, мои знания будут действительно полезными.
А напоследок хочу посоветовать всем школьникам по возможности участвовать в олимпиадах. Это не только опыт, призы и перспективы, например поступление в вуз без вступительных экзаменов, но и комьюнити. Ты знакомишься с единомышленниками из разных городов, из года в год встречаешь их на олимпиадах, вы говорите «на одном языке», становитесь близкими друзьями. И это круче всего!
Задача Д. Графы и запросы
Имя входного файла: стандартный ввод.
Имя выходного файла: стандартный вывод.
Ограничение по времени: 2 секунды.
Ограничение по памяти: 1 024 мебибайт.
Дан неориентированный граф G, состоящий из n вершин и m ребер. У каждой вершины есть значение xv. Назовем характеристикой графа величину c(G) = minu,v|xu − xv| по всем таким парам вершин u ≠ v, что из u в v существует путь. Если в графе нет ребер вообще, положим c(G) = -1.
Вам нужно найти характеристику графа в самом начале и после выполнения каждого из q запросов. В i-ом запросе вам нужно удалить из графа ребро с номером numi. Обратите внимание: все удаления в графе сохраняются, в i-ом запросе граф без ребер num1, num2, ..., numi.
Формат входных данных
В первой строке вам даны числа 1 ≤ n ≤ 105,1 ≤ m ≤ 2 ∗ 105 и 1 ≤ q ≤ 2 ∗ 105 — количество вершин графа, ребер графа и количество запросов.
В следующей строке вам дано n целых чисел −109 ≤ xi ≤ 109 — значения вершин. В следующих m строках заданы ребра графа — по два числа в каждой строке 1 ≤ ui ≠ vi ≤ n, все ребра различны. В следующей строке дано q чисел — номера ребер 1 ≤ numi ≤ m в порядке их удаления из графа.
Формат выходных данных
Выведите q + 1 чисел — характеристику графа до начала выполнения запросов и после выполнения каждого из них.
Примеры
Решение
Ответ на каждый запрос зависит только от состояния графа. Так что можно перейти от запросов удаления ребер к запросам их добавления, просто развернув последовательность запросов.
Чтобы обработать запросы добавления ребер, будем поддерживать текущее значение характеристики, компоненты связности графа и множество значений x_i для каждой компоненты, храня его в std::set.
Заметим, что если концы добавленного ребра уже были в одной компоненте, то характеристика графа не изменится. Если же концы были в разных, то во множество рассматриваемых пар вершин (u, v) в определении характеристики графа добавляются все пары, где одна из вершин пары лежит в первой компоненте, а другая — во второй.
Значит, достаточно найти минимум |x_u - x_v| по всем вышеупомянутым парам (u, v) и обновить им значение характеристики. Чтобы найти это значение, достаточно пройтись по всем вершинам одной из компонент. И с помощью std::set::lower_bound найти оптимальное значение x_i в другой компоненте.
Если мы будем проходиться по вершинам компоненты меньшего размера (точнее, не большего), каждая вершина будет затронута такими обходами не более чем log_2(n) раз. Ведь после каждого обхода размер компоненты связности увеличивается хотя бы в два раза. Так как std::set::lower_bound работает за O(log n), то все решение работает за O(n log^2 n).
Что дальше
Мы обязательно расскажем, когда состоится третий чемпионат — и будем ждать вас в качестве участников и гостей. А пока напомню, что True Tech — это не только чемпионат. Мы проводим митапы — например, для ИТ-архитекторов — True Tech Arch, начинающих специалистов и лидеров ИТ-индустрии — True Tech Hub, хакатоны для разработчиков True Tech Hack. В пилотном режиме запустили подкаст True Tech Talks. А в начале лета пройдет масштабная конференция True Tech Day, которую смотрят 87+ тысяч человек по всему миру.
Чтобы узнавать о новостях первыми, присоединяйтесь к сообществу True Tech в Telegram и ВКонтакте. Оставайтесь на связи и до встречи!