Ինչպես հաշվողական օլիմպիադայում նվաճեցի 3 ոսկե մեդալներից 4-ը

Ես պատրաստվում էի Google HashCode World Championship Finals 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-ի համար.

Նախ, դուք պետք է հղկեք ձեր գիտելիքները հիմունքների վերաբերյալ

Լեզվի շարահյուսությանը վարժվելուց հետո որոշ խնդիրներ կան, որոնք պետք է հաղթահարվեն: Սկսեք պարզ խնդիրներից, որոնք պրակտիկա են պահանջում: Այս փուլում գլխավորը ձեր ծրագրավորման ոճը որոշելն է։ Միգուցե ձեզ դուր է գալիս կոդ գրել շատ բացատներով, գուցե ոչ: Դուք կարող եք փակագծերը դնել նույն տողի վրա, ինչ «եթե», կամ կարող եք դրանք դնել առանձին տողերի վրա:

Դուք պետք է գտնեք ձեր ծրագրավորման ոճը, քանի որ դա ձեր ոճն է:

Երբ փնտրում եք այն, հիշեք երկու հիմնական սկզբունք.

• Ձեր կոդը պետք է հեշտ կիրառվի: Դուք պետք է հարմարավետ զգաք՝ իրականացնելով ձեր առաջարկած լուծումը: Ինչո՞ւ։ Որովհետև մրցույթի ժամանակ վերջին բանը, որ ուզում ես, քո ծածկագրի մեջ կորչելն է: Միշտ ավելի լավ է լրացուցիչ 5 րոպե ծախսել՝ մտածելով, թե ինչպես պարզեցնել կոդի իրականացումը, քան 10 րոպե ծախսել՝ փորձելով պարզել այն:
• Ձեր կոդը պետք է հեշտ ընթեռնելի լինի: Երբ կոդը հեշտ է կարդալ, հեշտ է վրիպազերծել: Եկեք խոստովանենք, որ սխալները միշտ լինում են: Գիտե՞ք այն զգացողությունը, երբ ձեզ մնում է 10 րոպե և չեք կարողանում գտնել անիծյալ սխալը: Իհարկե, դու անում ես: Այս իրավիճակից խուսափելու համար գրեք ընթեռնելի կոդ: Հենց որ սկսեք վրիպազերծել այն, կոդը բնական և հեշտ հասկանալի կթվա:

Ահա իմ օրինակը ծրագրավորման ոճ.

Ինչպես բարելավել ձեր զարգացման հմտությունները

Պրակտիկա, պրակտիկա և ավելի շատ պրակտիկա: Ես խորհուրդ եմ տալիս լուծել առաջին 250 ամենալուծվող խնդիրները ՍՊՈJ. Լուծեք դրանք հերթականությամբ: Առնվազն մեկ ժամ ծախսեք՝ մտածելով դրանցից յուրաքանչյուրի լուծման մասին։

Մի ասա. «Այս խնդիրը ինձ համար շատ դժվար է, ես կփորձեմ լուծել հաջորդը»: Այսպես են մտածում պարտվողները.

Վերցրեք մի կտոր թուղթ և մատիտ: Մտածիր այդ մասին. Գուցե դուք կարող եք լուծում գտնել, գուցե ոչ: Առնվազն դուք կզարգացնեք ալգորիթմական մտածողությունը: Եթե ​​մեկ ժամվա ընթացքում չեք կարողանում լուծում գտնել, ապա պատրաստի լուծում փնտրեք ֆորումում կամ հոդվածներում։

Ինչի՞ կհասնեք այս մոտեցմամբ։ Սովորեք արագ իրականացնել ձեր գաղափարները՝ օգտագործելով կոդը: Եվ ուսումնասիրեք դասական խնդիրներ և ալգորիթմներ:

Երկրորդ, դուք պետք է տիրապետեք ալգորիթմներին և տվյալների կառուցվածքներին

Հետևեք հիերարխիկ մոտեցմանը: Սկսե՞լ եք վազել՝ առանց քայլել իմանալու: Ոչ Կարո՞ղ եք երկնաքեր կառուցել առանց ամուր հիմքի: Էլի ոչ։

Դուք չեք կարող անտեսել ուսուցման ճանապարհին կատարվող քայլերը: Եթե ​​դուք անտեսեք դրանք, դուք կմնաք գիտելիքների բացեր: Ժամանակի ընթացքում դրանք միայն կվատթարանան։

Սկսեք հիմնարար ալգորիթմներից և տվյալների կառուցվածքներից

Դժվար է սկսել: Միգուցե այն պատճառով, որ դուք չգիտեք, թե ինչ սովորել առաջինը: Ահա թե ինչու Ես ստեղծել եմ «Ալգորիթմներ և տվյալների կառուցվածքներ» տեսադասընթաց. Այս դասընթացը ստեղծելիս ես դրա հիմքում դրեցի այն, թե ինչպես կուզենայի ինձ դասավանդել: Արձագանքը անհավանական էր։ Դասընթացին առաջին ամսվա ընթացքում գրանցվել են ավելի քան 3000 ուսանողներ ավելի քան 100 երկրներից:

Եթե ​​աշխատես հեշտ խնդիրների լուծման վրա, երբեք չես բարելավվի։

Ամենաարդյունավետ միջոցը հասկանալու այն, ինչ չգիտես, դա գործնականում զգալն է: Ես այդպես սովորեցի։ Ես սովորեցի շատ նոր տեխնիկա, որոնց մասին նախկինում երբեք չէի լսել՝ ընտրելով դժվար առաջադրանք:

Յուրաքանչյուր երրորդ խնդիր, որի վրա աշխատում եք, պետք է ձեզ նոր բան սովորեցնի: Խնդիրներ ընտրելիս ավելի զգույշ եղեք։ Ընտրեք ավելի բարդ խնդիրներ:

Երբ ավարտեք SPOJ-ի այս 250 խնդիրները, դուք կունենաք հիմնական պատկերացում սպորտային ծրագրավորման հիմնական թեմաների մասին: Հիմնական ալգորիթմների տրամաբանության խորը ըմբռնման դեպքում բարձր մակարդակի ալգորիթմները ավելի քիչ բարդ կթվան: Այս կերպ Դուք կարող եք առավելագույնս օգտագործել ձեր գիտելիքները:

Ավելի խորացրեք յուրաքանչյուր հիմնական թեմա

Ահա արժեքավոր ռեսուրս շատ տեղեկություններով: Այնտեղ դուք կգտնեք լավագույն 10 ալգորիթմները և տվյալների կառուցվածքները յուրաքանչյուր թեմայի համար: SPOJ-ի 250 խնդիրներից հետո դուք շատ բան կիմանաք այս ցուցակից։ Բայց դուք նաև կբախվեք շատ բաների վրա, որոնց մասին նախկինում երբեք չեք լսել: Այսպիսով, սկսեք ուսումնասիրել այս թեմաները աճման կարգով:

Եթե ​​նոր բան սովորելուց հետո գիտելիքներդ չամրապնդես, արագ կմոռանաս ամեն ինչ։
Ես խորհուրդ եմ տալիս, որ նոր ալգորիթմ սովորելուց հետո այն գործնականում օգտագործեք: Աշխատեք այն 2-3 առաջադրանքների միջոցով: Փնտրեք ալգորիթմի պիտակը SPOJ-ում: Այնտեղ դուք կգտնեք խնդիրներ, որոնք լուծելու համար անհրաժեշտ է այս ալգորիթմը: Նախ անդրադառնանք այս խնդիրներին:

Վարպետեք դինամիկ ծրագրավորում, քանի որ այն ձեզ կտանի դեպի հաղթանակ
Իմ փորձից ելնելով` յուրաքանչյուր մրցույթ առնվազն մեկ խնդիր ունի դինամիկ ծրագրավորում. Շատերի մոտ գլխացավ է առաջանում «դինամիկ ծրագրավորում» արտահայտությունը լսելիս, քանի որ այն ընդհանրապես չեն հասկանում:

Եվ սա լավ է: Որովհետև եթե հասկանում ես դինամիկ ծրագրավորում, ուրեմն կհաղթես։

Սիրում եմ դինամիկ ծրագրավորում, դա իմ սիրելի թեման է։ Դինամիկ ծրագրավորման գաղտնիքը գլոբալ օպտիմալ ընտրություն կատարելն է, ոչ միայն տեղական: Դուք պետք է խնդիրը բաժանեք ավելի պարզ ենթախնդիրների: Այս ենթախնդիրներից յուրաքանչյուրը լուծեք միայն մեկ անգամ: Այնուհետեւ ստեղծեք լուծում, որը միավորում է լուծված ենթախնդիրները։ Ագահ ալգորիթմ - դինամիկ ծրագրավորման հակառակը: Այն պահանջում է տեղական օպտիմալ ընտրություն կատարել յուրաքանչյուր քայլում: Իսկ տեղական օպտիմալ ընտրությունը կարող է հանգեցնել վատ գլոբալ լուծման:

Նոր հասկացություններ սովորելիս ստուգեք TopCoder ձեռնարկներ. Դրանք շատ մանրամասն ու հասկանալի են։ Նրանց շնորհիվ ես կարողացա հասկանալ երկուական ինդեքսավորված ծառեր.

Տքնաջան աշխատել

Երբևէ լսե՞լ եք մարզիկների մասին, ովքեր առանց տարիների պրակտիկայի հաղթում են Օլիմպիական խաղերում: Ես ոչ:

Ամեն տարի համակարգչային օլիմպիադայի նախապատրաստական ​​աշխատանքները սկսվում էին սեպտեմբերին և ավարտվում ապրիլին:

Այս 8 ամիսների ընթացքում ես ամեն օր պարապում էի 5 ժամ։

Եվ այո, ես այս 5 ժամը ծախսել եմ միայն ալգորիթմական խնդիրներ լուծելու վրա։ Հիշում եմ այն ​​օրերը, երբ պարապում էի 8 և նույնիսկ 10 ժամ։ Ինչո՞ւ։ Որովհետև դա ինձ դուր եկավ: Ամեն օր, երբ դպրոցից վերադառնում էի տուն, գնում էի ուղիղ ննջարան, նստում համակարգչի մոտ և սկսում էի վերլուծել նոր խնդիր։ Կամ ես սովորում էի նոր ալգորիթմ, որը պետք է իմանայի այս խնդիրը լուծելու համար:

Եթե ​​ուզում ես հաղթել, պետք է նույնը անես։ Ընտրեք խնդիր և մնացեք դրան: Մտածեք այդ մասին սուպերմարկետ գնալիս կամ մեքենա վարելիս:

Գիտեի՞ք, որ երբ դուք քնում եք, ձեր ուղեղը վերափոխում է այդ օրը հավաքագրված տեղեկատվությունը: Նա կարծես գրքեր է շարում այբբենական կարգով գրապահարանի վրա: Ըստ էության, ձեր ուղեղը մտածում է ձեր առջև ծառացած տարբեր խնդիրների մասին:

Սա կարելի է հմտորեն օգտագործել։ Քնելուց առաջ կարդացեք բարդ խնդիր և հիշեք, թե ինչ է անհրաժեշտ այն լուծելու համար։ Այս փուլում պետք չէ ինքնին լուծում փնտրել։ Գնալ քնելու. Ձեր ուղեղը կսկսի մշակել այս խնդիրը: Երբ արթնանաք, կզարմանաք՝ հասկանալով, որ լուծումը գտել եք քնած ժամանակ։

Փորձեք ինքներդ: Դա նման է մոգության:

Ես ստեղծել եմ վիդեո բլոգ

Այս կարճ պարբերությունը կապված չէ սպորտային ծրագրավորման հետ: Եթե ​​դուք քսան տարեկան եք և մտածում եք, թե ինչպես եմ ես տեսնում աշխարհը, գուցե ցանկանաք ստուգել իմ վիդեո բլոգը Youtube-ում. Ես խոսում եմ աշխարհի, կյանքի և համակարգչային գիտության մասին:

Խելացի աշխատեք

Սա է հաջողության գաղտնիքը։ Ձեզ պետք են նպատակներ։

Մենք մարդիկ ենք և դա մեզ դուր է գալիս հետաձգել. Մենք միշտ ցանկանում ենք հետաձգել այն, ինչ պետք է անել հենց հիմա: Netflix-ը դիտելը միշտ ավելի հաճելի է, քան դինամիկ ծրագրավորման խնդիրներով զբաղվելը: Դուք գիտեք սա, և դուք պետք է շտկեք այն:

Ինչպես հաղթահարել հետաձգումը

Ձեր առջեւ նպատակներ դրեք։ Դուք միշտ կգտնեք հետաքրքիր խնդիրներ, որոնցից կարող եք նոր բան սովորել (նայեք վերը նշված ռեսուրսներին): Բայց այս խնդիրները պետք է լուծվեն, ոչ թե պարզապես կարդալ:

Այսպիսով, ահա թե ինչպես ես հաղթահարեցի հետաձգումը: Ես սկսեցի թղթե օրացույց և ամեն օր լրացնում էի խնդիրներով, որոնք ցանկանում էի լուծել: Ես խնդիրները միշտ լրացրել եմ երկու օր առաջ։ Այսպիսով, ես գիտեի, թե ինչպես տնօրինել իմ ժամանակը հաջորդ օրերին:

Այնպես որ, ես միշտ մոտիվացված էի: Ինձ պետք էր որոշ խնդիրներ լուծել և նորերը գտնել օրացույցի հաջորդ օրերը լրացնելու համար: Լուծված խնդիրները հատելը հիանալի է: Գիտեմ, որ քեզ էլ է դուր գալիս:

Ստացեք ձեր սեփական թղթային օրացույցը: Հեռախոսում մի ստեղծեք այլ անելիքների ցուցակ, որի մասին վաղը կմոռանաք:

Ինչպես արդյունավետ կերպով կարգաբերել

Ցանկանու՞մ եք պրոֆեսիոնալ դառնալ։ Եթե ​​այո, ապա դուք պետք է «վրիպազերծեք այն ձեր մտքում»:
Սա իմ իմացած վրիպազերծման ամենաարդյունավետ տեխնիկան է, քանի որ այն ընդհանրապես չի պահանջում վրիպազերծիչ: Ձեր ուղեղը միաժամանակ ուսումնասիրում է կոդի բազմաթիվ ճյուղեր և ձեզ տալիս է կոդի ավելի լայն ակնարկ՝ համեմատած դրա հետ դասական կարգաբերիչ.

Դուք կարող եք համեմատվել գրոսմայստերի հետ, ով շախմատ է խաղում և մտածում է 3 քայլ առաջ:

Ես օգտագործում եմ այս տեխնիկան բացառապես որպես իմ սկզբնական պաշտպանության գիծ: Հետո ես օգտագործում եմ իրական կարգաբերիչ:

Որպեսզի սովորեք, թե ինչպես կարգաբերել ձեր գլխում, դուք պետք է փորձեք: Երբ դուք հաստատում եք խնդրի լուծումը և ստանում «սխալ պատասխան», անմիջապես մի անցեք վրիպազերծիչի կոճակին: Կրկին կարդացեք կոդը և մտածեք. «Ի՞նչ է կատարվում այս տողում», «Ինչպե՞ս է «եթե»-ն ազդում ծրագրի վրա», «Երբ մենք դուրս ենք գալիս հանգույցից, ո՞րն է կրկնվողի արժեքը»:

Այս կերպ դուք ինքներդ եք մտածում: Ժամանակի ընթացքում դուք կսովորեք գրել կոդ և շտկել այն անմիջապես:

Հեղինակի մասին

Անդրեյ Մարգելոյուն մոլի ծրագրավորող է, որը հետաքրքրված է ձեռներեցությամբ, ստարտափներով և դրսում: Դուք կարող եք կապվել նրա հետ LinkedIn-ում.

Թարգմանություն՝ Դիանա Շերեմևա

Source: www.habr.com