Priprema za državno takmičenje i SIO iz informatike

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

• TAČAN IZRAZ — kombinatorika i rekurzija.
• Permutacije i podskupovi
• Brojanje načina (Fibonacci varijanta)
• Hanojske kule
• LeetCode — Permutations
• Generisanje kombinatornih objekata

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

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.

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

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.

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.

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

Plan rada (predlog)

1. Analiziraj Fibonacci rekurziju i pronađi ponavljanje podproblema.
2. Izmeri broj poziva funkcije za n=30 i n=40.
3. Implementiraj memoizaciju i uporedi broj poziva.
4. Pređi na bottom-up tabulaciju.
5. Optimizuj memoriju sa O(n) na O(1).
6. Reši Frog 1 koristeći isti princip.
7. Počni prve Knapsack i Coin Change zadatke.
8. 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

• CP-Algorithms — Intro to DP
• USACO Guide — Intro to DP
• AtCoder — Educational DP Contest
• Uvod u dinamičko programiranje — SvetProgramiranja

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.

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

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

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)

1. Počni sa jednostavnim DP problemima nad matricama.
2. Ručno nacrtaj DP tabelu za male ulazne primere.
3. Analiziraj kako se formiraju prelazi između stanja.
4. Pređi na LCS i probleme nad stringovima.
5. Implementiraj Edit Distance.
6. Pokušaj optimizaciju memorije na dva reda.
7. 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.

Resursi i reference

• Vodič kroz algoritme — SvetProgramiranja
• DP — Longest Common Subsequence
• DP u matrici — maksimalna suma puta
• CP-Algorithms — Dynamic Programming
• USACO Guide — Dynamic Programming

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]

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]);
    }
}

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)

1. Implementiraj klasični 2D Knapsack.
2. Razumi značenje dp[i][w].
3. Prevedi 2D DP u 1D DP.
4. Eksperimentiši sa smerom petlji (0/1 vs unbounded).
5. Reši Coin Change (broj načina + minimum kovanica).
6. 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

• CP-Algorithms — Knapsack
• USACO Guide — Knapsack DP
• Vodič kroz algoritme — SvetProgramiranja

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

Resursi

• Vodič kroz algoritme — SvetProgramiranja
• CP-Algorithms — BFS
• CP-Algorithms — DFS

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 visited niza, 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});
            }
        }
    }
}
  

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

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)

1. Obnoviti osnovna svojstva deljivosti i NOD/NZS.
2. Naučiti i implementirati Euklidov algoritam.
3. Uvežbati modularnu aritmetiku.
4. Implementirati brzu eksponencijaciju.
5. 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

• Vodič kroz algoritme — SvetProgramiranja
• Teorija brojeva — SvetProgramiranja
• CP-Algorithms — Euclidean Algorithm
• CP-Algorithms — Modular Arithmetic

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.

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

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";
}
  

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

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

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)

1. Obnoviti STL strukture (set, map, priority_queue).
2. Razumeti razliku između O(n), O(log n) i O(1).
3. Naučiti osnovnu ideju Fenwick stabla.
4. Preći uvod u segmentno stablo.
5. Vežbati zadatke sa velikim brojem upita.

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

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.

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)

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

• Algoritmi — SvetProgramiranja
• CP-Algorithms — Geometry
• USACO Guide
• CSES Problem Set

Plan rada (predlog)

1. Obnoviti sve prethodne oblasti.
2. Rešavati kombinovane zadatke.
3. Vežbati modelovanje problema.
4. Raditi simulacije takmičenja.
5. Analizirati svoja rešenja i greške.

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

• CP-Algorithms — Bitmask DP

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.