Привет, Хабр! Меня зовут Алина Ёжикова, я работаю в МТС Диджитал и делаю мероприятия для разработчиков. Сегодня расскажу, как мы организовали самый большой и сложный ивент в моей карьере — олимпиаду по программированию на восемь тысяч разработчиков.
Я говорю про True Tech Champ — всероссийскую олимпиаду по программированию для студентов, школьников и опытных IT-специалистов. В треке для школьников и студентов нужно было решить алгоритмические задачи и описать метод их решения на любом удобном языке программирования (чаще всего участники выбирали C++).
В этом посте мы познакомимся с нашими победителями и разберем вместе с ними задачи, которые привели их на призовые места.
Мы очень хотели собрать на одной площадке самых сильных ребят-олимпиадников: студентов, школьников. К ним присоединились и уже состоявшиеся специалисты.
«В школьном треке такие монстры алгоритмических задач участвуют, что туда лучше даже не соваться»
— сказал мне победитель трека для взрослых Дима, когда я собирала фидбэк от участников. Я вспомнила Дашу — пятнадцатилетнюю школьницу, серебряного призёра школьного трека, и согласилась.
В онлайне мы провели отборы и полуфинал, а финал сделали очным. Посмотреть на финал в МТС Live Hall приехало около 1000 гостей: 250 финалистов и 750 гостей. 10 000 человек наблюдали за программой онлайн. 12 победителей, 10 миллионов рублей призового фонда на всех, и целый день напряжённого кодинга.
Весь день на площадке проходили митапы, мастер-классы и воркшопы. Эксперты рассказывали про будущее искусственного интеллекта, использование ML-платформ, технологии Big Data и другие направления и инструменты. В развлекательной зоне можно было поиграть в аэрохоккей, кикер, игровые консоли, VR-клуб, набить тату и посоревноваться в кодинге.
Фотографии с True Tech Champ
Оглавление по историям наших победителей:
Монстры алгоритмических задач: почему школьники и студенты участвуют в олимпиадах
Ладно, шутки шутками, а призовое место на олимпиаде — это хороший шанс получить место в вузе или стажировку в крупной компании. Как именно? Это лучше расскажут сами ребята.
Даша, 15 лет. Второе место в треке «Школьники и студенты»
Как всё начиналось
Я участвую в олимпиадах по программированию и математике с 5 класса. Меня тогда родители перевели в физмат школу. Пришла в школьный кружок по информатике, пробовала написать «змейку» на паскале, анимировать квадратики. Через полгода попала на свою первую олимпиаду и завертелось. Сейчас я регулярно проверяю — куда можно записаться, что предлагают. О каких-то олимпиадах узнаю от друзей или в кружке, о чём-то пишут в каналах и чатах.
На True Tech Champ попала почти случайно — увидела где-то в сети рекламу. Туда много моих знакомых пришло. Например, даже один из преподавателей моего кружка по алгоритмическому программированию — Иван. Мы участвовали в одном треке, он занял первое место — единственный из всех решил задачку про крестики-нолики.
Я вообще не рассчитывала на призовое место: знала, что очень много сильных знакомых зарегистрировалось.
Про жизнь олимпиадника
Олимпиадная жизнь требует довольно много времени. 5 часов в неделю на кружок. Если готовлюсь к чему-то важному, то эти 5 часов в неделю превращаются в 7-8 часов в день. Я после такой подготовки к Всероссийской олимпиаде в себя приходила почти месяц. Ещё дистанционные туры, тренировки с командой и самостоятельно. А хочется ещё и погулять с друзьями, поиграть во что-нибудь — «Цивилизация» или платформер какой-нибудь, посмотреть аниме. Ещё на досуге учу японский сама. Но менталитет японцев мне не близок — они постоянно перерабатывают, не уверена, что я бы смогла с ними сойтись.
Немного об этике и «перечневых» олимпиадах
Внутри нашего сообщества не принято, если ты сильный участник, писать простые «перечневые» олимпиады (то есть, входящие в Перечень олимпиад школьников, который обновляется каждый учебный год). Их нужно оставить ребятам, которым это нужно просто для поступления в вуз. Два года назад победой во Всероссийской олимпиаде я себе уже обеспечила место в университете. Правда, пока не решила до конца, в каком именно.
О будущем
«Думать поменьше в работе — это не звучит как что-то интересное»
Я пока не знаю, чем именно хочу заниматься. Не уверена даже, что буду сдавать информатику. Если мне в школе скажут, что мне надо для экзамена каждый день ходить на дополнительные занятия и решать по варианту экзаменационных заданий, возможно, откажусь.
Как-то из интереса с друзьями командой зарегистрировались на олимпиаду по кибербезу в формате Capture The Flag.
Смысл в том, чтобы находить какие-то уязвимости — флаги — в коде сайта, приложения. Например, в случае с сайтом это могут быть проблемы с авторизацией. Создатели что-то не учли, и можно было войти в чужой аккаунт. Задача олимпиадника — понять, как это сделать. Иногда задача — просто текстовый файлик, в котором какой-то шифр.
Мы тогда посмотрели курс от авторов олимпиады и даже заняли одно из призовых мест.
Я думаю теперь, что посмотрю углублённый курс по информационной безопасности. Если смогу как-то поместить в своё расписание.
О сложных и простых задачах
У меня не очень хорошо выходят задачи, которые называют «нетóчками». В чём смысл, если кратко: в обычных задачах просят найти какое-то идеальное решение. При решении «неточек» нужно найти наилучший вариант из возможных. Заранее определена некоторая метрика качества, и решение с бóльшим значением по этой метрике — лучшее. С такими задачами я не очень хорошо справляюсь.
Я просила моих друзей, которые лучше решают «неточки» тренировать меня на известных им задачах. Не скажу, что стало идеально. Но теперь я понимаю, какие основные методы стоит применять при решении.
Например, метод отжига — сперва находим случайное решение и понемногу меняем его. И после каждого изменения останавливаем алгоритм и смотрим, стало лучше или хуже.
Но зато у меня хорошо получаются задачи на комбинаторику, графы и деревья.
Самая простая задача на МТС True Tech Champ
Задача A. Автоматическое исправление
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 1024 мегабайта
Это задача с двойным запуском
...Начало 2000-х. Мобильная связь начинает появляться не только в крупных городах, но и вдоль отдельных трасс. Так как покрытие далеко не идеально, а технологии были на невысоком уровне, то при передаче информации могли случаться сбои.
При отправке SMS-сообщений у жителей посёлка N происходили следующие эффекты: время от времени произвольная буква в тексте сообщения могла замениться на следующую по циклу с сохранением капитализации (то есть буква или остаётся неизменной, или заменяется следующей по алфавиту; если буква в алфавите последняя, она заменяется первой).
Например, текст mts мог придти как mts, или как nts, или как mus, или как mtt, или даже как nut.
Ваша задача — написать программу, которая позволяет исправить эти ошибки, то есть в режиме передачи получает исходное сообщение, передаёт некоторый текст, а в режиме получения сообщения получает отправленный текст с возможными искажениями и восстанавливает переданное сообщение.
Передаваемое сообщение состоит из не более, чем 160 строчных латинских букв. Протокол сети поддерживает передачу строк, состоящих из не более, чем 160 строчных и заглавных латинских букв (то есть передаваемое в режиме передачи сообщение должно удовлетворять этим ограничениям).
Формат входных данных
Первая строка входных данных содержит одну строку — «send», если нужно передать сообщение, и «receive», если нужно принять сообщение.
В случае передачи сообщения вторая строка содержит одно слово, составленное из строчных латинских букв. Длина слова не менее 1 и не более 160.
В случае приёма сообщения вторая строка содержит одно слово, составленное из строчных или заглавных латинских букв. Длина сообщения не менее 1 и не более 160 символов. Сообщение отличается от отправленного в режиме «send» только возможными искажениями, описанными в условии задачи.
Формат выходных данных
В режиме передачи выведите одну строку, состоящую из строчных и заглавных латинских букв и имеющую длину от 1 до 160.
В режиме приёма выведите одну строку — сообщение, которое вам надо было передать.
Ваше решение будет запущено на каждом тесте два раза — сначала в режиме передачи, затем в режиме приёма. Если в итоге принятое сообщение (выход второго запуска) будет отличаться от переданного (вход первого запуска), или же промежуточная строка не будет удовлетворять ограничениям, решение на данном тесте будет признано неверным
Примеры
стандартный ввод | стандартный вывод |
send mts | TrueTechChamp |
receive TsueTechDhbmp | mts |
Решение
В этой задаче программу запускают дважды.
В первом запуске ей даётся строка из строчных латинских букв. Программа в ответ тоже должна выдать строку, но некоторые буквы в ней могут быть заглавными.
Во втором запуске программе дают строку, которую она вывела в первый раз, но с возможными изменениями. Например, каждую букву строки могли заменить на следующую по алфавиту с сохранением регистра.
Программе надо вывести строку, которую она получила во время в первого запуска. Я решала задачу так: если у буквы нечётный номер в алфавите, сделаем её заглавной, иначе оставим строчной. Тогда, если во второй запуск программы размер буквы не соответствует ее чётности, то мы знаем, что ее заменили и можем вернуть обратно.
Самая интересная задача на МТС True Tech Champ
Задача B. Базовая станция
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 1024 мегабайта
Это — интерактивная задача
Во время испытания одной из базовых станций сети 6G произошёл сбой — зона передачи внезапно из окружности радиуса 1 стала правильным n-угольником, вписанным в окружность радиуса 1 с центром в точке (0, 0) и одной из вершин в точке (0, 1).
Вы находитесь около базовой станции — в точке (0, 0). Ваша задача — определить минимально возможное значение n.
У вас есть 6 дронов. Дрон может быть запущен в некотором направлении, пролететь по прямой до момента потери связи со станцией, после чего дрон падает и разбивается. В случае потери связи с дроном у вас на пульте управления выводится целая часть расстояния, которое было преодолено до потери связи.
Ваша задача — определить минимально возможное значение n.
Протокол взаимодействия
Взаимодействие начинает ваша программа. Вы отправляете дрон в полёт. Для этого задаёте направление — целое число градусов u от 0 до 359 (например, 0 соответствует положительному направлению оси x, 90 — положительному направлению оси y) в формате ? u. В ответ программа жюри возвращает 0 или 1 — целую часть длины пути, который преодолел дрон в заданном направлении до момента исчезновения связи.
Если вы готовы вывести ответ, используйте команду ! n, где n > 3 — минимально возможное количество вершин многоугольника n.
«Минимально возможное» расшифровывается следующим образом: если существует несколько значений n таких, что результаты всех возможных запусков дронов при этих значениях n полностью совпадают, выведите наименьшее возможное такое n.
Пример
стандартный ввод | стандартный вывод |
0 1 0 | ? 33 ? 14 ? 133 ! 180 |
Замечание
Не забывайте после каждого запроса ответа или вывода результата выводить перевод строки и очищать буфер ввода-вывода вызовом функции flush выбранного вами языка программирования.
Решение
Целая часть пройденного расстояния равна 1, если дрон пролетает через вершину, и 0 во всех остальных случаях.
Так как вершины правильного n-угольника имеют полярный угол k · 360/n (0 ≤ k < n), то
наличие вершины при повороте на X градусов обозначает, что для какого-то k k · 360/n = x. Если X и k не взаимно просты, то, разделив X и k на их наибольший общий делитель, получаем, что существует меньшее целое x, для которого поворот на x градусов приводит к попаданию в вершину и при этом (k, x) = 1, то есть 360 делится на x.
Тогда и все направления с углами вида ax, где a — целое число, также содержат вершины. Поэтому достаточно проверить все углы, являющиеся делителями 360, чтобы получить информацию, эквивалентную всем 360 запросам.
Так как 360 = 23 · 32· 5, то можно сделать 6 запросов: проверка угла 180 (кратность n двум), проверка угла 90 (кратность n четырём), проверка угла 45 (кратность n восьми), проверка угла 120 (кратность n трём), проверка угла 40 (кратность n девяти), проверка угла 72 (кратность n пяти), после чего получить максимальный делитель 360, на который делится n. Можно сэкономить один запрос: проверяем угол 90, если в этом направлении ответ 1, проверяем 45, а если нет — проверяем 180. Так находим d = НОД (n, 360) за 5 запросов. Если d ≤ 2, то многоугольника с n вершинами не существует, соответственно, надо найти минимальное n, для которого (n, 360) = d, это 7 и 14 для d = 1 и d = 2 соответственно. Если d > 2, то минимальное n, удовлетворяющее условиям задачи, равно d.
Иван, 22 года. Первое место в треке «Школьники и студенты», студент, инженер в компании-производителе электроники
На очном финале True Tech Champ со мной постоянно здоровались знакомые участники. Я регулярно участвую в олимпиадах и веду несколько кружков по алгоритмическому программированию.
Даша — серебряный призёр этого же трека — некоторое время занималась в моём кружке. Да-да, всегда двое их — учитель и ученик (на деле, конечно, намного больше, да и я на Дарта Сидиуса не тяну).
Я профессиональный олимпиадник. Как начал в 8 классе, так до сих пор регулярно и участвую. Правда, на студенческих треках этот год для меня последний: заканчиваю магистратуру. Дальше планирую приходить уже на чемпионаты и хакатоны для специалистов. На True Tech Champ попал, увидев рекламу. Ещё в пользу олимпиады сыграло то, что у меня не было возможности заниматься дополнительной подготовкой к мероприятию, а тут это не было нужно.
Олимпиады и приглашения на стажировки
Сами результаты олимпиад мне никогда не помогали получить стажировку — обычно я сам записывался куда-то, проходил отборы. Чаще на собеседованиях играли роль мои навыки в алгоритмах.
Потому что когда людей набирают на какие-то младшие позиции, их проверяют, тестируют на умение решать алгоритмические задачи. А с этим у меня проблем нет.
На нынешнее рабочее место тоже попал, фактически, сам.
Победителей олимпиад моя компания приглашала на свою конференцию как зрителей. После неё у меня остались контакты рекрутера, я и написал.
Как алгоритмические задачи помогают в работе
Сейчас я оптимизирую для своей компании алгоритм поиска ближайших соседей. Нет, я имею в виду не тех людей, которые в соседней квартире живут (и сверлят что-то в 8 утра в субботу).
«Ближайшие соседи» — это ближайшие точки из множества. Этот алгоритм используется во многих программах, в которых нужно искать похожие объекты и сравнивать с базой заранее известных объектов.
Моя компания продает этот алгоритм разным компаниям, которые интегрируют его в свои сервисы. Например, одни из наших клиентов используют «ближайших соседей» в системе распознавания лиц. В этом случае алгоритм работает в связке с методами машинного обучения. Лица детектируются и сопоставляются с некоторой базой людей.
Согласитесь, похоже отчасти на олимпиадные задачки?
Про сообщество олимпиадников
Наш мир достаточно тесен. Есть, например, одна из самых популярных платформ по олимпиадному спортивному программированию в онлайне, CodeForces. На ней, наверное, у любого человека, который ходит на олимпиады, есть свой аккаунт. Многих знаешь даже без личного знакомства — имя, никнейм, какие-то общие данные.
И на очных этапах эти никнеймы вдруг становятся реальными людьми. Не скажу, что я близко дружу со всеми «коллегами по цеху» и много общаюсь с кем-то вне олимпиад. Обычно всё ограничивается командой и теми, с кем, например, учишься вместе.
Но знание сообщества отчасти помогает — я вижу имена тех, кто прошёл на олимпиаду и могу прикинуть свои шансы на победу. Например, я знал, что на True Tech Champ будут очень сильные ребята и победу просто так никто не отдаст.
Как я чуть не проиграл и почему ошибки полезны
В самом начале соревнования я растерялся и очень многие меня обошли. Ошибся в программах, замедлился. Потом понял, что если последнюю задачу не решу, то всё, это провал. И выбора, в общем-то, не оставалось: надо собраться и вернуть себе лидерскую позицию.
Такие моменты я считаю интересными и полезными для себя. Потому что это хорошо, когда получается заметить свои слабые места и проанализировать ошибки, которые можно будет не допускать в следующих соревнованиях. На True Tech Champ удалось и победить, и свои слабые места выявить.
Крестики-нолики и первое место на МТС True Tech Champ
Задача F. Если отсутствует связь...
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 1024 мегабайта
Это — задача с двойным запуском. Первый запуск является интерактивным
Вы решили принять участие в открытом чемпионате МТС по интеллектуальным играм. Сегодня ваша команда играет в две игры — крестики-нолики и пентамино.
Крестики-нолики проходят на доске 3×3 по классическим правилам. Вы играете одну или более партий против гроссмейстера. Вы всегда играете крестиками и ходите первым. Гроссмейстер играет оптимально (то есть при вашей оптимальной игре партия, как известно, закончится вничью, при вашей ошибке компьютер постарается выиграть), из различных оптимальных вариантов он может выбрать любой.
Финальные позиции всех сыгранных партий публикуются на сайте чемпионата.
Вы сами можете выбрать количество партий, однако гроссмейстер слишком занят, чтобы играть против одного участника более, чем 21 партию.
Задачу с пентамино будут решать оставшиеся члены вашей команды.
Вы же, как капитан, получили входное задание — непустой набор попарно различных пентамино. Напоминаем, что пентамино — это фигура из пяти клеток на клетчатой бумаге, обладающая следующим свойством: между любыми двумя клетками пентамино можно пройти по клеткам пентамино, перемещаясь только в клетки, которые имеют общую сторону с текущей. В этой задаче два пентамино считаются равными, только если они совмещаются параллельным переносом. То есть если даже одно пентамино получено из другого поворотом или отражением, такие пентамино считаются разными. Однако за минуту до начала игры в крестики-нолики вы осознали, что забыли отправить задание сокомандникам.
А средства связи уже отключены... И единственная информация, которую ваши сокомандники могут от вас получить — это финальные позиции ваших игр против гроссмейстера, опубликованных на сайте чемпионата. Таким образом, Вам требуется передать выданный вам набор попарно различных пентамино за предстоящую 21 партию.
При первом (интерактивном) запуске ваша программа получает на вход количество пентамино, а также сами фигуры, заданные в стандартном формате. После чего ваша программа выбирает количество партий (от 1 до 21), которые она должна сыграть. Далее запускаются партии в крестики-нолики. Если Ваша программа проиграет хотя бы раз или нарушит правила (например, сходит на занятую клетку) — вы получаете вердикт Wrong Answer.
Если все партии заканчиваются вничью, то финальные позиции всех сыгранных партий будут переданы вашей программе при её втором (неинтерактивном) запуске в том порядке, в котором партии были сыграны. Ваша программа должна вывести тот же набор пентамино, который был передан на вход программе при первом запуске. Порядок фигур в наборе значения не имеет. Если ваша программа выведет фигуру, которой не было в исходном наборе, или не выведет какую-то фигуру, которая была в исходном наборе, или выведет какую-то фигуру дважды, решение будет признано неверным.
Протокол взаимодействия
Взаимодействие при первом запуске начинает программа жюри.
В первой строке программа жюри выводит сообщение encode. Во второй — одно целое число K: количество пентамино в наборе. Гарантируется, что число является положительным и что каждое пентамино встретится в наборе не более одного раза (то есть что никакие два пентамино в наборе не переводятся друг в друга параллельным переносом).
Далее следуют K описаний пентамино.
Описание одного пентамино имеет следующий формат:
• Первая строка описания содержит два целых числа r и c (1 ≤ r, c ≤ 5) — количество строк и столбцов в минимальном прямоугольнике пентамино. Минимальный прямоугольник для некоторого пентамино определяется как прямоугольник, в каждой строке и в каждом столбце которого есть как минимум одна клетка, принадлежащая данному пентамино.
• Далее следуют r строк, каждая из которых содержит c символов. Символ равен ., если соответствующая клетка прямоугольника свободна, и *, если она занята элементом пентамино.
Гарантируется, что всего ровно 5 клеток содержат * и что фигура, образованная звёздочками, является связной в описанном в условии смысле.
После вывода описаний пентамино Ваша программа выводит одно целое число n (1 ≤ n ≤ 21) — количество партий в крестики-нолики. После чего играется n партий. Формат взаимодействия во время партии:
Поля имеют следующую нумерацию:
abc
3...3
2...2
1...1
abc
То есть левое нижнее поле имеет номер a1, правое нижнее — c1, поле в середине — b2 и так далее.
В каждой партии вы делаете первый ход.
Ход заключается в указании через пробел номера позиции, в которую ставится крестик, то есть, например «a 1». Если позиция уже занята или некорректна (на доске нет такого поля), Ваше решение получает сообщение об ошибке. В ответ компьютер выводит ход гроссмейстера в аналогичном формате. Если вы проигрываете, ваше решение получает сообщение об ошибке. В противном случае после вашего пятого хода доска оказывается полностью заполненной, фиксируется ничья, после чего начинается следующая партия (или взаимодействие успешно завершается, если уже сыграно n партий).
После вывода количества партий, а также после каждого хода не забывайте выводить символ перевода строки, а также сбрасывать буфер вывода с помощью вызова функции flush используемого языка программирования. В противном случае вы можете получить вердикт Wall Time Limit.
Формат входных данных
При втором (неинтерактивном) запуске первая строка содержит сообщение decode. Вторая строка содержит количество сыгранных партий n. Далее идут n блоков по 3 строки — финальные позиции партий в том порядке, в котором они были сыграны. Клетки, на которые делала ход ваша программа, обозначены символом x, клетки, на которые делал ход гроссмейстер, обозначены символом o. Гарантируется, что позиции соответствуют сыгранным партиям.
Формат выходных данных
Выведите описание набора пентамино в том же формате, в котором пентамино были заданы во время первого запуска. Порядок следования пентамино в наборе может быть произвольным.
Помните, что повёрнутые или отражённые пентамино в этой задаче считаются различными.
Решение
Конкретно в этой задаче показывалось некоторое множество фигур. Нужно было его посмотреть, потом выиграть или свести к ничьей несколько партий в крестики-нолики. Во втором запуске показывалась история игр и их результаты. И нужно было сказать, какое множество было загадано.
Решить её просто так на листочке не получится — пришлось пробовать несколько разных подходов, придумать и проверить гипотезы.
Но я быстро пришёл к правильной гипотезе.
Для начала сгенерируем все варианты пентамино. Это можно сделать двумя способами:
Вспомнить все 12 свободных пентамино и затем применить к ним вращение и отражение и сохранить получившиеся объекты в set,
Генеририровать пентамино рекурсивно и сохраняя их в set (при этом сразу сгенерируются варианты со всеми поворотами).
В обоих случаях есть смысл вместе с фигурой хранить размеры минимального прямоугольника с осями, параллельными осям координат, в который эта фигура вписана, а координаты клеток перевычислять относительно этого прямоугольника (чтобы избежать случаев, когда две фигуры отличаются только положением внутри прямоугольника с координатами). Получаем 63 варианта.
Надо закодировать 263 различных наборов 21-й партией в крестики-нолики. То есть одна партия должна кодировать три бита информации (то есть число от 0 до 7). Генерируем все заполнения поля 3 × 3 крестиками и ноликами, при которых число крестиков на единицу больше числа ноликов и никакие три одинаковых символа не образуют выигрышную позицию. Таких заполнений 16. В 8 из них в центре стоит крестик, ещё в 8 — нолик.
Можно показать, что если при первом ходе в угловую клетку компьютер не ставит нолик в центр, то крестики неизбежно выигрывают. Из оптимальности игры компьютера следует, что при ходе в угловую клетку первый ход компьютер сделает в центр.
Обозначим цифрами ходы крестиков, а буквами — ходы ноликов. При двух первых ходах крестиков 1 и 2 позиция автоматически приходит к следующей (с ходом ноликов):
B21
4AC
..3
В любом из двух вариантов окончания хотя бы одна из пары клеток, получающихся поворотом этой конструкции на 90 · n градусов из клеток b3, c3, будет занята ноликом. То есть по финальной позиции первые два хода определяются однозначно (единственная из этих пар, занятая двумя крестиками).
Так как всего существуют 4 поворота данной позиции, то всего мы можем так передать 4 варианта.
Пусть первый ход делается в центр. Ответ не в угловую клетку ведёт к проигрышу. Так что первый ход идёт в угловую клетку. После чего можно форсированно поставить ходы 2 и 3 (на них нолики вынуждены делать автоматические ответы), получив «уголок». Примеры ниже показывают, как получить любую из четырёх возможных его ориентаций. Понятно, что в случае ещё одной клетки, составляющей «уголок» с уже существующим, будет заполнена вертикаль или горизонталь, так что данный «уголок» однозначно идентифицируется.
.2A.
C13
.B.
.CA.
B12
.3.
B.A
31C
.42
.2A
31C
.B.
Так мы получили 4 варианта при первом ходе в угол (и занятом ноликами центре), и 4 варианта при первом ходе в центр, итого требуемые 8 вариантов. На уровне декодирования остаётся реализовать распознавание положения уголка или поворота пары клеток b2, b3, после чего принять 63 бита и сгенерировать набор уникальных пентамино одним из способов, указанных в начале.
Руслан, 24 года, второе место в треке «Специалисты», backend-разработчик. Первый блин — серебряной медалью
True Tech Champ для меня — первый опыт олимпиады. Я увидел рекламу, прикинул, что выходные свободны и подал заявку на участие. Ещё и призовой фонд выглядел заманчиво.
Как вирус привёл второклассника в разработку
Ещё второклассником я поймал свой первый вирус. Это был винлок. Я скачивал игру, и у меня заблокировался компьютер. Ну и попало же мне от родителей!
Потом мне стало интересно, что такое вирус и как он работает. Разобрался, написал свою первую вредоносную программу, и снова получил нагоняй от родителей. Но меня уже было не остановить: я понял, что в IT происходят какие-то интересные мне вещи.
В вуз не прошёл на информационную безопасность, попал на информатику и вычислительную технику. Года три хотел перевестись на инфобез, а потом я пообщался с ребятами, которые там учились. В итоге свою жизнь с информационной безопасностью связало 3 человека со всего курса. А остальные всё равно пошли в бэкенд-разработку. Я понял, что не так уж и плохо быть просто разработчиком.
Я вообще порой «не попадаю». Например, со стажировкой в той компании, где сейчас работаю, была долгая история. Там и ковид, и закрытие набора было. Устроился в другую компанию, тихо-мирно работал. Но потом мне позвонил HR первой компании и позвал к ним. И вот сейчас я здесь — пишу на C++ приложение для водителей.
Случайная победа
Я раньше не участвовал ни в каких олимпиадах и не мог в полной мере представить, что меня ждёт. Поэтому особо не готовился к отборочному. А к финалу не готовился уже потому, что знал: нужно масштабировать уже написанное решение.
На победу вообще не рассчитывал. На лидборде иногда я шёл пятым-шестым. Написал программу, понял, что лучше я её уже не сделаю. Собрался и поехал на работу. Спустя пару часов мне звонят координаторы: «А ты где?». Собственно, так и узнал о своём почётном серебре. Даже не сразу понял, что произошло: вскочил, начал собираться. Попутно рассказал коллеге о выигрыше.
На награждение я опоздал: приезжаю, а там на сцене группа выступает. Награду мне вручили уже на afterparty.
Что важно в работе
В моей команде (да и в смежных) много очень крутых ребят. Они примерно мои ровесники, но в некоторых вещах намного профессиональнее меня. Это одновременно и мотивация, и возможность получить помощь, когда она нужна. Я middle+, но постепенно расту. В том числе, благодаря примеру коллег. Смотрю на них и понимаю, что ещё из навыков мне нужно подтянуть. Собственно, я так компанию и команду выбирал: чтобы и задачи интересные, и простор для роста.
А зарплата, красивый офис — это всё хорошо, но не всегда решающий фактор.
А что решали взрослые?
Общая задача трека для специалистов
Условия
Эмулируется приложение, запущенное в облачной инфраструктуре на виртуальных машинах. Приложение использует базу данных, развернутую на отдельной виртуальной машине. Участники должны оптимизировать расходы на инфраструктуру с наименьшими простоями в работе приложения.
Описание работы эмуляции – участникам не известно. Все числа приведены для примера. Основной параметр, определяющий нагрузку на приложение – количество входящих запросов. Количество входящих запросов изменяется в течение дня от 0 до нескольких тысяч по определенному закону.
На обработку каждого запроса требуются ресурсы приложения и ресурсы базы данных.
Время обработки запроса складывается из времени обработки в приложении и времени выполнения запроса в БД.
При выполнении запроса больше 400ms он считается неуспешным.
Для работы приложения необходимо иметь как минимум одну виртуальную машину и одну виртуальную машину с базой данных.
Ресурсы приложения
Выполнение каждого запроса требует 0.001 CPU и 5Mb памяти
Время выполнения запроса – 50ms
Накладные расходы приложения на каждой виртуальной машине – 0.05 CPU, 300Mb памяти
Если суммарное количество требуемых ресурсов CPU превышает 95% от выделенных, то приложение перестает отвечать и уходит в офлайн
Если суммарное количество требуемых ресурсов памяти превышает 95% от выделенной, то приложение перестает отвечать и уходит в офлайн
Ресурсы БД
Выполнение каждого запроса требует 0.001 CPU и 30Mb памяти
Время выполнения запроса – 50ms
Накладные расходы ядра БД на каждой машине с БД – 0.05 CPU, 512Mb памяти
Если суммарное количество требуемых ресурсов CPU превышает 95% от выделенных, то приложение перестает отвечать и уходит в офлайн
Если суммарное количество требуемых ресурсов памяти превышает 95% от выделенной, то приложение перестает отвечать и уходит в офлайн
Общие принципы работы с виртуальными машинами
При изменении количества ресурсов виртуальной машины — виртуальная машина перестает работать на 3 минуты. Тарификация машины продолжается
При заказе новой виртуальной машины — она становится доступной через 5 минут. Но тарификация начинается с момента создания машины
Время ответа приложения
Время ответа приложения зависит от нагрузки на CPU для виртуальных машин и базы данных. Виртуальные машины и базы данных вносят разные задержки в обработку запроса. Если время ответа на запрос превышает 400ms, то приложение уходит в офлайн.
API
Запрос ресурсов возвращается список из:
тип ресурса - db/vm
стоимость ресурса (cost)
нагрузка на cpu
нагрузка на память
количество cpu
количество памяти
ID ресурса
состояние неработоспособности ресурса (failed) после заказа или изменения
Запрос цен возвращается список ценовых позиций из:
тип ресурса vm/db
стоимость ресурса
количество cpu
количество ram
ID позиции
Запрос текущей статистики возвращает текущую статистику по пользователю, запрос включает:
"availability": доступность сервиса по шкале 0…1. 1 означает работу сервиса 100% времени без пропущенных запросов
"cost_total": общие затраты накопительным итогом
"db_cpu": всего ЦПУ для баз данных
"db_cpu_load": текущая нагрузка на цпу базы данных
"db_ram": всего памяти для базы данных
"db_ram_load": текущая нагрузка на память базы данных
"last1": затраты за последнюю минуту
"last15": затраты за последние 15 минут
"last5": затраты за последние 5 минут
"lastDay": затраты за последний день
"lastHour": затраты за последний час
"lastWeek": затраты за последнюю неделю
"offline_time": общее время оффлайна
"online": признак работоспособности
"online_time": общее время онлайна
"requests": текущее количество запросов
"requests_total": общее количество запросов, поступившее к приложению
"response_time": время ответа приложения (должно быть меньше 400 для работоспособного приложения)
"vm_cpu": всего ЦПУ для виртуальных машин
"vm_cpu_load": нагрузка на ЦПУ для виртуальных машин
"vm_ram": всего памяти для виртуальных машин
"vm_ram_load": нагрузка на память для виртуальных машин
Все запросы к API (кроме получения списка цен) делаются с токеном пользователя.
Токен пользователя можно найти в правой части страницы, под доступами к gitlab.
Заказ/модификация ресурса возможны только в комбинациях CPU/RAM для которых есть соответствующая строка с ценами.
Ссылка на полную документацию API.
Оценка работы сервиса
Мы собираем 2 показателя, которые оценивают эффективность решения: количество затрачиваемых ресурсов и кол-во минут, которые «сервис» был офлайн.
Расчет со стороны API происходит каждую минуту: каждый «тик» времени сервис записывает в лидерборд кол-во потраченных за эту минуту «ресурсов» (число) и время, которое сервис был оффлайн (0 или 1). Лидерборд складывает эти данные и показывает итоговые числа по работе системы.
Для исключения разности результатов ввиду разного времени старта работы сервиса, итоговый лидерборд будет строиться отдельно. После завершения работы над решением (стоп-кодинг), мы отключим возможность обновлять алгоритмы, сбросим лидерборд и в течение 60 минут «засечем» работу всех решений с нуля. Таким образом, сформировав итоговый лидерборд по этапу, на основании которого и будут выявлены лидеры.
Решение
Для оптимизации затрат ресурсов и оптимизации времени работы сервиса был разработан следующий план:
Рассчитываем требуемые ресурсы CPU и RAM для обработки одного запроса и накладные ресурсы приложения на основе статистических данных.
Прогнозируем количество запросов, которые будут сделаны в следующий момент времени, используя алгоритмы для анализа временных рядов, такие как ARIMA, поскольку количество запросов подчиняется определенному закону.
После прогноза количества запросов анализируем, справляются ли текущие ресурсы приложения с нагрузкой. Если нет, необходимые ресурсы приобретаются, а если да, проверяется, есть ли возможность освободить избыточные ресурсы.
Рассмотрим каждый пункт подробнее:
1. Расчет требуемых ресурсов CPU и RAM для обработки одного запроса
Для каждого ресурса (VM CPU, VM RAM, DB CPU, DB RAM) вычисляются накладные расходы при помощи линейной алгебры. Необходимо решить следующую систему уравнений:
cpuCount(t1)=cpuOverhead+requestsCount(t1)∗cpuRequest
cpuCount(t2)=cpuOverhead+requestsCount(t2)∗cpuRequest
В этих уравнениях:
requestsCount(t1) и requestsCount(t2) обозначают количество запросов в моменты времени t1 и t2 соответственно.
cpuOverhead представляет собой накладные расходы CPU виртуальной машины.
cpuRequest представляет собой потребление CPU для одного запроса.
cpuCount(t1) и cpuCount(t2) обозначают общее количество CPU в моменты времени t1 и t2 соответственно.
Аналогичные формулы и для вычисления RAM.
Фрагмент кода, выполняющий расчеты:
data = (
(f_vm_cnt, s_vm_cnt, "vm_cpu", "vm_cpu_load",),
(f_vm_cnt, s_vm_cnt, "vm_ram", "vm_ram_load",),
(f_db_cnt, s_db_cnt, "db_cpu", "db_cpu_load",),
(f_db_cnt, s_db_cnt, "db_ram", "db_ram_load",),
)
for f_cnt, s_cnt, res, load in data:
m = np.array([[f_cnt, first_item.requests], [s_cnt, second_item.requests]])
v = np.array(
[
_cal_percent(getattr(first_item, res), getattr(first_item, load)),
_cal_percent(getattr(second_item, res), getattr(second_item, load)),
]
)
# https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html
over, request = np.linalg.solve(m, v)
result.append([over.item(), request.item()])2. Прогнозирование количества запросов
Для прогнозирования используется модель ARIMA. Прогноз делается на 5 минут вперед, так как время создания одного ресурса занимает 5 минут, а изменение — 3 минуты.
Фрагмент кода:
dates = [
item.timestamp
for item in list(self._stats_service.memory.values())[
-settings.train_size:
]
]
requests = [
item.requests
for item in list(self._stats_service.memory.values())[
-settings.train_size:
]
]
df = pd.DataFrame(list(zip(dates, requests)), columns=["date", "requests"])
df.set_index("date", inplace=True)
train = df["requests"]
model = auto_arima(
train, trace=False, error_action="ignore", suppress_warnings=True
)
model.fit(train)
# Прогноз делается на 5 минут вперед
result = model.predict(n_periods=5)
self.requests = [math.ceil(i) for i in list(result)]3. Расчет необходимых ресурсов
Для оптимизации затрат на ресурсы требуется решить задачу линейного программирования. Сделать это можно с помощью библиотеки PuLP. Мы стремимся к минимизации общих издержек на ресурсы, при условии выполнения требований к количеству CPU и RAM.
Фрагмент кода:
def choose_optimal_resources(
data: tp.List[models.Price],
requests: int,
request_cpu: float,
request_ram: float,
overhead_cpu: float,
overhead_ram: float,
):
# Создаем проблему линейного программирования
model = LpProblem("Minimize_Cost", LpMinimize)
# Создаем переменные для количества ВМ каждого типа
resource_types_cnt = len(data)
vm_vars = LpVariable.dicts(
"VM", range(resource_types_cnt), lowBound=0, cat="Integer"
)
# Целевая функция: минимизировать общую стоимость
model += lpSum(
vm_vars[i] * (data[i].cost - settings.penalty)
for i in range(resource_types_cnt)
)
# Условие 1: необходимое количество CPU
model += (
lpSum(
vm_vars[i] * (settings.pod_load_max_percent * data[i].cpu - overhead_cpu)
for i in range(resource_types_cnt)
)
>= requests * request_cpu
)
# Условие 2: необходимое количество RAM
model += (
lpSum(
vm_vars[i] * (settings.pod_load_max_percent * data[i].ram - overhead_ram)
for i in range(resource_types_cnt)
)
>= requests * request_ram
)
# Решаем проблему
model.solve(PULP_CBC_CMD(msg=False))
optimal = []
for i in range(resource_types_cnt):
num = int(value(vm_vars[i]))
if num > 0:
optimal.extend([data[i]] * num)
return optimalПолное решение можно найти здесь.
Вместо заключения
Под брендом True Tech мы проводим не только осеннюю олимпиаду, но и хакатон True Tech Hack и масштабную IT-конференцию True Tech Day. Сейчас на финишной прямой подготовка конференции — она пройдёт 17 мая. Будем вас ждать и надеемся подружиться, как и с героями этого текста. Зарегистрироваться можно по ссылке.
На True Tech Day вы сможете поделиться опытом и познакомиться с людьми внутри профессионального сообщества. Это прекрасная возможность узнать, что находится «под капотом» у самых технологически продвинутых и популярных цифровых продуктов рынка.
На конференции представлены пять направлений: Development, AI/ML, Cloud, Science и отдельный научный трек.
Поговорим об особенностях построения облачных платформ и обеспечении безопасности в облаке; разберемся, как происходит управление базами данных в крупных компаниях электронной коммерции; узнаем о новых подходах в языках программирования, применении ИИ в дизайне материалов и многом другом. А еще ты сможешь прокачать свои навыки в Event Storming и понять, как быстро и эффективно создавать «правильные» микросервисы.
Своими кейсами поделятся 50 представителей IT-индустрии. Среди спикеров: Олег Бондарь (Яндекс), Антон Степаненко (Ozon), Денис Кораблев (Positive Technologies), Илья Валяев (Авито), Максим Чудновский (СберТех). Эксперты от МТС — Павел Воронин, Михаил Федяев, Алексей Попов.
А в октябре приходите на второй True Tech Champ. С нетерпением ждём новых интересных участников, новых знакомств в ИТ-сообществе и интересных задач.
До встречи!