PRIPREMA ZA DRŽAVNO TAKMIČENJE I SIO IZ INFORMATIKE
Plan pripreme za državna takmičenja i SIO (8. razred & 1. godina srednje škole) — 11 nedelja
Ovaj plan je namenjen naprednim učenicima koji se pripremaju za državno takmičenje i SIO iz informatike. Pretpostavlja se da učenici već imaju osnovno iskustvo sa:
- rekurzijom i rekurzivnim razmišljanjem
- kombinatorikom (permutacije, kombinacije, podskupovi)
- backtracking zadacima
- osnovnim dinamičkim strukturama (nizovi, liste)
Plan je koncipiran tako da:
- ✔ sistematično uvede dinamičko programiranje (DP),
- ✔ poveže DP sa graf algoritmima,
- ✔ postepeno uvede napredne strukture podataka,
- ✔ omogući prelazak ka olimpijskom nivou za zainteresovane učenike.
Osnova za ponavljanje i praksu
Pre početka ovog plana, preporučuje se ponavljanje sledećih oblasti kroz postojeće materijale na sajtu:
-
Priprema za državno takmičenje — SvetProgramiranja
— zbirka zadataka i objašnjenja srednje težine. - Algoritmi: Euklidov algoritam (NZD), Eratostenovo sito, maksimalna suma podniza.
- Rekurzija i kombinatorika: permutacije, kombinacije, generisanje podskupova.
- Backtracking: zadaci sa takmičenja („Puž“, „Tačan izraz“).
- Sortiranje i binarna pretraga: osnovne implementacije i tipični zadaci.
- Takmičarski zadaci: problemi sa okružnih i državnih takmičenja (npr. „Seča drva“).
Napomena: Ovi materijali su odlični za ponavljanje i konsolidaciju znanja. U ovom planu fokus će biti na novim konceptima: dinamičkom programiranju, graf algoritmima i naprednim strukturama podataka, koje su ključne za uspeh na SIO i državnom nivou.
Obavezno predznanje (pre početka plana)
Sledeće strukture podataka se ne obrađuju kao posebne nedelje, ali se stalno koriste u skoro svim oblastima koje slede (dinamičko programiranje, grafovi, interaktivni zadaci).
-
Stek (Stack)
— osnova rekurzije, DFS-a, evaluacije izraza i backtracking zadataka.
Spoljni resurs: CP-Algorithms — Stack -
Red (Queue)
— osnova BFS-a, simulacija, obrade događaja i stanja.
Spoljni resurs: CP-Algorithms — Queue
Napomena: Ako učenik nema sigurno razumevanje steka i reda, grafovi i DP će biti znatno teži za savladavanje.
- □ Pročitaj kompletan plan jednom da stekneš pregled.
- □ Fokusiraj se samo na trenutnu nedelju.
- □ Linkovi vode ka detaljnim lekcijama — plan je mapa, ne udžbenik.
-
Nedelja 1 — Ponavljanje rekurzije i kombinatorike
- Generisanje permutacija, kombinacija, svih podskupova.
- Brojanje rešenja sa dodatnim ograničenjima (npr. određena suma).
- Rekurzija sa memoizacijom (prvi korak ka DP).
- Preporučeni zadaci: SvetProgramiranja — Permutacije, Kombinacije, „Tačan izraz“.
Resursi: CP-Algorithms (recursion), GeeksforGeeks (recursion problems), Petlja zadaci.
-
Nedelja 2 — Priprema za SIO: interaktivni i vremenski zavisni zadaci
Ova nedelja je fokusirana na tip zadataka koji se često pojavljuju na SIO: interaktivni zadaci i zadaci čije stanje zavisi od vremena/dana (DP kroz dane). Proučićemo kako dizajnirati pitanja i odgovore, kako simulirati grader lokalno, kao i kako formulirati DP stanja za vremenski zavisne probleme.
Zašto ova tema?
- Mnogi takmičarski zadaci zahtevaju rad sa interakcijom ili sa nizom dnevnih prelaza (npr. investicije, sekvencijalne odluke).
- Na SIO su često prisutne varijante gde je važno pravilno modelovati stanje i izbeći dupliranje rada.
- Stranica sa primerima i zadacima: Interaktivni algoritmi — SvetProgramiranja.
Teme i koncepti koje ćemo pokriti (konkretno za SIO):
- Interaktivni protokol: kako pravilno formulisati upite i obraditi odgovore; lokalna simulacija (grader / Lgrader).
- Robustne strategije: kako postupati kada dobijamo neodređene ili nasumične odgovore (npr. Džoker koji vraća min ili max) — majority voting, probabilistička verifikacija.
- DP kroz dane: modelovanje stanja kao
dp[dan][stanje](primer: investicije u kriptovalute — maksimalizacija BTC kroz N dana). - Prefiks-sume i deljivost: tehnika za brojanje podsekvenci sa sumom deljivom sa y (korisno za zadatke o kofama / pakovanju).
- String manipulacija i rad sa ulazom/izlazom: pažnja na terminatore, sigurni pozivi za učitavanje (fgets vs scanf), ispravno prikazivanje rezultata.
- Praktikum: pisanje lokalnih stubova (stubs) za
query/answeri testiranje strategija pre slanja rešenja.
Konkrektni zadaci / primeri koje obrađujemo (i koje treba rešavati ove nedelje)
- Igra sa Džokerom — interaktivni zadatak gde Džoker vraća ili minimum ili maksimum segmenta. (strategije: konstrukcija diskriminativnih nizova, probabilističko testiranje kandidata)
- Maksimizacija BTC kroz razmenu (DP kroz dane) — modelovanje stanja
dp[day][currency], prelazi pomoću dnevnih matrica kursa. - Deljivost podsekvenci (kofe / pakovanje) — prefiks-sume i brojanje parova ostataka (praktičan linearni/kvazi-linearni pristup).
- Interaktivni primeri sa stranice — pregled zadataka i primera: Interaktivni algoritmi — SvetProgramiranja.
Preporučeni resursi (Nedelja 2)
- SvetProgramiranja — Interaktivni algoritmi (primeri i objašnjenja)
- Naš primer: rešenje i uputstvo za „Igra sa Džokerom“ (interaktivni pristup + demo kod).
- Naš primer: „Maksimizacija BTC kroz razmenu kriptovaluta“ (DP kroz dane) — kod i objašnjenje.
- CP-Algorithms — sekcije o binarnoj pretrazi i DP-u.
Preporučeni zadaci za vežbu (Nedelja 2)
- Svi zadaci sa stranice Interaktivni algoritmi — praktikujte lokalnu simulaciju i verifikaciju strategija.
- Zadatak o kofama / deljivosti (prefiks-sume) — vežbajte optimizovano prebrojavanje podsekvenci.
- DP primer: implementirati i testirati rešenje za N dana / K valuta (iskustveno testiranje na različitim N, K i skokovima kursa).
- Eksperimenti: napišite Lgrader verzije svojih rešenja i testirajte ih protiv slučajnih i ručno konstruisanih testova.
Praktični savet za vežbu ove nedelje
- Za svaki interaktivni zadatak najpre napišite lokalni grader/stub (funkcije
queryianswer) kako biste mogli da simulirate i debug-ujete strategiju. - Kod interaktivnih strategija zabeležite koliko upita koristite; probajte da optimizujete broj upita pre nego što povećate kompleksnost strategije.
- Za DP kroz dane napravite jednostavnu implementaciju (O(N·K²)), testirajte na manjem skupu, pa eventualno optimizujte memoriju ili prelaze ako je potrebno.
- Redovno dokumentujte hipoteze i eksperimentisane konstrukcije nizova (što je radilo, šta nije) — to pomaže pri pripremi za SIO i pri brzom ispravljanju grešaka.
Napomena: Sadržaj Nedelje 2 je usklađen sa zadacima koje si postavio i sa primerima na stranici Interaktivni algoritmi. Ako želiš, mogu da ubacim direktne linkove na konkretne datoteke/stranice za svaki od gore navedenih primera (npr. direktan link na „Igra sa Džokerom“, „Maksimizacija BTC“ i „Deljivost podsekvenci“) — pošalji mi URL-ove tih stranica i ja ću ih umetnuti u ovu listu.
-
Nedelja 3 — Backtracking (napredni zadaci)
- N-Queens (varijacije i optimizacija).
- Sudoku solver, Knight's Tour, reči u mreži (word search).
- Kombinacije i permutacije sa zabranjenim pozicijama.
- Preporučeni zadaci: SvetProgramiranja — „Puž“, Sudoku primeri.
Resursi: GeeksforGeeks backtracking, LeetCode N-Queens, praktični primeri sa Petlje.
-
Nedelja 4 — Uvod u dinamičko programiranje (DP)
- Koncepti: preklapanje podproblema, optimalna podstruktura.
- Fibonacci: rekurzija vs. memoizacija vs. tabulacija.
- Razlika između memoizacije (top-down) i tabulacije (bottom-up).
- Jednostavni primeri za vežbu: broj načina, minimum/max.
Resursi: Uvod u dinamičko programiranje — SvetProgramiranja. (osnovni pregled i primeri)
-
Nedelja 5 — Klasični DP zadaci
- LCS (Longest Common Subsequence) — analiza stanja i tabulacija.
- LIS (Longest Increasing Subsequence) — (resurs i objašnjenja u vodiču za pripremu; Priprema za državno takmičenje).
- Minimum broj kovanica (Coin change) — varijante: minimum i broj načina (Subset Sum / Coin Change primeri).
Resursi: linkovi iznad (LCS, Subset Sum), plus CP-Algorithms i AtCoder za dodatne zadatke.
-
Nedelja 6 — Napredniji DP i knapsack
- Knapsack 0/1 — tabulacija i optimizacija memorije.
- DP na matricama: maksimalna suma puta, broj putanja sa preprekama.
- DP sa kompresijom dimenzije i prelaskom sa stanja na stanje.
Resursi: Knapsack (0/1) — SvetProgramiranja i AtCoder / Codeforces primeri.
-
Nedelja 7 — Grafovi: predstavljanje i pretrage
- BFS koristi red, DFS koristi stek / rekurziju — očekuje se da su ove strukture poznate.
- Lista susedstva, matrica susedstva; efikasne reprezentacije.
- DFS i BFS — pronalaženje puteva, komponente povezanosti.
- Primenjeni zadaci: broj ostrva, povezane komponente u matrici.
Resursi: BFS i DFS — SvetProgramiranja.
-
Nedelja 8 — Grafovi: najkraći putevi i varijante
- BFS za najkraći put u neprioritetnim grafovima (jednaka težina).
- Dijkstra — najkraći putevi (osnovna implementacija, priority queue primena).
- Varijante: težinski grafovi, transformacije stanja (modelovanje problema kao graf).
Resursi: Dijkstra — SvetProgramiranja, plus praktične vežbe iz arhive zadataka.
-
Nedelja 9 — Teorija brojeva
- Eratostenovo sito, proste i faktorizacija.
- Euklidov algoritam (GCD) i prošireni Euclid.
- Modularna aritmetika, brzo potenciranje po modulu.
Resursi: Eratostenovo sito i Euklid (linkovi gore).
-
Nedelja 10 — Napredne strukture podataka
Sledeće lekcije su planirane i biće dodate. Linkovi služe kao orijentir za gradivo koje je važno na takmičenjima.
- Set / Map (hash i stablo) — u izradi
- Prioritetni red (Heap) — u izradi
- Fenwick (BIT) — u izradi
- Uvod u segmentno stablo — u izradi
Napomena: ove teme su u vodiču označene kao planirane — čim napraviš stranice, ja ću ih odmah ubaciti kao aktivne linkove.
-
Nedelja 11 — Geometrija i mešoviti zadaci
- Shoelace formula (površina poligona), rastojanje tačke od prave.
- Provera preseka duži, osnovni konveksni omotač (uvod).
- Mešoviti zadaci koji kombinuju DP, grafove i kombinatoriku.
Resursi: opšti algoritamski vodič: Algoritmi — SvetProgramiranja (geometrija i primeri), plus CP-Algorithms za detaljne tutorijale.
Preporučeni sajtovi za vežbanje i učenje
- Petlja — srpski zadaci i zbirke, odlična baza za školsku pripremu.
- Codeforces — takmičarski zadaci, filter po temama i težini.
- AtCoder — kvalitetni contest-ovi i DP zadaci.
- CP-Algorithms — teorija i primeri (grafovi, DP, strukture).
- USACO Guide — strukturisani vodič i kolekcije zadataka po temama.
- GeeksforGeeks — objašnjenja i praktični primeri.
- LeetCode — vežba za specifične probleme (grafovi, DP, backtracking).
- Svet Programiranja — zbirke zadataka sa takmičenja, primeri algoritama.
Dodatni resursi (na srpskom jeziku)
- Priprema za državno takmičenje — Svet programiranja — detaljna objašnjenja i primeri na srpskom jeziku.
- Petlja — Zbirke i materijali za takmičenja — zvanični materijali i zadaci za pripremu državnog takmičenja.
- Takprog — Petlja — zvanična stranica takmičenja (osnovne i srednje škole), vesti, rezultati, arhiva zadataka.
- DMS — Društvo matematičara Srbije (dms.rs) — arhiva zadataka i zvanične objave za takmičenja iz matematike i informatike.
- MatF — Programiranje 1 (materijali i zbirke zadataka) — korisni univerzitetski materijali i zbirke zadataka za dublje razumevanje.
Preporučeni pristup (metodologija rada)
- Ponavljanje teorije kratko pre vežbe (15–20 min), potom ciljane zadatke 1–2 h.
- Za DP: uvek prvo pokušati rekurzivno + memoizacija pa preći na tabulaciju.
- Za svaki zadatak — analizirati kompleksnost i moguće optimizacije.
- Raditi takmičarske simulacije (timed contests) jednom nedeljno.
Nedelja 1 — Ponavljanje rekurzije i kombinatorike
Cilj nedelje: razumeti rekurzivni tok i naučiti kako se problemi prebacuju iz čistog generisanja u efikasno brojanje pomoću memoizacije.
Ova nedelja je posvećena osvežavanju i produbljivanju znanja iz rekurzije i kombinatorike. Cilj: razumeti rekurzivnu strukturu, naučiti sistematsko generisanje permutacija/kombinacija/podskupova i uvesti memoizaciju kao prvi korak ka DP. Kao klasičan primer rekurzije radi se Hanojske kule.
Teme i koncepti:
- Rekurzija: baza, rekurzivni poziv, složenost.
- Kombinatorika: permutacije, kombinacije, podskupovi, binomni koeficijent.
- Brojanje rešenja sa ograničenjima (npr. ciljna suma).
- Rekurzija sa memoizacijom (top-down DP).
- Backtracking u kombinatorici (generisanje sa ograničenjima).
- Hanojske kule: rekurzivna formulacija, ispis poteza i analiza broja poteza (2^n − 1).
Preporučeni online resursi (Nedelja 1):
- CP-Algorithms — Generating combinations
- GeeksforGeeks — Recursion
- SvetProgramiranja — Kombinatorika (primeri)
- Petlja — Zbirka2 (pregled i zadaci)
- GeeksforGeeks — Tower of Hanoi
- Wikipedia — Tower of Hanoi
Predloženi zadaci za vežbu (konkretni linkovi — Nedelja 1)
- TAČAN IZRAZ — SvetProgramiranja — generisanje i provera kombinacija operacija (kombinatorika + backtracking).
- Permutacije / Podskupovi — SvetProgramiranja
- Petlja — Aritmetički trougao (Zbirka2) — originalni tekst zadatka na Petlji
- Rešenje — Aritmetički trougao — analiza i objašnjenje rešenja na sajtu Svet programiranja
- Rešenje — Problem "Hanojske kule" — analiza i objašnjenje rešenja na sajtu Svet programiranja
- Petlja — Maksimalni zbir na putu kroz matricu (Zbirka2)
- SvetProgramiranja — Maksimalan zbir na putu kroz matricu (rešenje) — detaljno objašnjenje i implementacija DP rešenja
- Petlja — Brojanje kombinatornih objekata / DP primeri (Zbirka2)
- LeetCode — Permutations
Preporučeni pristup u vežbi (Nedelja 1):
- Počni od malih instanci (n ≤ 5–6) da se razume rekurzivni tok.
- Za zadatke brojanja uvoditi memoizaciju i uporediti rezultate i vremena.
- Analizirati složenost (broj generisanih rešenja, memorija).
Primer naprednog backtracking-a: Sudoku koristi istu ideju kao kombinatorni zadaci, ali sa dodatnim ograničenjima (pruning).
// Simple Sudoku solver using backtracking (C++)
// Input: 9x9 board with 0 for empty cells. Prints solved board if solvable.
#include <iostream>
#include <vector>
using namespace std;
bool is_safe(vector<vector<int>>&board, int r, int c, int val){
for(int i=0;i<9;i++){
if(board[r][i]==val) return false;
if(board[i][c]==val) return false;
int br = (r/3)*3 + i/3;
int bc = (c/3)*3 + i%3;
if(board[br][bc]==val) return false;
}
return true;
}
bool solve(vector<vector<int>&board){
for(int r=0;r<9;r++){
for(int c=0;c<9;c++){
if(board[r][c]==0){
for(int val=1; val<=9; val++){
if(is_safe(board, r, c, val)){
board[r][c]=val;
if(solve(board)) return true;
board[r][c]=0;
}
}
return false; // no valid number found
}
}
}
return true; // solved
}
int main(){
vector<vector<int>> board(9, vector<int>(9));
// Read 9x9 integers (0 for empty)
for(int i=0;i<9;i++) for(int j=0;j<9;j++) cin >> board[i][j];
if(solve(board)){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
cout << board[i][j] << (j==8? '\\n' : ' ');
}
}
} else {
cout << "No solution exists\\n";
}
return 0;
}
Nakon što smo u Nedelji 1 naučili kako da modelujemo stanje i rekurzivne prelaze, u Nedelji 2 prelazimo na zadatke gde se stanje menja tokom vremena ili zavisi od odgovora sistema — što je čest scenario na SIO.
Nedelja 2 — Priprema za SIO: interaktivni i vremenski zavisni zadaci
Ova nedelja je fokusirana na tip zadataka koji se često pojavljuju na SIO: interaktivni zadaci i zadaci čije stanje zavisi od vremena/dana (DP kroz dane). Proučićemo kako dizajnirati pitanja i odgovore, kako simulirati grader lokalno, kao i kako formulirati DP stanja za vremenski zavisne probleme.
Zašto ova tema?
- Mnogi takmičarski zadaci zahtevaju rad sa interakcijom ili sa nizom dnevnih prelaza (npr. investicije, sekvencijalne odluke).
- Na SIO su često prisutne varijante gde je važno pravilno modelovati stanje i izbeći dupliranje rada.
- Stranica sa primerima i zadacima: Interaktivni algoritmi — SvetProgramiranja.
Teme i koncepti koje ćemo pokriti (konkretno za SIO):
- Interaktivni protokol: kako pravilno formulisati upite i obraditi odgovore; lokalna simulacija (grader / Lgrader).
- Robustne strategije: kako postupati kada dobijamo neodređene ili nasumične odgovore (npr. Džoker koji vraća min ili max) — majority voting, probabilistička verifikacija.
- DP kroz dane: modelovanje stanja kao
dp[dan][stanje](primer: investicije u kriptovalute — maksimalizacija BTC kroz N dana). - Prefiks-sume i deljivost: tehnika za brojanje podsekvenci sa sumom deljivom sa y (korisno za zadatke o kofama / pakovanju).
- String manipulacija i rad sa ulazom/izlazom: pažnja na terminatore, sigurni pozivi za učitavanje (fgets vs scanf), ispravno prikazivanje rezultata.
- Praktikum: pisanje lokalnih stubova (stubs) za
query/answeri testiranje strategija pre slanja rešenja.
Konkrektni zadaci / primeri koje obrađujemo (i koje treba rešavati ove nedelje)
- Igra sa Džokerom — interaktivni zadatak gde Džoker vraća ili minimum ili maksimum segmenta. (strategije: konstrukcija diskriminativnih nizova, probabilističko testiranje kandidata)
- Maksimizacija BTC kroz razmenu (DP kroz dane) — modelovanje stanja
dp[day][currency], prelazi pomoću dnevnih matrica kursa. - Deljivost podsekvenci (kofe / pakovanje) — prefiks-sume i brojanje parova ostataka (praktičan linearni/kvazi-linearni pristup).
- Interaktivni primeri sa stranice — pregled zadataka i primera: Interaktivni algoritmi — SvetProgramiranja.
Preporučeni resursi (Nedelja 2)
- SvetProgramiranja — Interaktivni algoritmi (primeri i objašnjenja)
- Naš zajednički primer: rešenje i uputstvo za „Igra sa Džokerom“ (interaktivni pristup + demo kod).
- Naš primer: „Maksimizacija BTC kroz razmenu kriptovaluta“ (DP kroz dane) — kod i objašnjenje.
- CP-Algorithms — sekcije o binarnoj pretrazi i DP-u (kao pomoć pri formulisanju stanja).
Preporučeni zadaci za vežbu (Nedelja 2)
- Svi zadaci sa stranice Interaktivni algoritmi — praktikujte lokalnu simulaciju i verifikaciju strategija.
- Zadatak o kofama / deljivosti (prefiks-sume) — vežbajte optimizovano prebrojavanje podsekvenci.
- DP primer: implementirati i testirati rešenje za N dana / K valuta (iskustveno testiranje na različitim N, K i skokovima kursa).
- Eksperimenti: napišite Lgrader verzije svojih rešenja i testirajte ih protiv slučajnih i ručno konstruisanih testova.
Praktični savet za vežbu ove nedelje
- Za svaki interaktivni zadatak najpre napišite lokalni grader/stub (funkcije
queryianswer) kako biste mogli da simulirate i debug-ujete strategiju. - Kod interaktivnih strategija zabeležite koliko upita koristite; probajte da optimizujete broj upita pre nego što povećate kompleksnost strategije.
- Za DP kroz dane napravite jednostavnu implementaciju (O(N·K²)), testirajte na manjem skupu, pa eventualno optimizujte memoriju ili prelaze ako je potrebno.
- Redovno dokumentujte hipoteze i eksperimentisane konstrukcije nizova (što je radilo, šta nije) — to pomaže pri pripremi za SIO i pri brzom ispravljanju grešaka.
Napomena: Sadržaj Nedelje 2 je usklađen sa zadacima koje si postavio i sa primerima na stranici Interaktivni algoritmi. Ako želiš, mogu da ubacim direktne linkove na konkretne datoteke/stranice za svaki od gore navedenih primera (npr. direktan link na „Igra sa Džokerom“, „Maksimizacija BTC“ i „Deljivost podsekvenci“) — pošalji mi URL-ove tih stranica i ja ću ih umetnuti u ovu listu.
Nedelja 3 — Backtracking (napredni zadaci)
Cilj nedelje: savladati sistematsko pretraživanje prostora rešenja, naučiti kako se uvode ograničenja (pruning) i prepoznati zadatke gde je backtracking jedino ili najprirodnije rešenje.
U ovoj nedelji obrađuju se napredniji zadaci iz oblasti backtracking (bektreking) i grube sile. Ovi algoritmi predstavljaju sistematsko pretraživanje svih mogućih rešenja nekog problema, uz odbacivanje onih koja ne zadovoljavaju uslove.
Zadatke ove vrste često nalazimo u kombinatornim problemima, kao što su slagalice, rasporedi, postavljanje figura, sudoku i drugi problemi gde se traži ispunjavanje preciznih uslova.
Backtracking se može posmatrati kao rekurzija + pametna provera uslova. U odnosu na brute-force, ključna razlika je u ranom odbacivanju loših grana pretrage.
Glavne teme:
- Uvod u backtracking (princip rada, drvo odluka)
- Razlika između brute-force i backtracking pristupa
- Generisanje permutacija i kombinacija sa ograničenjima
- Problemi sa ograničenjima: Sudoku, N-Queens, lavirint, puž
Predloženi zadaci za vežbu (konkretni linkovi — Nedelja 3)
- LeetCode — N-Queens
- SvetProgramiranja — N kraljica — lokalno rešenje sa objašnjenjem algoritma i implementacijom.
- Analiza 5 rešenja problema N kraljica — SvetProgramiranja — poređenje više pristupa: osnovni backtracking, optimizacija dijagonalama, memoizacija i heuristički min-conflicts.
- LeetCode — Sudoku Solver
- Knight's Tour — GeeksforGeeks — klasičan backtracking zadatak (obilazak konja).
- Knight's Tour (Obilazak konja) — lokalno rešenje
- Word Search — LeetCode — DFS + backtracking u mreži.
- Reči u mreži — lokalno rešenje (SvetProgramiranja)
- Puž — SvetProgramiranja — primer backtracking-a sa simulacijom kretanja.
- SvetProgramiranja — Backtracking i gruba sila (primeri)
- Rešavač Sudokua — detaljno objašnjenje
- Takprog / Petlja — arhiva zadataka
Savet: Kod svakog zadatka jasno definiši:
• stanje (šta trenutno znaš),
• izbor (šta pokušavaš),
• uslov prekida i
• uslov validnosti.
To je univerzalna šema za sve backtracking probleme.
Predloženi domaći zadaci (SvetProgramiranja & Petlja)
- Zadatak 15 — Tačan izraz — kombinatorika i rekurzija, generisanje svih izraza koji zadovoljavaju uslov.
- Permutacije i podskupovi — SvetProgramiranja — generisanje svih permutacija i podskupova niza.
- Brojanje načina popunjavanja niza — Petlja — Fibonacci varijanta: koliko načina postoji da se popune koraci od 1 ili 2 (brojanje načina / dekodiranje).
- Generisanje kombinatornih objekata (permutacije/kombinacije/varijacije) — Takprog / Petlja — praktična kolekcija primera uključujući N-Queens stil zadataka i backtracking pristupe.
- Sudoku solver (rekurzivni pristup) — SvetProgramiranja — jednostavnija mreža za početak, učenje backtracking tehnike.
- Generisanje kombinacija k elemenata iz n — Takprog / Petlja — praktična vežba kombinatorike (k / n kombinacije i podskupovi).
Napomena: Preporučuje se prvo rešavati zadatke sa manjim veličinama (n ≤ 5–6) da se razume osnovna rekurzivna logika, a zatim postepeno povećavati kompleksnost.
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 radila presporo, tako što pamti rezultate već rešenih podproblema i koristi ih ponovo.
Glavni koncepti
- Preklapanje podproblema — isti podproblemi se pojavljuju više puta kod rekurzivnog rešenja; umesto ponovnog izračunavanja, rezultate čuvamo.
- Optimalna podstruktura — optimalno rešenje problema može se izgraditi iz optimalnih rešenja njegovih podproblema.
- Razumevanje kako prepoznati stanje (state) i prelaz (transition) — ključne ideje pri osmišljavanju DP-a.
DP šablon razmišljanja:
1) Definiši stanje (dp[...])
2) Odredi bazne slučajeve
3) Napiši prelaze
4) Izaberi redosled računanja (top-down ili bottom-up)
Fibonacci kao uvodna ilustracija
Fibonacci je odličan primer da se pokažu razlike između: rekurzija (eksponencijalna), memoizacija (top-down) i tabulacija (bottom-up).
1) Rekurzivno (bez DP)
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
Brzo raste broj poziva — vreme eksponencijalno (2^n) zbog ponavljanja istih podproblema.
2) Memoizacija — top-down
#include <vector>
using namespace std;
vector<int> memo;
int fib_memo(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib_memo(n-1) + fib_memo(n-2);
return memo[n];
}
// Inicijalizacija: memo.resize(n+1, -1);
Rekurzivna logika ostaje, ali rezultat svakog stanja čuvamo u tabeli — složenost postaje O(n).
3) Tabulacija — bottom-up
int fib_tab(int n) {
if (n <= 1) return n;
vector<int> dp(n+1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
// Memorija se može optimizovati na O(1) koristeći samo dve promenljive.
Radi iterativno, popunjava se tabela od najmanjih ka većim stanjima — takođe O(n) vreme i O(n) memorije.
Memoizacija vs. Tabulacija — kratka razlika
- Memoizacija (top-down): počinjemo od originalnog problema, rekurzivno idemo prema podproblemima i čuvamo rezultate.
- Tabulacija (bottom-up): identifikujemo redosled podproblema i iterativno popunjavamo DP tabelu od najjednostavnijih stanja naviše. Bolja kontrola memorije i često brže u konstantama.
Jednostavni primeri za vežbu (ideje)
- Broj načina (Climbing Stairs / Penjanje stepenicama) — koliko načina da se dođe do cilja
- Minimum / maksimum (Min Path / Maksimalna suma) — najmanji trošak prelaska, maksimalna suma podniza
- Coins / ways to make sum (Novčanice / načini da se složi suma) — koliko načina da se složi suma datim novčanicama
Predloženi zadaci za vežbu
Napomena: AtCoder DP (A–Z) je jedan od najboljih setova za sistematsko učenje DP-a — zadaci su poređani po težini i idejama.
- Prvi deo: AtCoder DP A — Frog 1 (Žaba 1): pređi stepenice sa minimalnim troškom (link)
- Drugi deo: Climbing Stairs (Penjanje stepenicama) — prvo rekurzija, pa memoizacija, pa tabulacija
- Treći deo: Knapsack (0/1) — maksimizacija vrednosti sa ograničenjem težine
- Četvrti deo: Coin Change (Promena novca) — minimum kovanica / broj načina
- Peti deo: LCS — longest common subsequence (Najduži zajednički podniz)
Plan rada (predlog)
- Prvi deo: Upoznaj pojmove preklapanje podproblema i optimalna podstruktura. Analiziraj Fibonacci rekurzivno.
- Drugi deo: Implementiraj Fibonacci sa memoizacijom (top-down). Mere vremena/poziva za n=30/35 i uporedi sa čistom rekurzijom.
- Treći deo: Implementiraj Fibonacci tabulacijom (bottom-up). Optimizuj memoriju na O(1).
- Četvrti deo: Počni sa jednostavnim zadacima: Climbing Stairs / Frog 1 — prvo rekurzija, pa memoizacija, pa tabulacija.
- Peti deo: Knapsack (0/1) — prvo razmišljanje o stanju dp[i][w], pa implementacija bottom-up i/ili top-down.
- Šesti deo: Coin Change — broj načina i minimum kovanica, pazi na redosled iteracija.
- Sedmi deo: Pregled i rešavanje 3-5 zadataka iz AtCoder Edu DP (A–I), pogledaj editoriale i uporedi top-down/tabulacija rešenja.
Studijske napomene i trikovi
- Prepoznaj DP: rekurzija sa ponavljajućim istim parametrima.
- Definicija state — broj parametara i njihova značenja.
- Za count-type problema koristi tip podatka sa dovoljnim opsegom (long/BigInt).
- Beleži prelaze i podeli razmišljanje na: definicija stanja, baza, prelazi, redosled popunjavanja.
Resursi i reference
Nedelja 5 — Dinamičko programiranje sa više dimenzija (2D / 3D DP)
Ako ti je potreban širi kontekst i mapa oblasti, pogledaj Vodič kroz algoritme — SvetProgramiranja, gde su dinamičko programiranje i strukture podataka povezani sa grafovima i kombinatorikom.
U ovoj nedelji proširujemo osnovno znanje iz dinamičkog programiranja na probleme gde stanje zavisi od dva ili više parametara. Ovo je ključni korak ka rešavanju ozbiljnijih takmičarskih zadataka, naročito na okružnom, državnom i SIO nivou.
Tipični primeri uključuju kretanje kroz matrice, poređenje stringova, kao i probleme sa ograničenjima po vremenu, prostoru ili broju poteza.
Glavne ideje i koncepti
- Višedimenzionalno stanje:
dp[i][j],dp[i][j][k]— svaki indeks ima jasno značenje. - Redosled popunjavanja: često je kritičan (po redovima, kolonama, dijagonalama).
- Prelazi iz više smerova: gore, levo, dijagonalno, ili kombinacije.
- Optimizacija memorije: redukcija sa 2D na 1D kada je moguće.
Pravilo: Ako DP stanje ima dva parametra koji rastu nezavisno, gotovo sigurno je potreban 2D DP.
Klasični 2D DP problemi
-
Maksimalan zbir na putu kroz matricu — SvetProgramiranja
— detaljna analiza DP stanja
dp[i][j], prelaza i optimizacije memorije. - Najduži zajednički podniz (LCS) — SvetProgramiranja — kompletno objašnjenje DP tabele, prelaza i implementacija u C++ / Python.
- Edit Distance (Levenshtein)
- 0/1 Knapsack — stanje
dp[i][w]
Primer: maksimalna suma puta kroz matricu
Dat je grid n × m. Dozvoljeno je kretanje udesno i nadole.
Naći maksimalnu sumu od (1,1) do (n,m).
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0) dp[i][j] = a[i][j];
else {
dp[i][j] = a[i][j];
if (i > 0) dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i][j]);
if (j > 0) dp[i][j] = max(dp[i][j], dp[i][j-1] + a[i][j]);
}
}
}
DP stanje: dp[i][j] — maksimalna suma do polja (i, j).
DP nad stringovima
- LCS:
dp[i][j]— dužina LCS prefiksas[0..i)it[0..j) - Edit Distance: minimalan broj operacija (insert, delete, replace)
Predloženi zadaci za vežbu (Nedelja 5)
- Petlja — Maksimalni zbir puta kroz matricu + SvetProgramiranja — rešenje
- Longest Common Subsequence (LCS) — SvetProgramiranja — kompletno objašnjenje DP tabele, prelaza i implementacija u C++ / Python.
- LeetCode — Longest Common Subsequence
- LeetCode — Edit Distance
- AtCoder DP C — Vacation (2D DP sa izborima po danima)
-
0/1 Knapsack — dinamičko programiranje (SvetProgramiranja)
— analiza stanja
dp[i][w]i tipične greške. - AtCoder DP E — Knapsack 2 (optimizacija DP stanja)
Plan rada (predlog)
- Počni sa DP-om u matrici (max/min put).
- Nacrtaj tabelu DP-a ručno za mali primer.
- Pređi na LCS — obrati pažnju na dijagonalni prelaz.
- Implementiraj Edit Distance i analiziraj razlike u prelazima.
- Pokušaj optimizaciju memorije (samo dva reda DP-a).
Studijske napomene i česte greške
- Nejasno definisano značenje
dp[i][j]. - Pogrešan redosled popunjavanja tabele.
- Zaboravljeni bazni slučajevi (prvi red/kolona).
- Prevelika memorija — razmisli da li je moguće koristiti 1D DP.
Resursi i reference
Praktična vežba — DP primeri u C++
U nastavku se nalaze konkretni primeri koji pokrivaju početne DP zadatke tipa SIO/Državno za učenike 8. razreda / 1. srednje.
Primer 1: Climbing Stairs (Penjanje stepenicama)
Zadatak: Koliko različitih načina postoji da se popne n stepenica, ako je moguće napraviti 1 ili 2 koraka odjednom?
Ideja rešenja
- Definiši
dp[i]kao broj načina da se dođe do stepenice i. - Baza:
dp[0] = 1(1 način da ostaneš na startu). - Prelaz:
dp[i] = dp[i-1] + dp[i-2]
Kod u C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n+1, 0);
dp[0] = 1; dp[1] = 1;
for(int i = 2; i <= n; ++i) {
dp[i] = dp[i-1] + dp[i-2];
}
cout << dp[n] << endl;
return 0;
}
Vizuelna tabela DP prelaza (primer za n=5)
| i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
Primer 2: Frog 1 (Žaba 1)
Zadatak: Žaba stoji na 0. stepenici i želi da dođe do n-1 stepenice. Svaka stepenica ima trošak h[i]. Može skočiti na sledeću ili preko jedne stepenice. Koliki je minimalni ukupni trošak?
Ideja rešenja
- Definiši
dp[i]kao minimalni trošak da se dođe do stepenice i. - Baza:
dp[0] = 0,dp[1] = abs(h[1]-h[0]) - Prelaz:
dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]))
Kod u C++
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> h(n);
for(int i=0; i<n; ++i) cin >> h[i];
vector<int> dp(n, 0);
dp[0] = 0;
dp[1] = abs(h[1]-h[0]);
for(int i=2; i<n; ++i) {
dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
}
cout << dp[n-1] << endl;
return 0;
}
Vizuelna tabela DP prelaza (primer za n=5, h={10,30,20,40,25})
| i | dp[i] |
|---|---|
| 0 | 0 |
| 1 | 20 |
| 2 | 10 |
| 3 | 30 |
| 4 | 35 |
Napomena
Ova dva primera pokrivaju osnovni princip DP-a: definicija stanja, baza, prelazi i iterativno popunjavanje tabele. Nakon ovih zadataka učenik je spreman da pređe na Knapsack i Coin Change probleme.
Linkovi za dalje vežbanje
Primer 3: Coin Change (Promena novca)
Zadatak: Dati su kovanice različitih vrednosti coins[] i ciljna suma sum. Koliko različitih načina postoji da se složi sum korišćenjem dostupnih kovanica (svaka kovanica može biti korišćena više puta)?
Ideja rešenja
- Definiši
dp[i]kao broj načina da se složi sumai. - Baza:
dp[0] = 1(1 način da se složi nula — ne koristiti nijednu kovanicu). - Prelaz: za svaku kovanicu
ci za sve sume odcdosum:dp[i] += dp[i-c]. - Ovako dobijamo broj kombinacija (redosled kovanica nije bitan).
Kod u C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, sum;
cin >> n >> sum; // n = broj kovanica, sum = ciljna suma
vector<int> coins(n);
for(int i=0; i<n; ++i) cin >> coins[i];
vector<long long> dp(sum+1, 0);
dp[0] = 1;
for(int c : coins) {
for(int i = c; i <= sum; ++i) {
dp[i] += dp[i - c];
}
}
cout << dp[sum] << endl;
return 0;
}
Vizuelna tabela DP prelaza (primer)
Za kovanice {1,2,5} i sumu 5:
| Suma i | dp[i] |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 2 |
| 4 | 3 |
| 5 | 4 |
Napomena
Ovaj zadatak uvodi učenika u DP koji se koristi za kombinatorne probleme i optimizaciju broja rešenja. Redosled iteracija je važan da bi se brojale kombinacije a ne permutacije.
Linkovi za dalje vežbanje
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.
Nedelja 6 — Naprednije dinamičko programiranje (Knapsack, optimizacije, DP po dimenzijama)
Ova nedelja je posvećena naprednijim oblicima dinamičkog programiranja. Fokus je na problemima gde DP tabela ima dve ili više dimenzija, kao i na tehnikama optimizacije memorije i pravilnog redosleda popunjavanja.
Zadaci iz ove oblasti su veoma česti na SIO i državnom takmičenju, jer zahtevaju precizno definisanje stanja i pažljivo razmišljanje o prelazima.
Glavne teme
- 0/1 Knapsack problem — klasičan DP sa dve dimenzije
- Optimizacija memorije — prelazak sa 2D DP na 1D DP
- DP po elementima i kapacitetu (dp[i][w])
- Razlika između 0/1, unbounded i bounded varijanti
- DP nad nizovima i podnizovima
Ključni primer — 0/1 Knapsack
Dat je skup predmeta, svaki sa težinom w[i] i vrednošću v[i].
Cilj je maksimizovati ukupnu vrednost bez prekoračenja kapaciteta ranca.
Standardno DP stanje:
dp[i][w] = maksimalna vrednost
koristeći prvih i predmeta
sa ukupnom težinom ≤ w
Prelaz:
• ne uzimamo predmet i → dp[i-1][w]
• uzimamo predmet i → dp[i-1][w - w[i]] + v[i]
Optimizacija memorije (2D → 1D)
Pošto stanje dp[i] zavisi samo od dp[i-1],
moguće je koristiti jednodimenzioni DP niz.
vector dp(W+1, 0);
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]);
}
}
Iteracija unazad po w je ključna — sprečava višestruko korišćenje istog predmeta.
Česte greške kod Knapsack zadataka
- Pogrešan redosled petlji (napred umesto unazad)
- Nejasno definisano DP stanje
- Mešanje 0/1 i unbounded varijanti
- Korišćenje int tipa gde je potreban long long
Predloženi zadaci za vežbu (interni + eksterni)
- Knapsack (0/1) — dinamičko programiranje (SvetProgramiranja) — detaljno objašnjenje DP stanja i prelaza.
- Longest Common Subsequence (LCS) — SvetProgramiranja — ponavljanje DP nad nizovima.
- Maksimalan zbir na putu kroz matricu — DP po 2D mreži
- AtCoder DP D — Knapsack 1
- Takprog / Petlja — zadaci sa takmičenja
Plan rada (predlog)
- Razumeti i zapisati DP stanje za Knapsack bez gledanja rešenja.
- Implementirati klasični 2D DP.
- Optimizovati memoriju na 1D DP i objasniti zašto ide unazad.
- Rešiti bar 2 varijacije Knapsack zadataka.
- Povezati Knapsack sa drugim DP problemima (Coin Change, LCS).
Studijske napomene
- DP zadaci gotovo uvek zahtevaju da se ručno napiše stanje na papiru.
- Ako DP ima više dimenzija — proveri da li se neka može eliminisati.
- Uvek razmisli: da li je ovo 0/1 ili unbounded problem?
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> adj(n);
adj[u].push_back(v);
adj[v].push_back(u);
Lista susedstva je standard na takmičenjima — 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 / matrice
- Topološko sortiranje (kasnije)
vector 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 nalazi najkraći put.
- Najkraći put u netežinskom grafu
- Problemi sa najmanjim brojem koraka
- Stanja i prelazi (graf stanja)
vector dist(n, -1);
queue 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);
}
}
}
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, tabla, lavirint. Svako polje je čvor, a kretanja su grane.
- Broj ostrva
- Najkraći put u lavirintu
- Poplave, širenje, požari
Česte greške kod BFS/DFS zadataka
- Zaboravljeno obeležavanje posećenih čvorova
- Pogrešna inicijalizacija distance
- Korišćenje DFS-a umesto BFS-a za najkraći put
- Nepravilno modelovanje stanja
Predloženi zadaci za vežbu (interni + eksterni)
- BFS i DFS — SvetProgramiranja (osnovni vodič)
- Broj ostrva — BFS/DFS u matrici (SvetProgramiranja)
- Najkraći put u lavirintu — BFS (SvetProgramiranja)
- LeetCode — Number of Islands
- Takprog / Petlja — grafovski zadaci
Plan rada (predlog)
- 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.
Studijske napomene
- Ako se problem može opisati kao „stanja + prelazi“ — verovatno je graf.
- BFS = najmanji broj koraka.
- DFS = struktura, komponente, ciklusi.
- Grafovi su temelj za sledeće teme: Dijkstra, DSU, 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 izuzetno česti na državnim takmičenjima i SIO. Učenici uče kako da pravilno modeluju realan problem kao graf i primene 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
- Upotreba priority_queue (min-heap) u C++
-
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 je konačna.
Primer C++ implementacije (Dijkstra)
#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});
}
}
}
}
Za razliku od BFS-a, ovde se ne koristi klasičan visited niz.
Umesto toga proveravamo da li je izvučena udaljenost zastarela
(d > dist[u]).
Tipični zadaci
- Najkraći put između dva grada
- Najbrži ili najjeftiniji put u mreži
- Višestruki upiti za najkraći put iz jednog izvora
- Graf kao matrica (lavirinti sa težinama prelaza)
- Modelovanje problema gde stanje predstavlja čvor grafa
Predloženi zadaci za vežbu
- SvetProgramiranja — Dijkstra algoritam (objašnjenje + primeri)
- Prioritetni red (priority_queue) u C++
- CSES — Shortest Routes I
- SPOJ — Easy Dijkstra
- AtCoder — Come Back Quickly
- Takprog / Petlja — grafovski zadaci
Plan rada (predlog)
- Rešiti najkraći put BFS-om u neponderisanom grafu.
- Razumeti zašto BFS ne radi kada težine nisu jednake.
- Implementirati Dijkstra algoritam sa priority_queue.
- Ručno ispratiti algoritam na malom grafu.
- Rešiti 2–3 zadatka sa CSES / SPOJ platformi.
Studijske napomene
- Dijkstra ne radi sa negativnim težinama.
- Vremenska složenost: O((V + E) log V).
- Uvek proveriti da li je graf usmeren ili neusmeren.
- Za veće ulaze koristiti
long longza udaljenosti.
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
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
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.
Nedelja 10 — Napredne strukture podataka (planirano gradivo)
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 (DP, grafovi, prioritetni redovi).
Gradivo iz ove nedelje je u vodiču označeno kao planirano. Stranice sa detaljnim objašnjenjima i primerima biće dodate postepeno, a linkovi ispod trenutno služe kao orijentir za važne teme.
Planirane teme
-
Set / Map (hash i balansirana stabla)
Razlike između unordered_map i map, složenosti, tipične greške na takmičenjima. -
Prioritetni red (Heap)
Interna struktura heap-a, primene van Dijkstra algoritma. -
Fenwick Tree (Binary Indexed Tree — BIT)
Efikasno računanje prefiksnih suma i ažuriranja u O(log n). -
Uvod u segmentno stablo
Opšti koncept, struktura stabla, osnovne operacije.
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.
Status gradiva
Ove teme su trenutno u izradi. Čim stranice sa objašnjenjima budu završene, linkovi će biti aktivirani i ubačeni direktno u ovu sekciju.
Preporuka učenicima
- 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 posvećena je osnovama algoritamske geometrije i mešovitim zadacima koji kombinuju više oblasti (DP, grafove, kombinatoriku, geometriju). 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 — računanje površine prostog poligona (orijentacija temena, redosled obilaska).
- Rastojanje tačke od prave — geometrijska interpretacija i formula, primene u optimizacionim problemima.
- Provera preseka duži — orijentacija tačaka, specijalni slučajevi (kolinearnost, dodir u krajnjim tačkama).
- Konveksni omotač (uvod) — osnovna ideja i primene (bez insistiranja na kompleksnim implementacijama).
Mešoviti (kombinovani) zadaci
- Problemi koji zahtevaju graf + DP (npr. najkraći put sa dodatnim ograničenjima).
- DP nad geometrijskim objektima (intervali, segmenti, tačke).
- Kombinatorika u grafovima (brojanje puteva, konfiguracija).
- Zadaci gde je ključno pravilno modelovati stanje.
Zašto je ova nedelja važna?
- Geometrija često donosi „neočekivane“ zadatke na takmičenjima.
- Mešoviti zadaci razdvajaju dobre od odličnih takmičara.
- Pomaže učenicima da nauče da kombinuju više tehnika u jednom rešenju.
Preporučeni resursi
- Algoritmi — SvetProgramiranja (sekcije o geometriji i mešovitim primerima)
- CP-Algorithms — Geometry (detaljni tutorijali i formule)
Preporuka za kraj pripreme
- Ne učiti geometriju napamet — fokus na razumevanje.
- Vežbati čitanje i modelovanje zadataka.
- Ponoviti sve prethodne oblasti kroz mešovite probleme.
- Raditi simulacije takmičenja sa ograničenim vremenom.
Napomena: Ova nedelja služi kao zaokruživanje pripreme i prelaz ka takmičarskom razmišljanju. Nije cilj savršena implementacija svake geometrijske tehnike, već prepoznavanje odgovarajućeg pristupa.
□ Proširenje za nivo olimpijade (napredni učenici)
Sledeće teme nisu obavezne za SIO i standardna školska takmičenja, ali su česte na republičkim olimpijadama i međunarodnim takmičenjima (IOI stil zadataka).
Napredni graf algoritmi
-
Minimalno razapinjuće stablo (MST) —
Prim i Kruskal algoritmi.
Interno: MST — SvetProgramiranja (u izradi)
Spoljno: CP-Algorithms — Kruskal -
Topološko sortiranje —
DAG grafovi, zavisnosti.
Interno: Topološko sortiranje (u izradi)
Spoljno: CP-Algorithms — Topological Sort -
Snažno povezane komponente (SCC) —
Kosaraju / Tarjan.
Spoljno: CP-Algorithms — SCC -
Bellman–Ford —
negativne težine i ciklusi.
Spoljno: CP-Algorithms — Bellman–Ford
Napredno dinamičko programiranje
- DP na grafovima (DAG DP). — USACO Guide — DAG DP
- DP sa bitmaskama (n ≤ 20). — CP-Algorithms — Bitmask DP
- Optimizacije DP-a (kompresija memorije, rolling array).
Napredne strukture podataka
-
Segmentno stablo.
Interno: Segmentno stablo (u izradi)
Spoljno: CP-Algorithms — Segment Tree -
Fenwick (BIT) stablo.
Interno: Fenwick stablo
Spoljno: CP-Algorithms — Fenwick
Preporuka: Ove teme uvoditi tek nakon sigurnog savladavanja DFS/BFS, osnovnog DP-a i Dijkstra algoritma.
|
Prethodno
|< Priprema za državna takmičenja |
Sledeće
Interaktivni Algoritmi >| |