🥇Как я выиграл 3 из 4 золотых медалей на Computing Olympiad

Я готовился к Финалу чемпионата мира Google HashCode 2017. Это крупнейший конкурс с алгоритмическими задачами, организованный Google.

Я начал изучать C ++ с нуля в девятом классе. Я ничего не знал о программировании, алгоритмах и структурах данных. В какой-то момент я написал свою первую строчку кода. Семь месяцев спустя на горизонте замаячила олимпиада по программированию. Я захотел узнать насколько хорошо работал мой стиль изучения программирования. Это была идеальная возможность.

После двухдневных соревнований пришли результаты: я выиграл золотую медаль.

Я был в шоке. Я опередил конкурентов с 5-летним опытом. Я знал, что много работал, но это достижение превзошло все мои ожидания. Я понял, что спортивное программирование это моя тема и ушел в нее с головой.

Я знаю, что привело меня к успеху и хочу поделиться этим с вами.

Статья переведена при поддержке компании EDISON Software, которая заботится о здоровье программистов и их завтраке, а также разрабатывает программное обеспечение на заказ.

Какой язык программирования выбрать

C++ — Настоятельно рекомендую! Он очень быстрый. Реализация алгоритмов занимает мало времени из-за STL. C ++ принимают во всех соревнованиях. Свою первую строчку кода я написал на C++.
C — изучайте C++ из-за STL. Если вы знаете C, вы также сможете программировать на C++.
Java — медленный язык программирования. У него есть класс Big Integer, однако он не особо вам поможет. Если на конкурсе есть ограничение по времени, с Java вы его наверняка превысите. Java принимают не на всех соревнованиях.

Где вы можете практиковаться

Я рекомендую Sphere Online Judge (SPOJ). Это эффективный ресурс с точки зрения количества и качества. Редакторы и решения доступны онлайн, если вы застряли в процессе решения проблем. Помимо этого сайта рекомендую SPOJ Toolkit и классификатор проблем для SPOJ.pl.

Во-первых, нужно отточить знание основ

После того, как вы привыкнете к синтаксису языка, придется решить некоторые проблемы. Начните с простых проблем, которые требуют практики. На этом этапе главное определить свой стиль программирования. Может быть, вам нравится писать код с большим количеством пробелов, а может и нет. Возможно, вы ставите скобки в одной строке с «if», а может ставите их на отдельных строках.

Вы должны найти свой стиль программирования, потому что это ВАШ стиль.

Когда будете искать его, не забывайте два основных принципа:

Ваш код должен легко реализовываться. Вы должны чувствовать себя комфортно при реализации решения, которое вы придумали. Почему? Потому что во время соревнования последнее, чего вы хотите, это потеряться в своем коде. Всегда лучше лишние 5 минут подумать о том как упростить реализацию кода, чем тратить 10 минут на то, чтобы в ней разобраться.
Ваш код должен легко читаться. Когда код легко читать, его легко отлаживать. Давайте смотреть правде в глаза — ошибки появляются постоянно. Знаете то самое чувство, когда до конца осталось 10 минут и вы не можете найти чертову ошибку? Конечно, знаете. Чтобы избежать этой ситуации, пишите разборчивый код. Когда вы начнете его отлаживать, код будет казаться естественным и простым для понимания.

Вот пример моего стиля программирования.

Как повысить ваши навыки разработки

Практика, практика и еще раз практика. Я рекомендую вам проработать первые 250 самых решаемых задач на SPOJ. Решайте их по порядку. Потратьте на обдумывание решения каждой из них хотя бы час.

Не говорите: «Эта проблема для меня слишком сложная, я попробую решить следующую». Так мыслят неудачники.

Возьмите лист бумаги и карандаш. Подумайте. Может вам удастся найти решение, а может и нет. Как минимум вы разовьете алгоритмическое мышление. Если вы не сможете придумать решение в течение часа, поищите готовое решение на форуме или в статьях.

Чего вы добьетесь с таким подходом? Научитесь быстро реализовывать свои идеи с помощью кода. И изучите классические задачи и алгоритмы.

Во-вторых, вы должны освоить алгоритмы и структуры данных

Следуйте иерархическому подходу. Вы начинали бегать, не умея ходить? Нет. Можете ли вы построить небоскреб без прочного фундамента? Снова нет.

Вы не можете игнорировать этапы на пути обучения. Если вы будете их игнорировать, у вас останутся пробелы в знаниях. C течением времени они лишь усугубятся.

Начните с фундаментальных алгоритмов и структур данных

Начать трудно. Возможно, потому что вы не знаете, что изучать в первую очередь. Поэтому я создал видео-курс «Алгоритмы и структуры данных». Создавая этот курс, я опирался на то, как хотел бы, чтобы меня учили. Реакция была невероятной! Более 3000 студентов из более чем 100 стран записались на курс в первый же месяц.

Если вы будете работать над решением легких проблем, вы никогда не станете лучше.

Самый эффективный способ разобраться в том, чего вы не знаете, это столкнуться с этим на практике. Так учился я. Я выучил много новых техник, о которых никогда раньше не слышал, выбрав сложную задачу.

Каждая третья проблема, над решением которой вы работаете, должна учить вас чему-то новому. Отнеситесь к выбору проблем тщательней. Выбирайте проблемы посложнее!

После того, как вы закончите эти 250 задач от SPOJ, у вас появится общее понимание основных тем спортивного программирования. Благодаря глубокому пониманию логики, лежащей в основе базовых алгоритмов, алгоритмы высокого уровня покажутся не такими сложными. Таким образом, вы можете использовать свои знания по максимуму.

Копните глубже каждую из основных тем

Вот ценный ресурс с большим количеством информации. Там вы найдете топ 10 алгоритмов и структур данных по каждой теме. После 250 проблем от SPOJ вы будете знать многое из этого списка. Но также наткнетесь на многое, о чем еще никогда не слышали. Поэтому начните изучать эти темы в порядке возрастания.

Если вы не укрепите свои знания после того, как выучите что-то новое, вы быстро все забудете.
Я рекомендую после того, как вы изучите новый алгоритм, использовать его на практике. Проработайте его на 2-3 задачах. Поищите тег алгоритма в SPOJ. Там вы найдете проблемы, для решения которых нужен этот алгоритм. Разберите эти проблемы в первую очередь.

Разберитесь с динамическим программированием, потому что оно приведет вас к победе
Исходя из моего опыта, в каждом конкурсе есть как минимум одна проблема динамического программирования. У многих людей начинает болеть голова, когда они слышат словосочетание “динамическое программирование”, потому что они его совсем не понимают.

И это хорошо. Потому что если вы разбираетесь в динамическом программировании, то вы победите.

Мне нравится динамическое программирование, это моя любимая тема. Секрет динамического программирования в том, чтобы делать глобально оптимальный выбор, а не только локальный. Вы должны разбить проблему на более простые подзадачи. Решите каждую из этих подзадач только один раз. Затем создайте решение, объединяющее решенные подзадачи. Жадный алгоритм — противоположность динамического программирования. В нем нужно делать локально оптимальный выбор на каждом шаге. А локально оптимальный выбор может привести к плохому глобальному решению.

Изучая новые концепции, ознакомьтесь с туториалами TopCoder. Они очень подробные и понятные. Благодаря им я смог понять двоичные индексированные деревья.

Работайте усердно

Вы когда-нибудь слышали о спортсменах, которые выигрывают Олимпиаду без многолетней практики? Я нет.

Каждый год подготовка к компьютерной олимпиаде начиналась в сентябре и заканчивалась в апреле.

Каждый день в течение этих 8 месяцев я практиковался по 5 часов.

И да, я тратил эти 5 часов лишь на решение алгоритмических задач. Я помню дни, когда я практиковался по 8 и даже по 10 часов. Почему? Потому что мне это нравилось. Каждый день возвращаясь домой из школы я шел прямо в спальню, садился за комп и начинал разбирать новую проблему. Или изучал новый алгоритм, который нужно было знать для решения этой проблемы.

Если вы хотите победить, вы должны делать то же самое. Выберите проблему и придерживайтесь ее. Думайте о ней, идя по дороге в супермаркет или будучи за рулем.

Знаете ли вы, что во время сна ваш мозг дефрагментирует информацию, собранную в этот день? Он будто бы складывает книги в алфавитном порядке на книжной полке. По сути, ваш мозг думает о различных проблемах, с которыми вы столкнулись.

Этим можно умело пользоваться. Перед сном прочитайте трудную проблему и запомните, что нужно для ее решения. На этом этапе вам не нужно искать само решение. Ложитесь спать. Ваш мозг начнет обрабатывать эту проблему. Когда вы проснетесь, вы удивитесь, осознав, что нашли решение пока спали.

Попробуйте сами. Это похоже на магию.

Я создал видеоблог

Этот короткий абзац не связан со спортивным программированием. Если вам за двадцать, и вам интересно, как я вижу мир, то вы можете посмотреть мой видеоблог на Youtube. Я говорю в нем о мире, жизни и информатике.

Работайте с умом

Это секрет успеха. Вам нужны цели.

Мы люди, и нам нравится прокрастинировать. Нам всегда хочется отложить то, что нужно сделать прямо сейчас. Смотреть Netflix всегда приятнее, чем разбираться с проблемами динамического программирования. Вы это знаете, и вам нужно это исправить.

Как победить прокрастинацию

Ставьте себе цели. Вы всегда найдете интересные проблемы, из которых вы сможете узнать что-то новое (проверьте ресурсы, которые я упоминал выше). Но эти проблемы нужно решать, а не просто читать о них.

Итак, вот как я преодолел прокрастинацию. Я завел бумажный календарь и заполнил каждый день проблемами, которые хотел решать. Я всегда заполнял проблемы заранее, на два дня раньше. Поэтому я знал, как распоряжаться своим временем в последующие дни.

Таким образом, у меня всегда была мотивация. Мне нужно было решить одни проблемы и найти новые, чтобы заполнить следующие дни в календаре. Вычеркивать решенные проблемы очень приятно. Я знаю, что вам это тоже нравится.

Заведите свой собственный бумажный календарь. Не создавайте на своем телефоне еще один список дел, о котором вы завтра же забудете.

Как эффективно дебажить

Хотите стать профессионалом? Если да, то вам нужно “дебажить в уме”.
Это, безусловно, самая эффективная техника отладки, которую я знаю, потому что она вообще не требует отладчика. Ваш мозг исследует несколько веток кода одновременно и дает вам гораздо более широкий обзор кода по сравнению с классическим отладчиком.

Вы можете сравнить себя с гроссмейстером, который играет в шахматы и думает на 3 хода вперед.

Я использую эту технику исключительно в качестве своей начальной линии защиты. Затем я использую настоящий отладчик.

Чтобы научиться «дебажить в уме», нужно практиковаться. Когда вы утверждаете решение проблемы и получаете «неправильный ответ», не переходите сразу к кнопке отладчика. Перечитайте код и подумайте: «Что происходит в этой строке?», «Как здесь “if” влияет на программу?», «Когда мы выходим из цикла, каково значение итератора?».

Таким образом, вы думаете самостоятельно. Со временем вы научитесь писать код и дебажить его на ходу.