Programare Competitivă

Cheatsheet pentru olimpiadă

O pagină de referință rapidă: tot ce ai nevoie la minutul 0 al concursului, când deschizi enunțul și trebuie să decizi repede. Nu e o lecție - e un aide-mémoire la care te întorci.

1. Tabel de complexități - ce încape în 1 secundă?

Rulând pe un judge modern (Intel @ 2-3 GHz), cu C++ compilat cu -O2, poți face aproximativ 10⁸ operații simple pe secundă. Deci:

N maxim Complexitate acceptabilă Exemple de algoritmi
N ≤ 11 O(N!) Brute force permutări
N ≤ 20 O(2^N) sau O(2^N · N) Bitmask DP, submulțimi
N ≤ 100 O(N⁴) DP cu 4 stări, LCS pe 3 șiruri
N ≤ 500 O(N³) Floyd-Warshall, DP pe intervale
N ≤ 5 000 O(N²) DP clasic 2D, Dijkstra naiv
N ≤ 10⁵ O(N · √N) Sqrt decomposition, Mo’s algorithm
N ≤ 10⁶ O(N log N) Sortare, Dijkstra cu heap, segment tree
N ≤ 10⁷ O(N) sau O(N log log N) Ciur, two pointers, prefix sums
N ≤ 10⁸ O(N) cu constantă mică Citire rapidă, procesare liniară pură
N ≤ 10¹⁸ O(log N) sau O(1) Binary search pe răspuns, formule matematice

Regulă empirică: dacă N = 10⁵, vizează O(N log N). Dacă N = 10⁶, vizează O(N). Dacă vezi N ≤ 20, gândește-te imediat la bitmask.

2. Limite de memorie - cum calculezi

Regula: nr_elemente × bytes_per_element = total_bytes. Împarte la 10⁶ → MB.

Tip Bytes Câte elemente încap în… 64 MB 128 MB 256 MB
bool 1 64·10⁶ 128·10⁶ 256·10⁶
char 1 64·10⁶ 128·10⁶ 256·10⁶
int 4 16·10⁶ 32·10⁶ 64·10⁶
long long 8 8·10⁶ 16·10⁶ 32·10⁶
double 8 8·10⁶ 16·10⁶ 32·10⁶

Exemple de matrici (int, 4 bytes/element):

Matrice Celule Memorie 64MB 128MB 256MB
int[1000][1000] 10⁶ 4 MB OK OK OK
int[2000][2000] 4·10⁶ 16 MB OK OK OK
int[4000][4000] 1.6·10⁷ 64 MB muchie OK OK
int[5000][5000] 2.5·10⁷ 100 MB MLE OK OK
int[10000][10000] 10⁸ 400 MB MLE MLE MLE

Atenție - limite la OJI/ONI: adesea 64 MB sau 128 MB, nu 256. Citește întotdeauna „Memorie” din enunț. Nu presupune 256 MB.

Dacă ai nevoie de flaguri bool pe un spațiu uriaș, folosește bitset (vezi bitset din STL) - 8× mai compact decât bool[] (1 bit/element în loc de 1 byte).

3. Template C++ pentru concurs

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define fi first
#define se second

const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const int NMAX = 1e6 + 5;

int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    return 0;
}
  • ios_base::sync_with_stdio(false); cin.tie(NULL); - obligatoriu dacă citești >10⁵ valori cu cin.
  • Nu uita return 0;.

5. Aritmetică modulară - formule esențiale

Pentru MOD = 10⁹ + 7 (prim):

Operație Formulă
Adunare (a + b) % MOD
Scădere ((a - b) % MOD + MOD) % MOD
Înmulțire (1LL * a * b) % MOD
Putere a^n vezi Exponențierea rapidă
Invers modular a⁻¹ putere(a, MOD - 2, MOD) (Fermat mic)
Împărțire a / b (a * putere(b, MOD - 2)) % MOD

Greșeală clasică: a * b când a, b sunt int → overflow. Pune 1LL * la început.

6. Combinatorică - formule de reper

Obiect Formulă Lecția
Permutări P(n) n! Permutări
Aranjamente A(n, k) n! / (n - k)! Aranjamente
Combinări C(n, k) n! / (k! · (n - k)!) Combinări
Pascal C(n, k) = C(n-1, k-1) + C(n-1, k) Triunghiul lui Pascal
Combinări cu repetiție C(n + k - 1, k) Combinări cu repetiție
Stars and Bars (x₁+…+xₖ=n) C(n + k - 1, k - 1) Stars and Bars
Catalan Cₙ C(2n, n) / (n + 1) Numere Catalan

7. STL - complexități de care trebuie să ții minte

Container insert / erase / find Observații
vector O(1) push_back, O(N) insert la mijloc cel mai rapid pentru parcurgeri
set / map O(log N) sortat, fără duplicate
multiset / multimap O(log N) sortat, cu duplicate
unordered_set / unordered_map O(1) amortizat poate degenera la O(N) cu hash rău
priority_queue O(log N) push/pop max-heap implicit
deque O(1) push/pop capete ideal pentru sliding window
bitset<N> O(N / 64) per operație 8× mai compact decât bool[]

Trucuri utile:

  • lower_bound(v.begin(), v.end(), x) → iterator spre prima poziție ≥ x - O(log N) pe vector sortat.
  • __builtin_popcount(x) → numărul de biți de 1 din x.
  • __builtin_clz(x) / __builtin_ctz(x) → zerouri leading/trailing.
  • next_permutation(v.begin(), v.end()) → generează toate permutările în ordine.

8. Greșeli clasice care te costă puncte

  • Overflow: 1LL * a * b în loc de a * b când depășește 2·10⁹.
  • Indexare de la 0 vs de la 1: hotărăște de la început și fii consecvent.
  • Vectori globali vs locali: globalii sunt inițializați cu 0; cei locali NU.
  • int vs long long pentru sume de N ≥ 10⁵ elemente mari.
  • Citire cu cin fără sync_with_stdio(false) pe N mare.
  • Lipsa \n la sfârșit - unele judge-uri sunt stricte.
  • Recursivitate prea adâncă → stack overflow. Pentru N > 10⁵ recursivitate, crește stack sau iterativ.
  • endl în loc de "\n" - endl face flush, e lent.
  • Modulo negativ: (-3) % 5 == -3 în C++, nu 2. Adaugă + MOD) % MOD.
  • pow() pe int - returnează double, pierde precizie. Scrie-ți propria exponențiere.

9. Checklist înainte de submit

10. Strategie de concurs (timp)

OJI / ONI - 4 ore, 3 probleme (sau 3 ore, 2 probleme pentru gimnaziu):

  1. Primele 15 min - citește toate cele 3 probleme. Evaluează-le: care e cea mai ușoară?
  2. Începe cu cea mai ușoară - nu cu prima din listă, cu cea mai ușoară pentru tine.
  3. Nu rămâne blocat - dacă ai pierdut 30 min fără progres, treci la alta.
  4. Subtask-urile contează - dacă nu poți 100p, ia 40p sau 60p cu o soluție parțială (brute force, N mic).
  5. Ultimele 20 min - verificări, edge cases, fișiere, long long. Nu submite în ultimele 2 minute dacă merge deja.

11. Când să folosești ce - pattern matching pe enunț

Dacă în enunț vezi… Gândește-te la…
„cea mai scurtă / cea mai lungă subsecvență” Two pointers, sliding window
„suma / minim / maxim pe interval” Prefix sums, sparse table, segment tree
„câte moduri”, „număr de” Combinatorică, DP de numărare
„drum minim”, „cost minim” BFS, Dijkstra, Bellman-Ford
„modulo 10⁹ + 7” Aritmetică modulară, exponențiere rapidă
„k-ul cel mai mic/mare” Heap, nth_element, sortare parțială
„substring”, „șablon” KMP, Rabin-Karp, hashing
„răspunsul este unic și crescător/descrescător în X” Binary search pe răspuns
„N ≤ 20” Bitmask
„arbore”, „părinte”, „fiu” DFS, parcurgere recursivă

12. Resurse externe utile

  • infoarena.ro - arhivă romanească, probleme clasice cu editorial.
  • pbinfo.ro - probleme pe teme, bun pentru începători.
  • kilonova.ro - platforma nouă românească, concursuri active.
  • codeforces.com - concursuri săptămânale, rating, editoriale bune.
  • cses.fi/problemset - set curat de probleme pe teme (CP handbook).
  • usaco.guide - ghid structurat pe niveluri (bronze → platinum).

PS. Acest cheatsheet e viu - adaugă aici orice formulă, truc sau pattern pe care îl descoperi și vrei să-l ai la îndemână în următorul concurs. Un cheatsheet bun e cel pe care l-ai scris tu.

Notițele tale

Nesalvat

Scrie aici orice — formule, trucuri, idei. Se salvează automat în browser-ul tău (localStorage). Nu se sincronizează între dispozitive.

Mult succes!

„Norocul ține cu cei pregătiți.”

Indiferent dacă te pregătești pentru OJI, ONI, un concurs online sau pur și simplu vrei să rezolvi o problemă grea, ține minte: fiecare submisie greșită te apropie de cea corectă, fiecare problemă pe care n-o înțelegi azi va deveni evidentă mâine, iar fiecare oră de antrenament contează.

Nu uita de ce ai început. Respiră adânc înainte de fiecare problemă. Citește enunțul de două ori. Și dă-i drumul.

Baftă la concurs! 🚀

Cuprins Inapoi Inainte