Cea mai bună foaie de parcurs de programare competitivă 🔥🔥🔥

Gândește-te repede, stai în fața concurenței și învață lucruri noi.

În acea singură linie, există întreaga esență a programării competitive. Vi se oferă un mediu programat pentru a gândi și a veni cu cea mai rapidă soluție la întrebările date.

În plus, soluțiile trebuie să fie acceptabile pentru a rula în limita de timp dată de 1 secundă.

În primul rând, învață un limbaj de programare. Ar putea fi C++ sau Java. Dar asigurați-vă că ați învățat elementele interioare și în afara limbii. Aflați cum funcționează diferitele tipuri de bucle și declarații if-else. Aș recomanda următorul curs pe Udemy pentru a învăța ambele limbi minunate.

Eu personal le-am luat pe amândouă. Dar acum îmi dau seama că cunoașterea multor limbi nu contează deloc nici pentru programarea competitivă, nici pentru interviurile FAANGM.

Pasul următorul și pasul fără sfârșit este să stăpânești structurile de date și algoritmii.

Acesta este cel mai provocator și mai distractiv cu care trebuie să te confrunți, uneori, îți vei trânti laptopul și nu ai vrea să-l vezi în viața ta. Vezi că asta se întâmplă cu toți cei care se numesc programatori.

Acestea sunt câteva site-uri care vă vor ajuta pe parcursul călătoriei dvs. Sunt de mare ajutor.

1 set de lucruri de bază

1. Probleme de imprimare a modelului
2. analiza timp-complexitate
3. căutare liniară și reprezentare în matrice circulară
4. palindrom și alte numere (perfect, Armstrong) pentru problemele de bază ale numerelor
5. Problemă simplă de hashing (numărarea frecvenței și altele)
6. Probleme cu suma prefixelor (1D și 2D) {codeforces}
7. Tehnica ferestrei glisante (2 din 5 concursuri)

Matematică și teoria numerelor

Bazele teoriei numerelor

1. Căutarea binară este obligatorie (2/5 concursuri)
2. GCD de 2 numere în timp logaritmic (algoritm euclidian și extins)
3. Ecuația diofantină liniară
4. Verificarea primului în complexitatea sqrt(n).
5. Sita lui Eratosthenes (foarte imp pentru a efectua probe de interogare pe primul)
6. Sita segmentata
7. Găsirea factorizării prime a unui număr în log(n) per interogare
8. Funcția Euler Totent
9. Mica Teoremă Fermat
10. Teorema lui Wilson

(gfg articole și probleme de pământ pentru hackeri pentru 8,9,10)

Versiune mai dură a teoriei numerelor

1. Găsirea x^n în log(n)
2. Aritmetică modulară
3. Inversul modular al unui număr
4. Exponentiație modulară
5. Teorema restului chineză
6. Modul factorial Mod
7. Găsirea nCr și nPr pentru interogări (timp constant)
8. Principiul de includere-excludere (probleme combinatorii) {hackerearth are o grămadă minunată} {codeforces}

Câțiva algoritmi de bază.

1. aflați despre algoritmii de sortare de bază (balon, selecție, inserare)
2. faceți probleme care sunt constructive și au o mulțime de termeni de schimb în ele.
3. rezolva probleme legate de abordarea cu două puncte.
4. Manipularea biților (deplasare la stânga, schimbare la dreapta, xor sau, și, set bit, MSB, LSB etc..)
5. Setul de putere al unui anumit tablou sau șir folosind BIT
6. Numărul de subbariere cu XOR ca zero (nu este un algoritm, ci o problemă obligatorie) (HackerEarth are un tutorial foarte bun despre manipularea biților, codarea blocurilor pentru a avea un videoclip adecvat pe un bit) {pentru probleme, vizitați hackerearth}
7. Probleme legate de eticheta algoritmului lacom
8. Algoritmul lui Kadane și problemele legate de acestea
9. Problema de secvențiere a locurilor de muncă și de selecție a activității (după ce ați făcut 8 și 9, mergeți la forțele de cod și rezolvați problemele cu o etichetă lacomă pe ele.)

Să o facem din nou și din nou.

Este bine să înveți recursiunea

1. începeți cu probleme de bază, cum ar fi găsirea factorilor și tot.
2. implementați căutarea binară
3. implementați exponentiația modulară folosind recursiunea
4. rezolva probleme de recursivitate, cum ar fi găsirea de subseturi cu date și altele pentru a obține o strângere puternică
5. Aflați despre sortarea prin îmbinare și sortarea rapidă
6. rezolva probleme legate de sortarea prin îmbinare
7. Faceți probleme de backtracking precum sudoku și N Queen, vă va ajuta atunci când doriți să faceți probleme cu calea DP

(pentru recursivitate vă puteți referi la leetcode sau la practica gfg unde veți găsi probleme de recursivitate și backtracking)

După recurență:

1. Întâlnește algoritmul de mijloc și problemele legate de acesta. 2. Împărțiți și învingeți problemele{recomandat să folosiți forțele de cod numai pentru aceasta}
2. Următorul element mai mare și următorul element mai mic folosind stiva
3. probleme legate de paranteză.
4. cea mai mare zonă dreptunghiulară din histogramă. (conceptul este folosit în multe probleme)
5. Probleme legate de Heap (Priority Queue) {deși acest lucru se înscrie în categoria lacomi după coada de prioritate, vă va ajuta să învățați o bibliotecă de șabloane standard încorporată sau o bibliotecă de colecții Java)

Componente avansate și decizia jocului

Algoritmi de șiruri:

1. hashing pe șiruri (învățați și rezolvați problema, înțelegeți când are loc o coliziune) {cpalgorithms are un articol minunat scris pe el) {Spoj sau codeforces}
2. Algoritmul Rabin Karp (cpalgorithm.com are un blog minunat pe el)
3. Funcția de prefix
4. Algoritmul KMP
5. Funcția Z
6. Algoritmul Manchers (odată ce ați completat algoritmii de mai sus, rezolvați o grămadă de probleme (25-30) pe ei de pe platforme diferite.)

Algoritmul arborelui:

1. Reprezentare arbore/grafic
2. Traversare DFS/BFS în grafic/arbore
3. Lucruri de bază (diametrul copacului, înălțimea copacului, nivelul copacului)
4. Euler Tour of Tree (Învățați și rezolvați probleme)
5. Găsirea LCA folosind Euler Tour(14:00){soluția eficientă folosește arbori de segmente)
6. Găsirea LCA folosind Binary Lifting.
7. Distanța dintre două noduri.
8. Probleme subarbore. (SPOJ este foarte recomandat pentru copaci și problemele de forțe de cod D și E, de asemenea)

Grafice:

1. Componente conectate.
2. Sortare topologică.
3. Detectarea ciclului în grafic
4. Graficul bipartit de check-in
5. SCC folosind algoritmul lui Kosaraju
6. Algoritmul lui Dijkstra
7. Surse pentru algoritmul Bellman-Ford pentru învățare: bloguri HackerEarth și cpalgorithm
   (25–30 de probleme pe subiectele de mai sus, SPOJ și codeforces, și HackerEarth)

Apoi:

1. Poduri În grafice
2. Punct de articulație într-un grafic
3. Arborele de întindere minim folosind Algo-ul lui Kruskal
4. Algoritmul lui Prim
5. 0/1 BFS (un mare salvator)
6. Aflați Găsirea podurilor online (cpalgorithms) Rezolvați problema

Programare dinamică:

1. Rezolvați concursurile educaționale AtCoder privind programarea dinamică. (toate 26)
2. Rezolvați problemele din SPOJ (foarte recomandat, deoarece nu implică alți algoritmi)
3. Google dynamic programare practice problem codeforces, voi obține un blog minunat cu o mulțime de probleme pe el. După toate DP standard de mai sus, aflați:
4. Înțelegeți cum scriem recurența pentru Digit DP(codeforces blog)(digit dynamic prog) și rezolvam probleme
5. citește despre DP cu Bitmasks și rezolvă probleme (blogul HackerEarth)
6. DP pe copaci (articole gfg, videoclipul lui Rachit Jain)
7. SOS DP (cpalgorithm blog) Rezolvați cât mai multe probleme posibile
8. Set disjunc (cpalgoritmi)
9. Interogări offline folosind Setul Disjoint (problema de matrice colorată de la spoj)
10. Algoritmul lui Kruskal folosind un set disjunc Rezolvați o mulțime de probleme de mai sus
11. Tabel rar (nu acela imp)
12. Fenwick Tree și Binary Lifting pe Fenwick Tree (citiți și despre trucul de actualizare a intervalului)
13. probleme pe arborele Fenwick
14. Exponentiarea matricei (probleme)
15. Tehnica de descompunere Sqrt (gfg sau cpalgorithms sau codeforces)
16. Operațiuni de actualizare și interogare
17. Algoritmul lui Mo (rezolva o matrice puternică din codeforces) (blog codeforces)
18. Algoritmul lui Mo pe copaci
19. Arborele de segmente (obligatoriu) (Interogări de interval și actualizări de puncte)
20. Propagare leneșă pe arbori segmentați

Apoi unele opționale și rare:

1. Sprague-Grundy Theorum
2. Fluxuri și probleme conexe
3. Descompunere ușoară grea
4. Algoritmul Convex Hull
5. FFT/NTT

Uite aici ceea ce spun este doar experiența mea, așa că te rog să nu sări peste asta. Te vei confrunta cu multe probleme, mai jos sunt soluțiile la multe dintre ele.

Atitudinea mentală este ceea ce le lipsește cel mai mult oamenilor. Amintiți-vă că pot exista momente în care ați dori să renunțați la toate, să vă trăiți viața așa cum ați fost.

Chiar și eu am suferit din cauza faptului că erau multe subiecte pe care nu le cunoșteam pe toate din cauza cărora nu puteam rezolva întrebări, aș continua o zi întreagă fără a rezolva o singură întrebare.

Ideea aici este de a oferi întrebării un nou timp de 15-20 de minute, 30-40 de minute, în funcție de nivelul de dificultate al întrebării. Dacă totuși, nu reușiți să faceți bine întrebările, vedeți editorialul acelei întrebări anume ia un mic indiciu, apoi folosiți-vă creierul. iar întrebarea completă trebuie rezolvată în 1 oră.

Făcând acest lucru, investind peste 6 ore pe zi timp de 4 luni, veți rezolva peste 720 de întrebări, care sunt mai mult decât suficiente pentru a ajunge la master candidat în Codeforces sau pentru a sparge orice companie FANGM.

Vă rog să mă urmăriți, împărtășiți cu prietenii tăi.

🤫Cum îmi folosesc noțiunea pentru a-mi îmbunătăți pregătirea DSA.