|
Takmičarsko programiranje • Državno • SIO
Priprema za državno takmičenje i SIO iz informatikeKompletan plan pripreme za učenike 8. razreda i 1. godine srednje škole. Fokus je na razvoju algoritamskog razmišljanja, dinamičkog programiranja, grafova, kombinatorike i naprednih takmičarskih tehnika. 11-nedeljni plan pripremePlan je namenjen učenicima koji već imaju osnovno iskustvo sa rekurzijom, kombinatorikom i osnovnim algoritmima, i žele da pređu na državni i SIO nivo takmičenja. Fokus nije samo na učenju algoritama, već i na razvoju načina razmišljanja koji je potreban za rešavanje kompleksnih takmičarskih problema.
Osnovni nivo
Rekurzija i kombinatorika
Permutacije, kombinacije, memoizacija i prvi koraci ka DP-u.
Srednji nivo
Dinamičko programiranje i grafovi
Klasični DP problemi, BFS, DFS, Dijkstra i modelovanje stanja.
Napredni nivo
SIO i olimpijski zadaci
Interaktivni problemi, optimizacije i napredne strukture podataka.
Preporučeno predznanje:
Kako koristiti ovaj plan?
|
Nedelja 1 — Rekurzija i algoritamsko razmišljanje
Prva nedelja je posvećena razvijanju načina razmišljanja koji je neophodan za takmičarsko programiranje. Fokus nije samo na pisanju koda, već na tome kako se problem razlaže na manje podprobleme.
Rekurzija predstavlja osnovu za kasnije oblasti kao što su backtracking, dinamičko programiranje, DFS i napredne pretrage stanja.
Teme koje treba savladati
- Osnovna rekurzija i povratak iz funkcije
- Rekurzivno računanje sume, stepena i faktorijela
- Rekurzivni obilazak nizova i stringova
- Praćenje stabla rekurzivnih poziva
- Razlika između iterativnog i rekurzivnog pristupa
- Vremenska složenost jednostavne rekurzije
- Memoizacija kao uvod u dinamičko programiranje
- Hanojske kule i analiza rekurzivnog stabla
Predloženi zadaci za vežbu
Nedelja 2 — Backtracking i generisanje kombinacija
Nakon osnova rekurzije prelazi se na backtracking — sistematsko pretraživanje prostora rešenja uz vraćanje na prethodno stanje.
Backtracking se može posmatrati kao rekurzija + provera uslova. Za razliku od obične grube sile (brute-force), kod backtracking pristupa ne ispitujemo bespotrebno sva moguća rešenja, već rano odbacujemo grane koje sigurno ne mogu dovesti do validnog rezultata.
Teme koje treba savladati
- Permutacije i kombinacije
- Podskupovi
- Backtracking stablo
- Pruning (odsecanje grana)
- DFS u prostoru rešenja
- Razlika između brute-force i backtracking pristupa
- Generisanje rešenja sa ograničenjima
Predloženi zadaci za vežbu
- TAČAN IZRAZ — generisanje kombinacija i izraza.
- Permutacije i podskupovi — SvetProgramiranja
- Brojanje načina (dekodiranje / Fibonacci)
- Generisanje kombinatornih objekata
- N kraljica — detaljno objašnjenje
- Analiza više rešenja problema N kraljica
- Sudoku solver
- Rešavač Sudokua — detaljno objašnjenje
- LeetCode — N Queens
- LeetCode — Sudoku Solver
- Word Search (DFS + backtracking)
- Reči u mreži — lokalno rešenje
Kod svakog zadatka pokušaj da identifikuješ:
- Stanje — šta trenutno znaš?
- Izbor — koje opcije možeš da probaš?
- Validnost — da li je parcijalno rešenje dozvoljeno?
- Prekid — kada je rešenje kompletno?
Nedelja 3 — Sortiranje, binarna pretraga i složenost
Fokus ove nedelje je na algoritmima koji se veoma često pojavljuju na školskim, okružnim i državnim takmičenjima. Dobro poznavanje sortiranja, binarne pretrage i vremenske složenosti često omogućava da se zadatak reši višestruko brže od naivnog pristupa.
Teme koje treba savladati
- Merge Sort
- Quick Sort
- STL sort i comparator funkcije
- Binarna pretraga
- Lower Bound i Upper Bound
- Sortiranje po više kriterijuma
- Analiza vremenske složenosti
- Binary Search on Answer
Predloženi zadaci za vežbu
- Pronaći prvi element ≥ x u sortiranom nizu.
- Pronaći poslednji element ≤ x u sortiranom nizu.
- Izračunati broj pojavljivanja elementa korišćenjem lower_bound i upper_bound.
- Sortirati intervale po početku, a zatim po kraju.
- Sortirati objekte po više kriterijuma korišćenjem comparator funkcije.
- Rešiti zadatak korišćenjem Binary Search on Answer pristupa.
- LeetCode — Binary Search
- Search Insert Position
- First and Last Position of Element in Sorted Array
- Koko Eating Bananas — klasičan primer „binary search on answer“ pristupa.
Kada primetiš da zadatak traži najmanju ili najveću vrednost koja zadovoljava određeni uslov, proveri da li se odgovor može pronaći binarnom pretragom. Takvi zadaci se veoma često pojavljuju na okružnim, državnim i međunarodnim takmičenjima.
Nedelja 4 — Uvod u dinamičko programiranje (DP)
U ovoj nedelji uvodimo ključne ideje iz dinamičkog programiranja (DP) — tehnike koja omogućava rešavanje problema koje bi čista rekurzija rešavala presporo, tako što pamti rezultate već obrađenih podproblema.
Teme koje treba savladati
- Preklapanje podproblema (Overlapping Subproblems)
- Optimalna podstruktura (Optimal Substructure)
- Definisanje DP stanja (State)
- DP prelazi (Transitions)
- Memoizacija (Top-Down DP)
- Tabulacija (Bottom-Up DP)
- Optimizacija memorije
- Fibonacci kao uvodni DP primer
- 1️⃣ Definiši stanje —
dp[...] - 2️⃣ Odredi bazne slučajeve
- 3️⃣ Napiši prelaze između stanja
- 4️⃣ Izaberi redosled računanja (top-down ili bottom-up)
Glavni koncepti
- Preklapanje podproblema — isti podproblemi se pojavljuju više puta tokom rekurzije.
- Optimalna podstruktura — optimalno rešenje problema može se sastaviti od optimalnih rešenja manjih podproblema.
- State & Transition — najvažniji korak je pravilno definisanje značenja DP stanja i prelaza.
Najveći problem kod početnika nije implementacija,
već pravilno definisanje značenja DP niza.
Ako ne znaš šta predstavlja dp[i],
gotovo sigurno nećeš napisati ispravno rešenje.
Fibonacci kao uvodni primer
Fibonacci je idealan primer za poređenje: rekurzije, memoizacije i tabulacije. Na njemu se veoma jasno vidi zašto dinamičko programiranje donosi ogromno ubrzanje.
- Memoizacija (Top-Down) koristi rekurziju i čuva rezultate već obrađenih stanja.
- Tabulacija (Bottom-Up) kreće od baznih slučajeva i iterativno popunjava DP tabelu.
- Oba pristupa često imaju istu asimptotsku složenost, ali tabulacija omogućava bolju kontrolu memorije.
Predložene lekcije
Predloženi zadaci za vežbu
- AtCoder DP A — Frog 1
- Climbing Stairs — prvo rekurzija, zatim memoizacija i na kraju tabulacija.
- 0/1 Knapsack — SvetProgramiranja
- Coin Change — minimum kovanica.
- Coin Change — broj načina formiranja zadate sume.
- Longest Common Subsequence (LCS)
- AtCoder Educational DP Contest
AtCoder Educational DP Contest (A–Z) predstavlja jedan od najboljih setova zadataka za sistematsko učenje dinamičkog programiranja. Zadaci su poređani tako da se postepeno uvode nove DP ideje.
Plan rada (predlog)
- Analiziraj Fibonacci rekurziju i pronađi ponavljanje podproblema.
- Izmeri broj poziva funkcije za n=30 i n=40.
- Implementiraj memoizaciju i uporedi broj poziva.
- Pređi na bottom-up tabulaciju.
- Optimizuj memoriju sa O(n) na O(1).
- Reši Frog 1 koristeći isti princip.
- Počni prve Knapsack i Coin Change zadatke.
- Uporedi performanse rekurzije, memoizacije i tabulacije.
Studijske napomene
- DP često nastaje kao optimizacija spore rekurzije.
- Uvek prvo napiši značenje DP stanja na papiru.
- Bazni slučajevi su podjednako važni kao i prelazi.
- Pokušaj da objasniš prelaze bez gledanja u kod.
- Ne memoriši formule — razumi značenje svakog stanja.
Resursi i reference
Nedelja 5 — Dinamičko programiranje sa više dimenzija (2D / 3D DP)
Nakon savladavanja osnovnih DP problema sa jednom dimenzijom, prelazimo na zadatke kod kojih stanje zavisi od dva ili više parametara. Ovakvi problemi se veoma često pojavljuju na okružnim, državnim i SIO takmičenjima.
dp[i][j] i dp[i][j][k],
kao i kako da pravilno odrediš redosled popunjavanja DP tabele.
Teme koje treba savladati
- 2D DP stanja —
dp[i][j] - 3D DP stanja —
dp[i][j][k] - DP nad matricama
- DP nad stringovima
- Longest Common Subsequence (LCS)
- Edit Distance
- 0/1 Knapsack kao 2D DP
- Optimizacija memorije (2D → 1D)
- Redosled popunjavanja DP tabele
Ako problem zavisi od dva nezavisna parametra (npr. pozicija u matrici, dva stringa ili indeks i kapacitet), vrlo često je potrebno koristiti 2D dinamičko programiranje.
Kako prepoznati 2D DP?
- Postoje najmanje dva parametra koja određuju stanje problema.
- Rešenje zavisi od kombinacije više prethodnih stanja.
- Prirodno se formira tabela
dp[i][j]. - Često se pojavljuju matrice, stringovi ili dva nezavisna indeksa.
- Potrebno je pratiti više informacija istovremeno.
Klasični 2D DP problemi
DP nad matricama
Kod problema sa mrežama i matricama najčešće se koristi stanje:
dp[i][j]
koje predstavlja najbolju vrednost do polja
(i,j).
- iz gornjeg polja
- iz levog polja
- iz dijagonalnog polja
- kombinacija više prethodnih stanja
DP nad stringovima
- Longest Common Subsequence (LCS) — pronalazak najdužeg zajedničkog podniza dva stringa.
- Edit Distance — minimalan broj operacija potrebnih za transformaciju jednog stringa u drugi.
- Longest Common Substring — najduži zajednički neprekidni podniz.
Predloženi zadaci za vežbu
- Petlja — Maksimalni zbir puta kroz matricu
- SvetProgramiranja — Maksimalan zbir kroz matricu
- Longest Common Subsequence (LCS)
- LeetCode — Longest Common Subsequence
- LeetCode — Edit Distance
- AtCoder DP C — Vacation
- AtCoder DP E — Knapsack 2
Plan rada (predlog)
- Počni sa jednostavnim DP problemima nad matricama.
- Ručno nacrtaj DP tabelu za male ulazne primere.
- Analiziraj kako se formiraju prelazi između stanja.
- Pređi na LCS i probleme nad stringovima.
- Implementiraj Edit Distance.
- Pokušaj optimizaciju memorije na dva reda.
- Uporedi memorijsku složenost 2D i optimizovanog 1D rešenja.
Česte greške
- Nejasno značenje DP stanja.
- Pogrešan redosled popunjavanja.
- Zaboravljeni bazni slučajevi.
- Prevelika memorijska složenost.
- Neprepoznavanje dimenzija koje zapravo definišu stanje.
- Korišćenje cele DP tabele kada je moguća optimizacija na 1D niz.
Kod svakog DP zadatka prvo definiši šta predstavlja jedno stanje. Tek kada jasno znaš značenje stanja, piši prelaze i kod. To je najvažnija navika koju treba razviti za ozbiljne DP probleme.
Resursi i reference
Nedelja 6 — Naprednije dinamičko programiranje (Knapsack i optimizacije)
Ova nedelja je fokusirana na naprednije oblike dinamičkog programiranja, sa posebnim akcentom na Knapsack probleme, različite varijacije i optimizaciju memorije i vremena izvršavanja.
Teme koje treba savladati
- 0/1 Knapsack problem
- Unbounded Knapsack
- Bounded Knapsack (osnovna ideja)
- DP po težini i vrednosti
- Optimizacija memorije (2D → 1D DP)
- Redosled petlji i njegov uticaj na rezultat
- DP nad podnizovima i kombinatornim izborima
Ključni koncept — 0/1 Knapsack
Cilj je maksimizovati vrednost predmeta bez prekoračenja kapaciteta ranca. Svaki predmet se može uzeti najviše jednom.
dp[i][w]
Maksimalna vrednost koristeći prvih i predmeta
uz kapacitet w.
Optimizacija memorije (ključna ideja)
Pošto svako stanje zavisi samo od prethodnog reda, 2D DP se može svesti na 1D niz.
for (int i = 0; i < n; i++) {
for (int w = W; w >= weight[i]; w--) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}
Ako se iteracija vodi unazad (W → 0), dobijamo 0/1 Knapsack. Ako se vodi unapred, prelazimo u unbounded Knapsack.
0/1 vs Unbounded Knapsack
- 0/1 Knapsack: svaki predmet se koristi najviše jednom.
- Unbounded Knapsack: svaki predmet se može koristiti više puta.
- Razlika je u smeru iteracije kroz kapacitet.
DP varijacije koje treba znati
- Knapsack po težini
- Knapsack po vrednosti
- Minimum troška za određenu vrednost
- Broj načina da se postigne suma
Česte greške
- Pogrešan smer petlje (najčešća greška)
- Mešanje 0/1 i unbounded logike
- Korišćenje iste DP vrednosti više puta u istoj iteraciji
- Pogrešno definisano DP stanje
- Prevelika memorija bez potrebe
Predloženi zadaci
- Knapsack — SvetProgramiranja
- AtCoder DP D — Knapsack 1
- AtCoder DP E — Knapsack 2
- LeetCode — Coin Change
- Partition Equal Subset Sum
Plan rada (predlog)
- Implementiraj klasični 2D Knapsack.
- Razumi značenje dp[i][w].
- Prevedi 2D DP u 1D DP.
- Eksperimentiši sa smerom petlji (0/1 vs unbounded).
- Reši Coin Change (broj načina + minimum kovanica).
- Poveži Knapsack sa prethodnim DP problemima.
Studijske napomene
- DP je modelovanje izbora, ne samo implementacija.
- Smer petlje direktno menja matematički model problema.
- Uvek prvo razjasni: da li se elementi mogu ponavljati.
- Optimizacija memorije ne menja logiku problema.
Resursi
Nedelja 7 — Grafovi: predstavljanje, BFS i DFS
Ova nedelja predstavlja ulazak u grafove, jednu od najvažnijih oblasti algoritamskog programiranja. Grafovi se pojavljuju u ogromnom broju takmičarskih zadataka — od jednostavnih pretraga do složenih problema sa ograničenjima.
Fokus je na razumevanju: kako predstaviti graf, kako izvršiti pretragu grafa i kako prepoznati da je neki problem zapravo grafovski.
Osnovni pojmovi
- Čvor (vertex), grana (edge)
- Usmereni i neusmereni grafovi
- Težinski i netežinski grafovi
- Povezane komponente
- Graf kao apstraktni model problema
Predstavljanje grafa
- Lista susedstva — najčešća i najefikasnija (O(V + E))
- Matrica susedstva — jednostavna, ali memorijski skupa (O(V²))
// Lista susedstva (neusmereni graf)
vector<vector<int>> adj(n);
adj[u].push_back(v);
adj[v].push_back(u);
Napomena: Lista susedstva je standard na takmičenjima i koristi se u gotovo svim BFS/DFS zadacima.
DFS — pretraga u dubinu (Depth-First Search)
DFS ide što dublje u graf pre nego što se vrati nazad. Najčešće se implementira rekurzivno i koristi se za:
- Pronalaženje povezanih komponenti
- Detekciju ciklusa
- Obilazak grafa i matrice
- Topološko sortiranje (kasnije)
vector<bool> visited;
void dfs(int u) {
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
BFS — pretraga u širinu (Breadth-First Search)
BFS obilazi graf po nivoima i koristi red (queue). Ključna osobina: u netežinskim grafovima BFS daje najkraći put.
- Najkraći put u netežinskom grafu
- Problemi sa minimalnim brojem koraka
- Graf stanja (state graph)
vector<int> dist(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
Važno: Ako su sve grane jednake težine — BFS je optimalan za najkraći put.
Graf u matrici (rešetka)
Mnogi zadaci nisu eksplicitno dati kao graf, već kao matrica ili lavirint. Svako polje je čvor, a pomeranja su grane.
- Broj ostrva
- Najkraći put u lavirintu
- Širenje (vatra, poplava, infekcija)
Predloženi zadaci za vežbu
- BFS i DFS — SvetProgramiranja
- Broj ostrva — BFS/DFS u matrici
- Najkraći put u lavirintu — BFS
- LeetCode — Number of Islands
- Takprog / Petlja — grafovski zadaci
- Naučiti osnovne pojmove i predstavljanje grafa.
- Implementirati DFS i BFS od nule.
- Vežbati grafove u matrici (4/8 smerova).
- Razlikovati kada koristiti BFS, a kada DFS.
- Rešiti bar 5 grafovskih zadataka.
- Ako se problem može opisati kao „stanja + prelazi“ — verovatno je graf.
- BFS = najmanji broj koraka.
- DFS = struktura, komponente, ciklusi.
- Grafovi su osnova za Dijkstra, DSU i topološko sortiranje.
Resursi
Nedelja 8 — Grafovi (najkraći putevi) + Priority Queue
U ovoj nedelji fokus je na problemima najkraćeg puta u grafu, koji su veoma česti na državnim takmičenjima i SIO. Učenici uče kako da pravilno modeluju realan problem kao graf i kako da izaberu odgovarajući algoritam u zavisnosti od tipa težina na granama.
Poseban akcenat je na algoritmu Dijkstra, kao i na pravilnoj upotrebi priority_queue (prioritetnog reda) iz C++ STL-a, što je česta tačka grešaka kod učenika.
Glavne teme
- Modelovanje problema kao grafa (čvorovi, grane, težine)
- Razlika između neponderisanih i ponderisanih grafova
- BFS kao algoritam za najkraći put u neponderisanom grafu
- Dijkstra algoritam — ideja, invarijante, složenost i implementacija
- Upotreba priority_queue u C++
- Rad sa min-heap strukturom
- Tipične greške početnika: višestruki ulasci u red, pogrešna upotreba
visitedniza, pogrešno poređenje parova
Dijkstra — osnovna ideja
Algoritam u svakom koraku bira čvor sa trenutno najmanjom poznatom udaljenošću i pokušava da poboljša udaljenosti njegovih suseda. Kada se čvor izvuče iz prioritetnog reda sa važećom udaljenošću, ta udaljenost postaje konačna.
Za razliku od BFS-a, ovde se obično ne koristi klasičan visited niz.
Umesto toga proverava se da li je izvučena udaljenost zastarela.
Primer implementacije (C++)
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
vector<vector<pair<int,int>>> graf;
vector<long long> dist;
void dijkstra(int start) {
priority_queue<
pair<long long,int>,
vector<pair<long long,int>>,
greater<pair<long long,int>>
> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // zastareli unos
for (auto [v, w] : graf[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
long long,
a uvek proveri da li je graf usmeren ili neusmeren.
Tipični zadaci
- Najkraći put između dva grada
- Najbrži ili najjeftiniji put
- Grafovi sa težinama
- Lavirinti sa cenama prelaza
- Višestruki upiti iz jednog izvora
- Modelovanje problema gde stanje predstavlja čvor grafa
Predloženi zadaci za vežbu
- SvetProgramiranja — Dijkstra algoritam
- Priority Queue u C++
- CSES — Shortest Routes I
- SPOJ — Easy Dijkstra
- AtCoder — Come Back Quickly
- Takprog / Petlja — grafovski zadaci
- Rešiti najkraći put BFS-om u netežinskom grafu.
- Razumeti zašto BFS ne radi za različite težine.
- Implementirati Dijkstra algoritam.
- Ručno simulirati algoritam na malom grafu.
- Rešiti nekoliko zadataka sa CSES / SPOJ platformi.
- Dijkstra ne radi sa negativnim težinama.
- Složenost: O((V + E) log V).
- Koristi
long longza velike udaljenosti. - Uvek proveri da li je graf usmeren ili neusmeren.
- Ako vidiš „najkraći put“ u neponderisanom grafu, prvo pomisli na BFS.
Nedelja 9 — Teorija brojeva (napredno / olimpijadski nivo)
Ova nedelja predstavlja proširenje osnovnog plana i namenjena je učenicima koji se spremaju za državna takmičenja, SIO i olimpijade. Teorija brojeva je jedna od najčešćih oblasti na višim nivoima takmičenja i zahteva kombinaciju matematičkog razmišljanja i efikasne implementacije.
Akcenat je na razumevanju osobina brojeva, modularne aritmetike i primeni poznatih algoritama kao što su Euklidov algoritam i brza modularna eksponencijacija.
Glavne teme
- Euklidov algoritam — NOD (GCD) i prošireni Euklidov algoritam
- Modularna aritmetika (sabiranje, množenje, modulo svojstva)
- Brza eksponencijacija (
a^b mod m) - Prosti brojevi i testiranje prostosti
- Razlaganje broja na proste činioce
- Najmanji zajednički sadržalac (NZS) i veza sa NOD-om
Važni koncepti za takmičenja
- Zašto direktno računanje često nije moguće (veliki brojevi)
- Rad sa modulom 10⁹+7 i sličnim konstantama
- Prepoznavanje kada je zadatak iz teorije brojeva „skriven“
- Kombinovanje teorije brojeva sa DP-om ili grafovima
- Uloga deljivosti u konstrukciji i analizi rešenja
Primer: Brza modularna eksponencijacija (C++)
long long modexp(long long a, long long b, long long mod) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
Ova tehnika se koristi u velikom broju zadataka — od teorije brojeva do kombinatorike i kriptografije.
Tipični zadaci
- Računanje NOD-a i NZS-a za veliki broj upita
- Provera deljivosti i osobina brojeva
- Rad sa velikim stepenima i modulom
- Zadaci sa prostim brojevima i faktorima
- Kombinacija matematike i implementacije
Predloženi zadaci za vežbu
- SvetProgramiranja — Teorija brojeva (vodič)
- Euklidov algoritam — objašnjenje i primeri
- CSES — Common Divisors
- SPOJ — Extended GCD
- Takprog / Petlja — teorija brojeva
- Modularna aritmetika — detaljno objašnjenje
- Brza eksponencijacija — primeri i primena
Plan rada (predlog)
- Obnoviti osnovna svojstva deljivosti i NOD/NZS.
- Naučiti i implementirati Euklidov algoritam.
- Uvežbati modularnu aritmetiku.
- Implementirati brzu eksponencijaciju.
- Rešiti nekoliko kombinovanih zadataka.
Studijske napomene
- Teorija brojeva zahteva više razmišljanja nego koda.
- Vežbaj prepoznavanje šablona u zadacima.
- Uvek proveri granice ulaza (constraints).
- Ova oblast je česta na olimpijadama i finalnim krugovima.
Resursi
Nedelja 10 — Napredne strukture podataka
Ova nedelja obuhvata napredne strukture podataka koje se često pojavljuju na državnim takmičenjima, SIO i olimpijadama, ali zahtevaju solidnu osnovu iz prethodnih oblasti kao što su DP, grafovi i prioritetni redovi.
Cilj nije samo naučiti implementaciju, već razumeti kada je određena struktura optimalna, kako utiče na složenost i kako se kombinuje sa drugim algoritamskim tehnikama.
- efikasno procesiranje velikog broja upita
- rad sa logaritamskim strukturama
- kombinovanje struktura podataka sa grafovima i DP-om
- optimizacija vremenske složenosti
Glavne teme
- Set / Map — balansirana stabla i hash strukture
- unordered_set / unordered_map — prosečno O(1) pristupanje
- Priority Queue (Heap) — minimum / maksimum elementi
- Fenwick Tree (BIT) — prefiksne sume u O(log n)
- Segment Tree — rad nad intervalima
Napredne strukture podataka se koriste kada običan niz, sortiranje ili linearna pretraga više nisu dovoljno efikasni.
Set i Map — osnovna ideja
Strukture set i map u C++ STL-u zasnovane su na balansiranim stablima
i omogućavaju:
- ubacivanje u O(log n)
- brisanje u O(log n)
- pretragu u O(log n)
set<int> s;
s.insert(5);
s.insert(2);
if (s.count(5)) {
cout << "Postoji";
}
unordered_set i unordered_map su često brži,
ali nemaju sortirane elemente.
Fenwick Tree — osnovna ideja
Fenwick Tree (BIT) omogućava:
- računanje prefiksnih suma
- ažuriranje elemenata
- sve u O(log n)
Koristi se kada postoji veliki broj:
- upita nad segmentima
- izmena elemenata
- online obrada podataka
- broj elemenata manjih od x
- prefiksne sume
- inverzije u nizu
- dinamički upiti
Segmentno stablo — uvod
Segment Tree predstavlja moćnu strukturu za obradu intervala.
Omogućava:
- minimum / maksimum na segmentu
- sume na segmentima
- range update operacije
- napredne lazy propagation tehnike
Detaljne stranice i implementacije za Fenwick i Segment Tree biće postepeno dodavane u narednim verzijama vodiča.
Zašto su ove teme važne?
- Omogućavaju rešavanje problema sa velikim brojem upita.
- Često su razlika između parcijalnog i punog broja poena.
- Kombinuju se sa DP-om, grafovima i teorijom brojeva.
- Pojavljuju se na višim nivoima takmičenja.
Predloženi zadaci i resursi
- Vodič kroz algoritme — SvetProgramiranja
- CP-Algorithms — Fenwick Tree
- CP-Algorithms — Segment Tree
- CSES Problem Set — Range Queries sekcija
- Priority Queue u C++
Plan rada (predlog)
- Obnoviti STL strukture (set, map, priority_queue).
- Razumeti razliku između O(n), O(log n) i O(1).
- Naučiti osnovnu ideju Fenwick stabla.
- Preći uvod u segmentno stablo.
- Vežbati zadatke sa velikim brojem upita.
Kod mnogih zadataka ključ nije komplikovan algoritam, već izbor odgovarajuće strukture podataka.
- Ne preskakati prethodne nedelje — ovo gradivo se nadovezuje na njih.
- Za sada je dovoljno razumeti kada se ove strukture koriste.
- Detaljna implementacija dolazi u sledećim verzijama vodiča.
Nedelja 11 — Geometrija i mešoviti zadaci
Završna nedelja predstavlja prelaz sa pojedinačnih oblasti na rešavanje kompleksnih takmičarskih problema koji kombinuju više tehnika.
Fokus je na algoritamskoj geometriji, modelovanju problema i razvoju takmičarskog načina razmišljanja. Ovakvi zadaci su česti na državnim takmičenjima i SIO jer testiraju razumevanje modelovanja problema, a ne samo poznavanje jedne tehnike.
Geometrijske teme
- Shoelace formula — površina poligona
- Orijentacija tačaka — levo/desno skretanje
- Presek duži — kolinearnost i specijalni slučajevi
- Rastojanje tačke od prave
- Konveksni omotač — osnovna ideja
Zadaci iz geometrije često zahtevaju precizno modelovanje i pažljivo razmišljanje, dok je sama implementacija obično kraća nego kod DP ili grafova. Zato je ključ u pravilnom tumačenju uslova i pažljivom radu sa specijalnim slučajevima.
Shoelace formula
Koristi se za računanje površine prostog poligona čija su temena poznata. Formula koristi koordinate susednih temena i veoma je česta na takmičenjima.
Redosled obilaska temena mora biti pravilan (u smeru kazaljke ili suprotno), jer u suprotnom znak može biti obrnut, ali apsolutna vrednost daje traženu površinu.
Presek duži
Jedan od najpoznatijih geometrijskih problema je da se odredi da li se dve duži seku. Za ovo su ključni orijentacija tačaka, kolinearnost i obrada specijalnih slučajeva.
- orijentacija tačaka
- kolinearnost
- specijalni slučajevi
- dodirivanje krajnjih tačaka
Mešoviti zadaci
Na višim nivoima takmičenja zadaci retko pripadaju samo jednoj oblasti. Vrlo često se kombinuju različite tehnike i upravo tu dolazi do izražaja sposobnost modelovanja problema.
Najčešće kombinacije su:
- grafovi + DP
- kombinatorika + matematika
- geometrija + pretraga
- strukture podataka + grafovi
- DP nad geometrijskim objektima (intervali, segmenti, tačke)
Najvažnije je naučiti da prepoznaš koja oblast i tehnika odgovaraju problemu. Kod mešovitih zadataka najčešće ne pobeđuje najduži kod, već najjasnije modelovanje.
Tipični problemi
- najkraći put sa dodatnim ograničenjima
- brojanje puteva u grafovima
- optimizacija nad segmentima
- kombinovani matematički problemi
- modelovanje stanja
Preporučeni resursi
Plan rada (predlog)
- Obnoviti sve prethodne oblasti.
- Rešavati kombinovane zadatke.
- Vežbati modelovanje problema.
- Raditi simulacije takmičenja.
- Analizirati svoja rešenja i greške.
Takmičarsko programiranje nije samo učenje algoritama, već razvoj načina razmišljanja.
Najveći napredak dolazi kroz:
- kontinuirano rešavanje zadataka
- analizu tuđih rešenja
- upornost i praksu
Nije potrebno naučiti sve napamet. Mnogo je važnije razumeti:
- kako razmišljati o problemu
- kako modelovati stanje
- kako analizirati složenost
- kada koristiti određenu tehniku
Proširenje za nivo olimpijade (napredni učenici)
Sledeće teme nisu obavezne za standardna školska takmičenja, ali predstavljaju veoma važan deo pripreme za državna takmičenja višeg nivoa, SIO finale, republičke olimpijade i IOI stil zadataka.
Ove oblasti zahtevaju ozbiljno iskustvo u rešavanju zadataka, dobro poznavanje osnovnih algoritama i sposobnost kombinovanja više tehnika u jednom problemu.
Napredni graf algoritmi
MST — Minimalno razapinjuće stablo
- Prim algoritam
- Kruskal algoritam
- Disjoint Set Union (DSU)
- Interno: MST — Prim (u izradi)
- Interno: MST — Kruskal (u izradi)
Topološko sortiranje
- DAG grafovi
- zavisnosti
- DP na grafovima
- Interno: Topološko sortiranje (u izradi)
Snažno povezane komponente (SCC)
- Kosaraju
- Tarjan
- kompresija grafa
- Spoljno: CP-Algorithms — SCC
Bellman–Ford
- negativne težine
- detekcija ciklusa
- Spoljno: CP-Algorithms — Bellman–Ford
Napredno dinamičko programiranje
DP na grafovima (DAG DP)
Kombinuje topološko sortiranje i dinamičko programiranje.
- najkraći / najduži put u DAG-u
- brojanje puteva
- optimizacija zavisnosti
- Interno: DP na DAG-ovima
- Interno (OBAVEZNO): Najduži put u DAG-u
DP sa bitmaskama
- TSP
- podskupovi
Napredne strukture podataka
- Segmentno stablo
- Fenwick (BIT)
- kombinovane strukture
Segmentno stablo
- Interno: Segmentno stablo (u izradi)
Fenwick (BIT)
- Interno: Fenwick stablo
Napomena o izvorima zadataka
Svi linkovi vode ka izvorima zadataka (LeetCode, GeeksforGeeks, Petlja) ili ka lokalnim rešenjima na SvetProgramiranja. Kod i detaljna objašnjenja na lokalnim stranicama su originalna i prilagođena za edukativnu upotrebu.
|
Prethodno
|< Priprema za državna takmičenja |
Sledeće
Interaktivni Algoritmi >| |