Я готувався до Фіналу чемпіонату світу Google HashCode 2017. Це найбільший конкурс із алгоритмічними завданнями, організований Google.
Я почав вивчати C++ з нуля у дев'ятому класі. Я нічого не знав про програмування, алгоритми та структури даних. Якоїсь миті я написав свій перший рядок коду. Через сім місяців на горизонті замаячила олімпіада з програмування. Я захотів дізнатися, наскільки добре працював мій стиль вивчення програмування. Це була ідеальна нагода.
Після дводенних змагань дійшли результати: я виграв золоту медаль.
Я був у шоці. Я випередив конкурентів із 5-річним досвідом. Я знав, що багато працював, але це досягнення перевершило всі мої очікування. Я зрозумів, що спортивне програмування – це моя тема і пішов у неї з головою.
Я знаю, що призвело до успіху і хочу поділитися цим з вами.
Статтю перекладено за підтримки компанії EDISON Software, яка , а також .
Яку мову програмування вибрати
- C++ - Настійно рекомендую! Він дуже швидкий. Реалізація алгоритмів займає мало часу через STL. C++ приймають у всіх змаганнях. Свою першу строчку коду я написав на C++.
- C – вивчайте C++ через STL. Якщо ви знаєте C, ви також можете програмувати на C++.
- Java – повільна мова програмування. Він має клас Big Integer, проте він не особливо вам допоможе. Якщо на конкурсі є обмеження часу, з Java ви його напевно перевищите. Java приймають не на всіх змаганнях.
Де ви можете практикуватись
Я рекомендую . Це ефективний ресурс з погляду кількості та якості. Редактори та рішення доступні онлайн, якщо ви застрягли у процесі вирішення проблем. Крім цього сайту рекомендую и .
По-перше, потрібно відточити знання основ
Після того, як ви звикнете до синтаксису мови, доведеться вирішити деякі проблеми. Почніть із простих проблем, які вимагають практики. На цьому етапі найголовніше визначити свій стиль програмування. Можливо, вам подобається писати код із великою кількістю прогалин, а може й ні. Можливо, ви ставите дужки в одному рядку з if, а може ставите їх на окремих рядках.
Ви повинні знайти свій стиль програмування, тому що це ваш стиль.
Коли будете шукати його, не забувайте два основних принципи:
- Ваш код має легко реалізовуватися. Ви повинні почуватися комфортно під час реалізації рішення, яке ви придумали. Чому? Тому що під час змагання останнє, чого ви хочете, це загубитися у своєму коді. Завжди краще зайві 5 хвилин подумати про те, як спростити реалізацію коду, ніж витрачати 10 хвилин на те, щоб у ній розібратися.
- Ваш код має легко читатись. Коли код легко читати, його легко налагоджувати. Давайте дивитися правді у вічі — помилки з'являються постійно. Знаєте те саме почуття, коли до кінця залишилося 10 хвилин і ви не можете знайти бісову помилку? Звісно, знаєте. Щоб уникнути цієї ситуації, пишіть розбірливий код. Коли ви почнете його налагоджувати, код буде природним і простим для розуміння.
стиль програмування.
Як підвищити ваші навички розробки
Практика, практика та ще раз практика. Я рекомендую вам опрацювати перші 250 найрозв'язніших завдань на . Вирішуйте їх по порядку. Витратьте на обмірковування рішення кожної їх хоча б годину.
Не кажіть: «Ця проблема для мене є надто складною, я спробую вирішити наступну». Так мислять невдахи.
Візьміть аркуш паперу та олівець. Подумайте. Може, вам вдасться знайти рішення, а може й ні. Як мінімум ви розвинете алгоритмічне мислення. Якщо ви не зможете вигадати рішення протягом години, пошукайте готове рішення на форумі або у статтях.
Чого ви досягнете з таким підходом? Навчіться швидко реалізовувати свої ідеї за допомогою коду. І вивчіть класичні завдання та алгоритми.
По-друге, ви повинні освоїти алгоритми та структури даних
Дотримуйтесь ієрархічного підходу. Ви починали бігати, не вміючи ходити? Ні. Чи можете ви побудувати хмарочос без міцного фундаменту? Знову ні.
Ви не можете ігнорувати етапи по дорозі навчання. Якщо ви їх ігноруватимете, у вас залишаться прогалини у знаннях. З часом вони лише посиляться.
Почніть із фундаментальних алгоритмів та структур даних
Почати важко. Можливо, тому, що ви не знаєте, що вивчати в першу чергу. Тому . Створюючи цей курс, я спирався на те, як хотів би, щоб мене вчили. Реакція була неймовірною! Понад 3000 студентів із понад 100 країн записалися на курс у перший же місяць.
Якщо ви працюватимете над вирішенням легких проблем, ви ніколи не станете краще.
Найефективніший спосіб розібратися в тому, чого ви не знаєте, це зіткнутися із цим на практиці. Так я вчився. Я вивчив багато нових технік, про які ніколи раніше не чув, вибравши складне завдання.
Кожна третя проблема, над вирішенням якої ви працюєте, має вчити вас чогось нового. Поставтеся до вибору проблем ретельніше. Вибирайте проблеми складніше!
Після того, як ви закінчите ці 250 завдань від SPOJ, у вас з'явиться загальне розуміння основних тем спортивного програмування. Завдяки глибокому розумінню логіки, що лежить в основі базових алгоритмів, алгоритми високого рівня здаються не такими складними. Таким чином, ви можете використати свої знання по максимуму.
Копніть глибше кожну з основних тем
з великою кількістю інформації. Там ви знайдете топ 10 алгоритмів та структур даних з кожної теми. Після 250 проблем від SPOJ ви знатимете багато з цього списку. Але також натрапите на багато чого, про що ще ніколи не чули. Тому почніть вивчати ці теми у порядку зростання.
Якщо ви не зміцните свої знання після того, як вивчите щось нове, ви швидко все забудете.
Я рекомендую після того, як ви вивчите новий алгоритм, використовувати його на практиці. Пропрацюйте його на 2-3 задачах. Пошукайте тег алгоритму SPOJ. Там ви знайдете проблеми, для вирішення яких потрібний цей алгоритм. Розберіть ці проблеми насамперед.
Розберіться з динамічним програмуванням, тому що воно приведе вас до перемоги
Виходячи з мого досвіду, у кожному конкурсі є як мінімум одна проблема . У багатьох людей починає боліти голова, коли вони чують словосполучення "динамічний програмування", тому що вони його зовсім не розуміють.
І це добре. Тому що якщо ви розумієтеся на динамічному програмуванні, то ви переможете.
Мені подобається динамічне програмування, це моя улюблена тема. Секрет динамічного програмування полягає в тому, щоб робити глобально оптимальний вибір, а не лише локальний. Ви повинні розбити проблему на простіші підзавдання. Вирішіть кожну з цих подзадач лише один раз. Потім створіть рішення, що поєднує вирішені підзавдання. - Протилежність динамічного програмування. У ньому потрібно робити локально оптимальний вибір на кожному кроці. А локально оптимальний вибір може призвести до поганого глобального рішення.
Вивчаючи нові концепції, ознайомтеся з . Вони дуже докладні та зрозумілі. Завдяки їм я зміг зрозуміти .
працюйте старанно
Ви колись чули про спортсменів, які виграють Олімпіаду без багаторічної практики? Я ні.
Щороку підготовка до комп'ютерної олімпіади розпочиналася у вересні та закінчувалася у квітні.
Щодня протягом 8 місяців я практикувався по 5 годин.
І так, я витрачав ці 5 годин лише на вирішення алгоритмічних завдань. Я пам'ятаю дні, коли я практикувався по 8 і навіть по 10 годин. Чому? Бо це мені подобалося. Щодня повертаючись додому зі школи я йшов прямо до спальні, сідав за комп'ютер і починав розбирати нову проблему. Або вивчав новий алгоритм, який треба було знати на вирішення цієї проблеми.
Якщо ви хочете перемогти, ви повинні робити те саме. Виберіть проблему та дотримуйтесь її. Думайте про неї, йдучи дорогою до супермаркету або будучи за кермом.
Чи знаєте ви, що під час сну ваш мозок дефрагментує інформацію, зібрану цього дня? Він ніби складає книги в алфавітному порядку на книжковій полиці. По суті, ваш мозок думає про різні проблеми, з якими ви зіткнулися.
Цим можна вміло скористатися. Перед сном прочитайте важку проблему та запам'ятайте, що потрібно для її вирішення. На цьому етапі вам не потрібно шукати саме рішення. Лягайте спати. Ваш мозок почне обробляти цю проблему. Коли ви прокинетеся, ви здивуєтеся, усвідомивши, що знайшли рішення поки що спали.
Спробуйте самі. Це схоже на магію.
Я створив відеоблог
Цей короткий абзац не пов'язаний із спортивним програмуванням. Якщо вам за двадцять, і вам цікаво, як я бачу світ, ви можете подивитися . Я говорю в ньому про мир, життя та інформатику.
Працюйте з розумом
Це секрет успіху. Вам потрібні цілі.
Ми люди, і нам подобається . Нам завжди хочеться відкласти те, що потрібно зробити зараз. Дивитися Netflix завжди приємніше, ніж розуміти проблеми динамічного програмування. Ви знаєте, і вам потрібно це виправити.
Як перемогти прокрастинацію
Ставте цілі. Ви завжди знайдете цікаві проблеми, з яких ви зможете дізнатися про щось нове (перевірте ресурси, які я згадував вище). Але ці проблеми слід вирішувати, а не просто читати про них.
Отже, ось як я подолав прокрастинацію. Я завів паперовий календар і щодня заповнив проблемами, які хотів вирішувати. Я завжди заповнював проблеми наперед, на два дні раніше. Тому я знав, як розпоряджатися своїм часом у наступні дні.
Таким чином, я завжди мала мотивацію. Мені потрібно було вирішити одні проблеми та знайти нові, щоб заповнити наступні дні у календарі. Викреслювати вирішені проблеми дуже приємно. Я знаю, що вам це також подобається.
Введіть свій власний паперовий календар. Не створюйте на своєму телефоні ще один список справ, про який ви завтра ж забудете.
Як ефективно дебатувати
Бажаєте стати професіоналом? Якщо так, то вам потрібно "бешкетувати в умі".
Це, безумовно, найефективніша техніка налагодження, яку я знаю, бо вона взагалі не потребує налагодження. Ваш мозок досліджує кілька гілок коду одночасно і дає вам набагато ширший огляд коду в порівнянні з .
Ви можете порівняти себе з гросмейстером, який грає в шахи і думає на 3 ходи вперед.
Я використовую цю техніку виключно як свою початкову лінію захисту. Потім я використовую справжній наладчик.
Щоб навчитися «бешкетувати в умі», потрібно практикуватися. Коли ви затверджуєте вирішення проблеми та отримуєте «неправильну відповідь», не переходьте одразу до кнопки відладчика. Перечитайте код і подумайте: "Що відбувається в цьому рядку?", "Як тут "if" впливає на програму?", "Коли ми виходимо з циклу, яке значення ітератора?".
Таким чином, ви думаєте самостійно. Згодом ви навчитеся писати код і бешкетувати його на ходу.
Про автора
Andrei Margeloiu — затятий програміст, який цікавиться підприємництвом, стартапами та природою. Ви можете зв'язатися з ним .
Переклад: Діана Шерем'єва
Джерело: habr.com