Как да се подготвим за конкурентно програмиране?

Така спечелих 3 от 4 златни медала в Олимпиадата по изчислителна техника.

По-късно редактиране: Допуснах се до световните финали на Google HashCode 2017, най-голямото алгоритмично състезание, организирано от Google.

Започнах да уча C ++ от нулата през първата ми година на Highschool. Не знаех нищо за програмиране, алгоритми или структури от данни. Седем месеца след като написах първия си ред код, компютърната олимпиада почука на вратата. И беше идеалният момент да видя дали стилът ми на обучение струва 5 цента.

След 2 дни състезание дойдоха резултатите: Спечелих златния медал.

Бях шокиран, защото бях надминал конкурентите с 5-годишен опит. Знаех, че съм работил усилено, но това постижение надхвърли очакванията ми. Състезанието по програмиране ме съвпадна перфектно и аз влязох ол-ин в тази област.

Знам какво ми донесе успех и искам да споделя това с вас.

Какъв език да изберете?

  1. C ++ - Силно препоръчително! Много е бързо Реализацията на различни алгоритми отнема малко време поради STL. C ++ се приема във всички състезания. Използвам го от първия си ред код.
  2. C - Отидете и научете C ++ заради STL. Ако имате знания за C, вие сте готови да кодирате и в C ++.
  3. JAVA - бавно е Но той има клас Big Integer, дори ако има много малко проблеми, които изискват използването му. Ако ограничението е ограничено, ще надвишите ограничението на времето. Java не се приема във всички състезания.

Къде можете да практикувате?

Препоръчвам Sphere Online Judge (SPOJ). Той е ефективен по отношение на качество и количество. Препоръките и решенията са достъпни онлайн, ако се забиете, докато решавате проблеми. Поддържащи уебсайтове Инструментариум за SPOJ и класификатор на проблеми за SPOJ.pl.

Първо, трябва да овладеете основите.

След като свикнете със синтаксиса на езика, е време да решите някои проблеми. Започнете с прости, които изискват умения за прилагане. На този етап целта ви е да определите стила си на кодиране. Може би обичате да пишете с много интервали, може би не. Може би поставете скобите на същия ред с израза „ако“, може и не.

Трябва да намерите своя стил на кодиране, защото е ваш.

И имайте предвид тези два принципа, докато развивате своя стил на кодиране.

  • Лесен за изпълнение. Трябва да се чувствате удобно да прилагате решението, което сте предложили. Защо? Защото по време на състезанието последното нещо, което искате да се случи, е да се изгубите в кода си. Винаги е по-добре да помислите още 5 минути за прилагането, отколкото да отделяте още 10 минути за това.
  • Лесен за четене. Това означава „Лесно за отстраняване на грешки“. Да си признаем, и двамата знаем, че бъгове се появяват непрекъснато. Знаете ли това усещане, когато ви остават 10 минути и не намерите този шибан бъг? Да, нали. За да решите, трябва да напишете четлив код. Така че, когато започнете да отстранявате грешки, кодът ще се почувства естествен и прост за следване.

Ето моят стил на кодиране.

Как да повишите уменията си за внедряване?

Практика, практика и повече практика. Препоръчвам ви да работите първия 250 най-решен проблем на SPOJ. Решете ги в точния ред. И помислете за решението поне един час.

Не казвайте „Този ​​проблем е твърде тежък за мен, ще опитам следващия“. Това е губещият манталитет

Вземете лист хартия и молив и се опитайте да мислите. По този начин вероятно ще намерите решението, но със сигурност ще развиете алгоритмично мислене. Ако не намерите решението за един час, можете да разгледате форума или редакциите, за да видите решението.

Резултатите от този подход? Бързо изпълнение. И учене на класически проблеми и алгоритми.

Второ, трябва да овладеете алгоритми и структури от данни.

Следвайте йерархичен подход. Започнахте ли да бягате, без да знаете как да ходите? Не. Можете ли да построите небостъргач без здрава основа? Отново не.

Това означава, че не можете да записвате стъпки в учебния си път. Или ако го направите, ще останете с пропуските в знанието, които ще се задълбочават с течение на времето.

Започнете с основните алгоритми и структури от данни.

Трудно е да започнеш Вероятно защото първо не знаете какво да научите. Ето защо създадох видео курс за алгоритми и структури за данни. Проведох този курс по начина, по който бих искал да съм научен. Отговорът беше невероятен, през първия месец 3000+ студенти от 100+ страни се присъединиха.

Ако работите с лесни проблеми, никога няма да станете по-добри.

Най-ефективният начин да намерите това, което не знаете, е всъщност да се сблъскате с него. Това се случи с мен. Научих много нови техники, за които никога не бях чувал, преди да избера труден проблем.

От всеки 3 проблема, които решавате, човек трябва да ви научи на нещо ново. Ако не, изберете ги по-внимателно. Изберете по-трудни проблеми!

След като завършите тези 250 проблема от SPOJ, ще имате преглед на основните теми на конкурентното програмиране. Чрез дълбоко разбиране на логиката зад основните алгоритми, алгоритмите на високо ниво ще изглеждат лесно разбираеми. Така че можете бързо да използвате вашите знания.

Сега копайте по-дълбоко във всяка основна тема.

Ето огромен ресурс с Топ 10 алгоритми и структури от данни във всяка тема. След тези 250 проблема от SPOJ, вие ще знаете много от този списък. Но все още има много, за които никога не сте чували. Затова започнете да ги изучавате във възходящ ред.

Ако не укрепите знанията си, след като научите нещо ново, ще го забравите.

Препоръчвам ви, след като научите нов алгоритъм, за да практикувате 2–3 проблеми с него. Търсете маркера на алгоритъма в SPOJ и ще намерите проблеми, които го изискват. Работете ги преди всичко друго.

Разберете динамичното програмиране, защото това ще ви накара да спечелите.

От моя опит във всеки конкурс има поне един проблем с динамичното програмиране. Много хора получават главоболие, когато чуят DP, защото не го разбират.

И това е хубаво нещо Защото ако наистина разбираш DP, ще спечелиш.

Харесвам DP, това е любимата ми тема. И тук е тайната на DP: мислите оптимално в световен мащаб, а не само на местно ниво. Трябва да разбиете проблема на по-прости подпроблеми, като решавате всяка от тях само веднъж и изграждате решението, комбиниращо тези решени подпроблеми. Обратното на DP е алчен алгоритъм, защото последният избира локално оптималния избор на всяка стъпка. И локално оптималният избор може да доведе до лошо глобално решение.

Когато изучавате нови концепции, проверете уроците за TopCoder. Те са много подробни и лесни за следване. Наистина разбрах бинарните индексирани дървета оттам.

Работи здраво.

Чували ли сте някога за спортисти, които печелят олимпиадата без години практика? Не съм

Всяка година подготовката за компютърната олимпиада започва през септември и приключва през април.

Всеки един ден в тези 8 месеца тренирах по 5 часа.

И да, прекарах тези 5 часа само за решаване на алгоритмични проблеми. Спомням си дни, когато прекарах дори 8 или 10 часа да тренирам. Защо? Защото бях страстен за това. Всеки ден след като се прибрах от училище, отидох направо в спалнята си и започнах да решавам нов проблем. Или да научите нов алгоритъм, необходим за този проблем.

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

Знаете ли, че докато спите, мозъкът ви дефрагментира информацията, събрана в този ден? Това е като поставянето на книгите по азбучен ред на рафт за книги. По принцип мозъкът ви мисли за различни проблеми, които сте срещали.

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

Опитайте сами. Усеща се като магия.

Започнах Vlog

Този кратък параграф не е свързан с конкурентното програмиране. Просто исках да ви уведомя, че ако сте на 20-те си години и ви е интересно как виждам света, аз правя влог на Youtube. Говоря за света, живота и компютърните науки.

Работете умно.

Това е тайната на успеха. Имате нужда от цели.

Ние сме хора и обичаме да прокрастираме. Това означава да отложите нещата, които трябва да направите сега. Винаги е по-удобно да гледате Netflix, а не да работите с DP проблеми. Знаете това и трябва да поправите това.

Как можеш да победиш отлагането?

Като приемаме цели. Винаги ще намерите интересни проблеми, откъдето можете да научите нещо ново (проверете ресурсите, които ви дадох по-горе). Но тези проблеми трябва да бъдат решени, а не само да се четат.

Ето как преодолях отлагането. Направих хартиен календар и го попълних с проблеми, които исках да решавам всеки ден. И винаги съм изпълвал два дни предварително с проблеми, така че знаех как да управлявам времето си в следващите дни.

По този начин винаги бях мотивиран да завърша проблемите и да намеря нови, които да запълня календара в следващите дни. Отговорно чувство е да режеш проблемите, когато ги решаваш. Знам, че и ти харесваш това.

Направете свой собствен хартиен календар. Не правете друг контролен списък на телефона си, за който утре няма да ви пука.

Как да отстранявате грешки ефективно?

Искате ли да станете професионалист? Ако е така, трябва да „отстраните грешки в ума си“.

Това е най-ефективната техника за отстраняване на грешки, която познавам, тъй като тя изобщо не изисква отстраняване на грешки. Мозъкът ви изследва множество кодови пътища едновременно и ви дава много по-широка перспектива на кода, в сравнение с класическия отладчик.

Тя е подобна на способността на гросмайсторите да играят шах и да мислят 3 движения предварително.

Използвам тази техника изключително като моята първоначална линия на защита, последвана от използване на действителна грешка в последната инстанция.

За да се научите да „отстранявате грешки в ума си“, трябва да практикувате. Когато изпратите проблем и получите „Грешен отговор“, не отидете направо към бутона за отстраняване на грешки. Вместо това започнете да четете кода и помислете „Какво се случва на този ред?“, „Как това изявление„ ако “засяга програмата?“, „Когато излезе от цикъла, каква е стойността на итератора?“.

По този начин мислите сами. С течение на времето ще започнете да отстранявате грешки в реално време, докато пишете кода.

Смятате ли, че тази публикация е полезна? Моля, докоснете бутона ❤ по-долу! :)

За автора

Андрей Маргелой е страстен програмист, който се интересува от предприемачество, стартъпи и природа. Можете да се свържете с него в LinkedIn.