Algorithms

Ishlaydigan kod bilan tez ishlaydigan kod o’rtasida katta farq bor. Bu modul shu farqni o’lchashni, kamaytirishni va — eng muhimi — oldindan bashorat qilishni o’rgatadi.

Modulning ikkita maqsadi bor va ular bir-biriga xalaqit bermaydi. Birinchisi: har o’quvchida algoritmik fikrlash paydo bo’lsin, u olimpiadaga bormasa ham. Ikkinchisi: boradiganlar uchun IOI darajasigacha uzluksiz yo’l bo’lsin.

Kirish sharti

Python Basic moduli to’liq. Sikl, ro’yxat, funksiya, lug’at va rekursiya yozishni bilish shart — bu modul programmalash o’rgatmaydi, masala yechishni o’rgatadi.

Besh daraja

Darajalar bloklanmaydi: xohlagan joyingizdan boshlashingiz mumkin. Lekin har daraja avvalgisiga suyanadi, shuning uchun oldingi darajaning kamida oltita masalasini yechmasdan o’tish — vaqtni yo’qotish.

1 · Bronza — 1–8 dars

Algoritmik fikrlash. To’liq izlash, modellashtirish, prefiks yig’indi, saralash, ikkilik qidiruv, ochko’zlik. 10⁸ qoidasi shu yerda o’rnatiladi. Yakuni: maktab olimpiadasi darajasi

2 · Kumush — 9–16 dars

Usullar: to’plam va lug’at, ikki ko’rsatkich, stek va navbat, javob bo’yicha ikkilik qidiruv, intervallar, stress-test va isbot. Yakuni: tuman va shahar bosqichi

3 · Oltin — 17–24 dars

Graflar: DFS, BFS, flood fill, backtracking, topologik saralash, daraxtlar, Dijkstra. Yakuni: viloyat bosqichi

4 · Platina — 25–32 dars

Dinamik programmalash memoizatsiyadan boshlab, knapsack, panjarada DP, LCS, DSU, MST, Fenwick daraxti. Yakuni: respublika bosqichi

5 · Olimpiada — 33–40 dars

Bitmask, sonlar nazariyasi, kombinatorika, geometriya, optimallashtirish, masaladan algoritmga xaritasi, musobaqa strategiyasi va yakuniy virtual musobaqa. Yakuni: IOI yo’li

Qayerdan boshlash

Python Basic dan keyin to’g’ridan-to’g’ri 1-darajadan boshlang. Algoritmlarni allaqachon o’rgangan bo’lsangiz, har daraja oxiridagi testni yechib ko’ring: to’rttadan ko’p xato bo’lsa o’sha darajani o’tish kerak.

4-daraja boshida C++ ga bir qarash sahifasi turadi. U majburiy emas, lekin xalqaro olimpiadaga niyat qilgan bo’lsangiz — o’qing.

Bu modul boshqalardan nimasi bilan farq qiladi

Avval qo’lda, keyin kod. Har algoritm birinchi qog’ozda yoki panjarada o’ynaladi. Algoritm qiyin tuyulishining asosiy sababi shundaki, u odatda kod sifatida tanishtiriladi — qo’lda bir marta bajargan o’quvchi esa kodni o’rganmaydi, taniydi.

Avval sekin yechim, keyin tez yechim. Har masala ikki bosqichda ishlanadi: to’liq izlash yoziladi va ishlaydi, keyin nega sekin ekani o’lchanadi, keyingina tezlashtiriladi. Bu tartib buzilsa, o’quvchi optimal yechimni yodlaydi, lekin qayerdan kelganini bilmaydi.

Isbot ixtiyoriy emas. «Ishladi» va «to’g’ri» — ikki boshqa narsa. Har ochko’z algoritm uchun nega to’g’ri ishlashi aytiladi.

Masalalar qayerda yechiladi

Saytda avtomatik tekshiruvchi yo’q. O’rniga har darsda CSES va Codeforces masalalariga havola beriladi — u yerda haqiqiy tekshiruv bor.

Bundan tashqari loyihaning mashqlar/ papkasida 38 ta to’liq to’plam bor: masala matni, sekin va tez yechim etaloni, test generatori va o’nta tayyor test. Ularni VS Code’da lokal yurgizasiz:

python mashqlar/tekshir.py 13-mashina
python mashqlar/stress.py 15-eng-katta-yigindi

Birinchi buyruq ikki yechimni barcha testda solishtiradi va vaqtini o’lchaydi. Ikkinchisi tasodifiy testlar yasab, javoblar farq qilgan birinchi holatni topadi.

Modul yakunida

Yangi masalani ko’rganingizda chegara raqamiga qarab qaysi usul kerakligini ayta olasiz, yechimingizni yozishdan oldin uning necha amal qilishini bashorat qilasiz va tanlagan usulingiz nega to’g’ri ishlashini asoslay olasiz.