avansat · olimpiadă · concursuri · C++
Pregătire pentru olimpiadă și concursuri de informatică (C++)
Tehnicile care contează la concurs: STL și complexitate, doi pointeri, sume parțiale, căutare binară pe răspuns, programare dinamică, DSU, Fenwick, arbori de intervale, teoria numerelor, grafuri și biți, încheiate cu o simulare de concurs. Probleme de pe infoarena, CSES și pbinfo.
12 lecții · 63 probleme de concurs
Începe cu prima lecțieInstrumente
Eficiență
OL.275 min· 5 probleme
Complexitate, doi pointeri și fereastra glisantă
Estimezi din limitele problemei ce complexitate este acceptabilă (și respingi din start soluțiile prea lente).
OL.375 min· 6 probleme
Sume parțiale pe matrice, vectori de diferențe și subsecvențe cu sumă dată
Calculezi suma oricărui dreptunghi dintr-o matrice în O(1) după o precalculare O(n·m).
Tehnici
OL.475 min· 5 probleme
Căutare binară pe răspuns
Recunoști o problemă de tip „cea mai mare / cea mai mică valoare pentru care se poate …”.
OL.590 min· 7 probleme
Programare dinamică de concurs: LCS, distanța de editare, LIS rapid, rucsac 1D
Construiești tabele dp pe două șiruri: cel mai lung subșir comun (LCS) și distanța de editare.
Structuri de date
OL.675 min· 6 probleme
Mulțimi disjuncte (DSU / Union-Find) și algoritmul lui Kruskal
Reții grupurile (mulțimile disjuncte) ca o pădure de arbori și implementezi find și union.
OL.770 min· 5 probleme
Arbori indexați binar (Fenwick): sume pe interval cu actualizări
Înțelegi de ce sumele parțiale nu ajung când valorile se modifică.
OL.890 min· 6 probleme
Arbori de intervale (segment tree) și propagare leneșă
Construiești un arbore de intervale și explici ce reține fiecare nod.
Matematică pentru programatori
Grafuri
Tehnici
Strategie
// meditații online
Te pregătești pentru olimpiadă sau pentru un concurs?
Parcurgem lecțiile în ritmul tău, pe Google Meet, și rezolvăm problemele pe ecran partajat. Primul pas e un intro gratuit de 20 de minute.