Как я в пятых тренировках по алгоритмам от Яндекса участвовала
Вводные
- Менеджерско-техническое высшее образование с 3 семестрами не очень глубокой высшей математики, из которых я уже практически ничего не помню;
- Годичный курс «Python-разработчик с нуля» от Нетологии;
- Участие в контестах – 1 шт. (контест на стажировку в Контур, март 2023 г., 5 задач без особого успеха, но все равно помогло, как – см. ниже);
- Знания об алгоритмах – книга «Грокаем алгоритмы» Адитья Бхаргава;
- Хорошая соображалка, повышенные дотошность и занудство.
Объявление о тренировках я увидела на канале 29 февраля и решила поучаствовать, т.к. за последний год почти ничем из программирования не занималась и хотелось заставить мозги поработать.
Призы Яндексом заявлены следующие:
- сертификат для решивших минимум половину задач (20 из 40);
- для топ-200 участников персональные тренировки по алгоритмам в мини-группах и после них возможность пройти пробное алгоритмическое собеседование в Яндекс. Если оно будет успешно, его засчитают вместо обычного собеседования на стажировку, если не получится – не будет штрафа как при обычном собесе (на полгода, если не ошибаюсь), плюс дадут обратную связь.
Так как я совсем не маэстро олимпиадного программирования, я поставила перед собой реалистичную цель – сертификат, который я потом с гордостью буду показывать маме)
Первый контест
Тренировки начались с лекции о сложности алгоритмов, тестировании решений и пограничных случаях, которые обязательно будут протестированы системой и на которых, как правило, и отсекаются многие неправильные решения. Так как с оценкой сложности алгоритмов я уже была знакома, особо ничего нового с этой лекции для себя не вынесла.
После лекции открылся первый контест, состоящий из 10 задач разного уровня сложности. В помощь участникам был создан телеграм-бот, у которого можно было запросить входные данные проваленного теста, и даже ответ на него, но не слишком часто: один тест раз в пол часа, ответ не раньше, чем через 10 минут после получения тестовых вводных данных. Также еще с прошлых тренировок есть чат в телеграме, где можно было пообщаться, подхватить идею и попросить совета, но, разумеется, публикация решений была запрещена. За чатом было очень интересно следить, а ходе тренировок он обрастал местячковыми мемами, несколько из которых я покажу.
Еще в чате я наткнулась на своего знакомого по хобби, не связанному с программированием. Возможность изредка спросить совет или просто пингануть на предмет «сколько решил» прилично поднимала боевой дух, хоть он и пишет на другом языке (Go), то есть прямо конкретные детали реализации мы обсуждать не могли, да и не хотели. Все-таки это соревнование с самим собой, только глупец захочет списать, тем самым, не получив от этого никакой пользы. Также в чате тренировок видела несколько человек и из нашего чата, с некоторыми даже общались немножко. Было бы интересно узнать об их успехах.
Семь из первого блока задач я решила достаточно легко с использованием практически только базовой математики и логики. Только лишь в одной из них реально пригодились базовые навыки работы с питоновской библиотекой datetime. Она прямо существенно облегчила жизнь, иначе мне бы пришлось вручную рассчитывать дни недели, а не выдергивать их из объектов datetime методом strftime('%A').
Еще одна задача была уже прилично сложнее. Я достаточно долго с ней ковырялась, пытаясь придумать какой-то толковый алгоритм решения. Но потом увидела в чате информацию, что даже на питоне временного ограничения хватает, чтобы ее забрутфорсить (решить перебором вариантов), и успешно этим воспользовалась. К слову все очень ждали разборной лекции, чтобы посмотреть, как было «правильно», но преподаватель ее тоже забрутфорсил. Его аргументом было: «Оценивайте имеющиеся у вас ресурсы. Если у вас хватает временного лимита и лимита по памяти пусть и на не очень красивое решение, то нет необходимости тратить огромное количество усилий для поиска «идеального» решения». Этот подход, по его словам, применим и для рабочих задач. Такие дела.
К слову у этой задачи было просто огромное количество тестов – 235. Их прогон занимал несколько минут. И большинство из нас как минимум несколько раз с замиранием сердца на протяжении этих минут следили, как растет счетчик выполненных тестов, а потом получали вердикт то TL (превышен лимит времени), то WA (неправильный ответ), то ML (превышен лимит памяти), то еще какую-нибудь ошибку. Ощущение очень так себе. Особенно когда на предыдущей попытке получил TL на 208 тесте, переделал, а теперь WA на 95-м. Сделала по этому поводу забавный скриншот из чата за авторством Валерия @Karkatyk
И две задачи мне не дались. Одна из них была связана с движением по окружности, я ее покрутила так и этак, но безрезультатно, тригонометрия уже давно мной забыта. Условие второй задачи в Ворде занимало 3 страницы, и, почитав ужаснувшийся чат, я, честно вам признаюсь, даже не стала читать задание. Хотя в ней вроде требовалось простое дотошное выполнение условий, с чем я бы скорее всего справилась, но уже прошла вторая лекция, и открылся второй контест, поэтому я предпочла синицу в руке начать решать второй контест, чем убиваться об эти две задачи с сомнительной перспективой их решить.
Второй контекст
Темой второй лекции был линейный поиск. Лекция была намного полезнее первой, с примерами задач, их решениями и подсказками разных трюков типа матрицы сдвигов или барьерного метода (ограждения матриц нулями, для облегчения работы с ними). Соответственно задачи были составлены так, что требовалось найти решение за линейное время. Решение со сложностью O(n^2) или O(nlogn) в Python уже не влезало бы в лимит времени.
Этот блок дался мне легче, чем предыдущий. Видимо поэтому смогла решить 10 из 10.
Во-первых, с двумя задачами я оказалась «знакома». Одна из них мне попалась год назад на контесте Контура. Нет, в смысле задача конечно была совершенно другая: в контуре мы косили газон, а в Яндексе выбирали как бы отсечь оппоненту выбор самых сильных персов в онлайн-игре, но их суть под капотом была один в один. Поэтому я, помня разбор задач из прошлого контеста, быстро с ней справилась. А вторая была на канале, хоть и с небольшим дополнением. Мы с вами покупали акции, а в Яндексе – рыбу, поэтому было ограничение по максимальному количеству дней между покупкой и продажей. Небольшая додумка и тоже готово.
Во-вторых, 4 задачи я решила так легко, что даже не вспомнила бы, о чем они, не подглянув в контест.
Из того, что посложнее, осталось 4 задачи. Три из них я решила с приложением разумного количества сил. Где-то помогала логика, где-то опять же было достаточно времени на брутфорс. Последнюю же я просто вымучила, по-другому не назовешь. Ну ни в какую, хотя другим, например, моему знакомому, она далась куда менее сложно.
Со вторым контестом связан локальный мем про улитку, которая была героем одной из задач. Ее нужно было в определенном порядке кормить ягодами, чтобы она поднялась максимально высоко по натянутой вверх веревке. Если вы спросите кого-то из решавших: какая ягода самая «особенная» в тесте № 16, большинство не задумываясь ответит вам, что двенадцатая. Потому что потому. Я тоже провела некоторое время в экселевской таблице с параметрами тысячи ягод в попытках разобраться, чего же такого особенного в двенадцатой. А вот еще впечатления от этой задачи за авторством Sbat(@Boboboshechka):
Третий контест
Третья лекция была посвящена словарям и множествам. Лектор немного рассказал о том, как эти структуры реализованы «под капотом», а также показал примеры решения некоторых задач.
С третьим блоком задач я тоже справилась успешно. На мой взгляд это был самый простой контест тренировок. В первое же утро я с наскока решила 6 задач. Две последние задачи требовали дотошного выполнения инструкций задания. Для такой зануды как я это было не сложно. И две задачи были по-настоящему сложные.
Первая из них про спички. Чат пестрил постами и даже мемами о том, что нужно искать решение за квадрат.
А также мемами, объединяющими несколько тем.
Мне повезло: две хорошие, подходящие идеи сразу пришли в голову. Иначе бы намучилась с ней, как большинство.
Зато я провозилась со второй сложной, где нужно было определить по множеству точек сколько нужно добавить, чтобы получился квадрат. Я написала на Python хорошее, правильное решение, но в тестовой системе Яндекса оно упиралось в лимит времени. Локально на самых объемных тестах я получала ответ за 1,8 секунды (лимит был 2) но в контесте я получала TL за TL. Раз за разом. Я оптимизировала все, что могла. Безуспешно. Мое отчаяние было настолько велико, что я решила сделать самый неожиданный ход.
Я переписала ее на языке программирования, который не знаю.
Мне нужен был компилируемый язык, но с функциональной парадигмой, чтобы не вникать в тонкости ООП в чуждом синтаксисе. Так что общество моего знакомого оказалось на руку: узнала от него, что Go прекрасно работает без ООП, и вперед: «Окей, chatGPT, перепиши мне этот код с питона на Golang». Плюс прочитала несколько статей с азами Go.
Без дебага, конечно, не обошлось. В моем решении было деление, и переписанный код вместо float записывал в переменные int и получал неправильный ответ на первых же тестах. Ох уж эта статическая типизация. Немного подшаманила код с помощью функции float32(), успешно прогнала на самых простых тестах, загнала в тестирующую систему и получила неверный ответ на 11 тесте. Почему? Решение же правильное, и визуально код на Go я внимательно проверила, он должен был вести себя ровно также как питоновский, который успешно справлялся с 11 тестом. Начала сравнивать ответы и заметила, что в ответах на Python и Go координаты точек наподобие (547 296 391, 239 601 902) отличаются на +- 2. Решение верное, но что-то не так с округлением. Тут пригодились статьи, которые я успела прочитать. Кроме типа данных float32 там же были float64 и вроде даже float128! «Надо повысить точность», - подумала я, заменила везде 32 и 64 и получила долгожданный «ОК».
Тут хочется бросить камень в огород Яндекса. Очень несправедливо, что на одном языке решение требуется оптимизировать до мелочей, и все равно есть риск не пройти, а на другом то же самое решение за данное время можно прогнать как минимум 5 раз. Говорят, на предыдущих тренировках для разных языков были разные лимиты. Поэтому не понятно, почему в этот раз сделали одинаковые.
Четвертый контест
Итак, окрыленная успехом второго и третьего контеста, я уже начала думать, что зря пропустила две задачи в первом, может с ними могла бы побороться за место в финале, но тут случились четвертая лекция и четвертый контест на тему «Бинарный поиск» с дополнением в виде тернарного поиска и префиксных сумм.
Я уже думала начать оправдываться тем, что на работе случился завал, что ребенок приболел и сама тоже, что устала решать задачи за 3 недели, но надо быть честной, в первую очередь с собой: я была не готова к задачам такого уровня сложности.
Судя по всему, т.к. 30 из 30 на первых трех контестах уже решили человек 300+, а призовые места планировались для топ-200, в заключительный контест собрали задачи повышенной сложности. Если в первых контестах я сходу решала 4-6 задач за несколько часов, то в этом в первый день я решила всего две. Потом за два дня осилила еще 3. Из них сходу я решила всего одну, остальные методом проб и ошибок. А потом все. Еще две я успела хотя бы попытаться, а потом случился дедлайн, который для последнего контеста оказался намного ближе, чем для остальных. Мне еще предстоит посмотреть разборную лекцию, чтобы понять, в какую сторону нужно было думать.
Дедлайна ждали всем чатом. Несколько участников сделали парсеры четырех лидербордов, поэтому можно было примерно отслеживать топ-200 и свое положение среди участников. С таким уровнем сложности четвертого контеста неожиданно выяснилось, что в топ-200 попадают не только «40 из 40», но и «39 из 40», поэтому у кого-то была очень напряженная пятница:
В 18:00 я поздравила всех с окончанием тренировок и напомнила, что не надо себя сравнивать с сыном маминой подруги, который два года «живет» на литкоде, а надо сравнивать с тем, кем ты был месяц назад. Все это не проходит зря, и каждый участник – молодец, даже те, кто не попал в топ-200 и не насобирал задач на сертификат. Решение таких задач – это навык, а не какая-то гениальность. И он тренируется: чем больше решаешь, тем чаще при прочтении новой задачи в голову будут приходить дельные мысли о том, как ее можно попробовать решить.
Итоги
Мой результат – 33 из 40. В местах по «неофициальным» лидербордам это ~ 480 место из около 4 тысяч участников. Есть и чем гордиться, и куда стремиться. Могла ли я решить больше? Думаю, да, но на это потребовалось бы больше времени. Всего я тратила на решение задач по 2-3 часа в будние дни, плюс бесконечные часы обдумывания. На выходных я не занималась задачами.
Стоит отметить, что мое состояние на протяжении этих четырех недель мне не очень понравилось. Конечно мало что сравнится со скачком дофамина от решенной сложной задачи, но большую часть времени я «витала в облаках» прокручивая в мозгу разные мысли по поводу решения задач. Даже перестала ходить на работе на предобеденную зарядку-разминку от вреда сидячей работы, предпочитая в это время обдумать или прогнать быстренько какие-то идеи. Так что зафиксировала у себя проблемы с невозможностью «переключить» голову при необходимости перехода на другой вид деятельности. С этим конечно надо работать, неделями в таком состоянии сложно находиться.
Все тренировки Яндекса по алгоритмам остаются доступны, можно смотреть лекции и решать задачи, просто без призовых мест. Кроме лекционных еще было два вебинара с алгоритмическими собеседованиями в прямом эфире, но к сожалению, я так их и не посмотрела из-за отсутствия времени.
Я перечислила темы, которые были в пятых тренировках, в предыдущих были другие. Поэтому, если интересуетесь алгоритмами, в каждой тренировке сможете найти что-то интересное.
Автор: Екатерина Михайлова