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.

Kako koristiti ovaj plan:

□ 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/answer i 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
1. Za svaki interaktivni zadatak najpre napišite lokalni grader/stub (funkcije query i answer) kako biste mogli da simulirate i debug-ujete strategiju.
2. Kod interaktivnih strategija zabeležite koliko upita koristite; probajte da optimizujete broj upita pre nego što povećate kompleksnost strategije.
3. Za DP kroz dane napravite jednostavnu implementaciju (O(N·K²)), testirajte na manjem skupu, pa eventualno optimizujte memoriju ili prelaze ako je potrebno.
4. 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):

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

Zašto sledi ova tema?
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/answer i 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 query i answer) 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 prefiksa s[0..i) i t[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

Vodič kroz algoritme — SvetProgramiranja
DP — Longest Common Subsequence (LCS)
DP u matrici — maksimalna suma puta
AtCoder — Educational DP Contest — dodatna praksa (A–Z).
CP-Algorithms — Dinamičko programiranje

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 suma i.
Baza: dp[0] = 1 (1 način da se složi nula — ne koristiti nijednu kovanicu).
Prelaz: za svaku kovanicu c i za sve sume od c do sum: 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)

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

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 long za 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

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

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

Osnova za ponavljanje i praksu

Obavezno predznanje (pre početka plana)

Nedelja 1 — Ponavljanje rekurzije i kombinatorike

Nedelja 2 — Priprema za SIO: interaktivni i vremenski zavisni zadaci

Zašto ova tema?

Teme i koncepti koje ćemo pokriti (konkretno za SIO):

Konkrektni zadaci / primeri koje obrađujemo (i koje treba rešavati ove nedelje)

Preporučeni resursi (Nedelja 2)

Preporučeni zadaci za vežbu (Nedelja 2)

Praktični savet za vežbu ove nedelje

Nedelja 3 — Backtracking (napredni zadaci)

Nedelja 4 — Uvod u dinamičko programiranje (DP)

Nedelja 5 — Klasični DP zadaci

Nedelja 6 — Napredniji DP i knapsack

Nedelja 7 — Grafovi: predstavljanje i pretrage

Nedelja 8 — Grafovi: najkraći putevi i varijante

Nedelja 9 — Teorija brojeva

Nedelja 10 — Napredne strukture podataka

Nedelja 11 — Geometrija i mešoviti zadaci

Preporučeni sajtovi za vežbanje i učenje

Dodatni resursi (na srpskom jeziku)

Preporučeni pristup (metodologija rada)

Nedelja 1 — Ponavljanje rekurzije i kombinatorike

Teme i koncepti:

Preporučeni online resursi (Nedelja 1):

Predloženi zadaci za vežbu (konkretni linkovi — Nedelja 1)

Preporučeni pristup u vežbi (Nedelja 1):

Nedelja 2 — Priprema za SIO: interaktivni i vremenski zavisni zadaci

Zašto ova tema?

Teme i koncepti koje ćemo pokriti (konkretno za SIO):

Konkrektni zadaci / primeri koje obrađujemo (i koje treba rešavati ove nedelje)

Preporučeni resursi (Nedelja 2)

Preporučeni zadaci za vežbu (Nedelja 2)

Praktični savet za vežbu ove nedelje

Nedelja 3 — Backtracking (napredni zadaci)

Glavne teme:

Predloženi zadaci za vežbu (konkretni linkovi — Nedelja 3)

Predloženi domaći zadaci (SvetProgramiranja & Petlja)

Nedelja 4 — Uvod u dinamičko programiranje (DP)

Glavni koncepti

Fibonacci kao uvodna ilustracija

1) Rekurzivno (bez DP)

2) Memoizacija — top-down

3) Tabulacija — bottom-up

Memoizacija vs. Tabulacija — kratka razlika

Jednostavni primeri za vežbu (ideje)

Predloženi zadaci za vežbu

Plan rada (predlog)

Studijske napomene i trikovi

Resursi i reference

Nedelja 5 — Dinamičko programiranje sa više dimenzija (2D / 3D DP)

Glavne ideje i koncepti

Klasični 2D DP problemi

Primer: maksimalna suma puta kroz matricu

DP nad stringovima

Predloženi zadaci za vežbu (Nedelja 5)

Plan rada (predlog)

Studijske napomene i česte greške

Resursi i reference

Praktična vežba — DP primeri u C++

Primer 1: Climbing Stairs (Penjanje stepenicama)

Ideja rešenja

Kod u C++

Vizuelna tabela DP prelaza (primer za n=5)

Primer 2: Frog 1 (Žaba 1)

Ideja rešenja

Kod u C++

Vizuelna tabela DP prelaza (primer za n=5, h={10,30,20,40,25})

Napomena

Linkovi za dalje vežbanje

Primer 3: Coin Change (Promena novca)

Ideja rešenja

Kod u C++

Vizuelna tabela DP prelaza (primer)

Napomena

Linkovi za dalje vežbanje

Napomena o izvorima zadataka

Nedelja 6 — Naprednije dinamičko programiranje (Knapsack, optimizacije, DP po dimenzijama)