SISergiu Ilincameditații informatică
Meniu

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ție

Instrumente

  1. OL.175 min· 6 probleme

    STL pentru concurs: sort cu comparator, set, map, priority_queue

    Sortezi orice fel de date cu un comparator scris de tine.

Eficiență

  1. 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).

  2. 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

  1. 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 …”.

  2. 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

  1. 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.

  2. 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ă.

  3. 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

  1. OL.980 min· 6 probleme

    Teoria numerelor pentru concurs: ciur, divizori, ridicare la putere, aritmetică modulară

    Generezi numerele prime cu ciurul lui Eratostene în O(n log log n).

Grafuri

  1. OL.1090 min· 6 probleme

    Grafuri pentru concurs: Dijkstra cu heap, sortare topologică, DP pe DAG

    Implementezi Dijkstra cu priority_queue, în O((n + m) log n), pe liste de adiacență.

Tehnici

  1. OL.1180 min· 6 probleme

    Operații pe biți și mulțimi codificate pe biți (bitmask), DP pe submulțimi

    Folosești operatorii pe biți (&, |, ^, ~, <<, >>) și verifici, setezi, ștergi, comuți un bit.

Strategie

  1. OL.12120 min· 6 probleme

    Strategie la concurs și simulare de olimpiadă

    Citești un enunț și alegi algoritmul pornind de la limitele de timp și de la constrângeri.

// 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.

Programează intro gratuit