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

Автор оригинала: Andrei Margeloiu
  • Перевод
image

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

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

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

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

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

EDISON Software - web-development
Статья переведена при поддержке компании 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 часов. Почему? Потому что мне это нравилось. Каждый день возвращаясь домой из школы я шел прямо в спальню, садился за комп и начинал разбирать новую проблему. Или изучал новый алгоритм, который нужно было знать для решения этой проблемы.

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

image

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

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

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

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


image

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

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


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

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

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


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

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

image

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

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

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


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

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

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

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

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

Об авторе

image
Andrei Margeloiu — заядлый программист, интересующийся предпринимательством, стартапами и природой. Вы можете связаться с ним на LinkedIn.

Перевод: Диана Шеремьёва
Edison
452,48
Изобретаем успех: софт и стартапы
Поделиться публикацией

Комментарии 10

  • НЛО прилетело и опубликовало эту надпись здесь
      –1
      Java — медленный язык программирования. У него есть класс Big Integer, однако он не особо вам поможет. Если на конкурсе есть ограничение по времени, с Java вы его наверняка превысите. Java принимают не на всех соревнованиях.

      заявление абсурдное даже для 2009, не говоря уже про 2019. вопрос тут кто как меряет скорость, без прогрева это не имеет смысла
        +2
        без прогрева это не имеет смысла
        Какой, к бесу, прогрев? На олимпиадах на прогон программы на заданных определённых данных выделяется фиксированное время. Обычно несколько секунд. Соответственно в случае с Java — вы тупо тратите значительную часть выделенного лимита на запуск Java-машины. Даже python быстрее, зачастую, будет.

        И почему так — достаточно понятно. Это — соревнование. Для прогона у организаторов есть определённое количество компьютеров и запустить нужно определённое количество поданных решений. Делим одно на другое — получаем сколько секунд достаётся каждой программе.

        Всё просто и логично… а если кому-то хочется писать на языке, требующем «прогрева»… так это его и только его проблемы…
          –4
          просто кто-то не умеет тестировать программы, вот и всё.
          а если кому-то хочется писать на языке, требующем «прогрева»… так это его и только его проблемы…

          это вообще ноукоментс
            0
            Ещё раз. Речь идёт о соревнованиях. По определённым правилам. Ну вот как бобслей какой-нибудь. Кто-то умеет хорошо разгоняться, а кто-то — быстро проходить повороты. Но важно — общее время прохождения дистанции.

            И если какая-то фирма выпускает боб без ручек, так что он может только под собственным весом ускоряться — то он будет среди отстающих. Даже если он великолепно проходит повороты.

            И это не «вы не умеете тестировать программы», а «кто-то не умеет в логику».

            Нет никакого закона, требующего вам предоставлять только условия, которые вам нравятся. Вот если принят дизайн, который при нехватке памяти принудительно программы закрывает — то медлительность запуска Java-программ становится бедой. Вас никогда не удивляло, что iPhone отзывчивее Android'а и это пытаются компенсировать вдвое-втрое большей памятью? Это — прямое следствие того, что Java требует «прогрева».

            На серверах же — это не так страшно, там программы с выполнения хотя и могут «сниматься», но некий пул их всё равно сохраняется, так что проблем с «прогревом» не возникает.

            Да, для соревнований — Java медленная. И вы ничего, ну вот ровно ничего с этим не сможете поделать. По крайней мере в ближайшем будущем. Потому что C++ занимается оптимизацией один раз, а Java — 10, а то и 100 (сколько раз тесты запускают). И чтобы получить сравнимую скорость Java должна не просто достигать сравнимых скоростей, но обгонять (и сильно обгонять!) С++, чтобы компенсировать медленный старт.
              –1
              ну я к тому, что java один из самых распространённых языков программирования и уже можно научиться запускать тесты не через «time java ...»
                +1
                Это не тест продакшн кода, это соревнование.
                Ваша задача решить задачу в ограниченное время и память.
                Соревнование идёт автоматически, код не ревьюится.
                Было бы не честно давать прогревочные круги для джавы просто потому что она джава — я бы запросто закешировал результат и получил бы отличные баллы на любой задаче.

                И обычно на соревнованиях уделяется внимание запуску тестов, они запускаются несколько раз и выбирается лучший/медианный результат чтобы убрать задержки от тестового окружения, диска итд.
                  0
                  не обязательно давать ей все тесты, можно греть и на тех что в условиях задачи указаны. опять, я к тому что язык популярный и сделать элементарный прогрев на такая уж и технически сложная задача, по этому для меня загадка почему этим не хотят заниматься.
                    +1
                    Потому что организовать прогрев несложно. Но тогда вы уже даёте фору Java-программистам — причём весьма нехилую.

                    Во многих задачах можно было бы написать на C++ вообще программу которая работает нуль времени рассчитав, через constexpr-функции огромные таблицы и сделав так, чтобы программа компилировалась часа два.

                    Это невозможно, так как время на компиляцию ограничивается тоже. Как это сделать, чтобы то же самое не сделали Java-программисты во время «прогрева» — науке неведомо.

                    Да, наверное можно сделать модификацию JVM, которая бы запоминала бы код, но выкидывала данные… но это немедленно упрётся в вопрос о настоящем шотландце, так как с учётом знания структуры современных JVM есть способы перенести «знание» из данных в кеши JVM… в общем было принято простое и разумное решение: если вы выбираете для решения задачи язык, который нужно прогревать или просто язык, который в 100 медленнее C++ (скажем Python) — то это ваши проблемы.

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

                    При этом это может быть отличный агрегат, он может на разогретых шинах уделывать вообще всех… но вот конкретно в данных соревнования — он будет отставать…
        0
        Java — медленный язык программирования. У него есть класс Big Integer, однако он не особо вам поможет. Если на конкурсе есть ограничение по времени, с Java вы его наверняка превысите. Java принимают не на всех соревнованиях.

        Какой-то странный наезд. Тот же Петр Митричев на Codeforces в основном только Java и использует, и как-то не скажешь, что это ему сильно мешает. И с C# там кто-то был в топе когда-то. И вообще, довольно редко именно скорость выполнения программы становится узким горлышком, скорее неоптимальное решение. Тогда с С++ может подфартить и вы впишетесь в лимит в ремени с чуть большей долей вероятности.

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

        Самое читаемое