Vodič · Algoritmi · Napredne tehnike
Napredne tehnike – vodič kroz lekcije
Napredne tehnike su opšti načini razmišljanja koji pretvaraju sporo rešenje (dve ili tri ugnježdene petlje) u brzo. Svaka se javlja u desetinama takmičarskih zadataka.
Za ove lekcije potrebno je poznavanje nizova, sortiranja i binarne pretrage.
- 7–8. razred i srednja škola
- C++
- Priprema za takmičenja
Kako prepoznati tehniku: „zbir dela niza“ → prefiksne sume; „uzastopni deo sa uslovom“ ili „par u sortiranom nizu“ → dva pokazivača; „najmanje/najveće X tako da…“ → binarna pretraga po rešenju; „uzmi najbolje što možeš sada“ → pohlepni algoritam (uz proveru da je ispravan).
1 Brzi prolazi kroz niz
Tehnike koje rade u jednom prolazu ili uz malu pripremu.
2 Opšti pristupi
Kako se rešenje gradi od manjih delova.
3 Šta dalje
Teme koje nadograđuju ove tehnike.
Predloženi redosled
Korisni spoljni resursi
- CSES Problem Set – odeljak „Sorting and Searching“, zadaci sa automatskom proverom
- USACO Guide – Prefix Sums – prefiksne sume sa zadacima (engleski)