Sport dasturchi yo'li — maktab olimpiadasidan IOI gacha
Sport dasturlash — bu masalani cheklangan vaqtda, cheklangan xotirada va cheklangan asab bilan yechish san’ati. Bu yerda yozilgan bosqichlar USACO Guide tuzilishiga, mavzular tartibi esa Antti Laaksonen ning kitobiga va IOI Syllabus chegarasiga tayanadi.
Bosqichlar
“Bosqichlar” bo'limiga havola- Umumiy vaqt
- ~2–4 yil · haftasiga 8–15 soat
- Kimga
- Jumboq yechishni yoqtiradigan, matematikadan qo'rqmaydigan 7-sinf va undan katta o'quvchi.
- Yangilangan
Tugunlarni belgilash uchun JavaScript kerak. Xaritaning o'zi quyida to'liq ochiq turibdi —47 tugun, 6 bosqich.
047 tugundan bajarildi
0 · Kirish
Bu bosqich algoritm emas, TIL haqida. U tugamasdan keyingisi vaqt isrofi
~4–6 oy · haftasiga 5–6 soat
Python Basic — to'liq~4 oy
Yigirma dars: o'zgaruvchidan fayl bilan ishlashgacha. Sport dasturlashda til to'siq bo'lmasligi kerak, aks holda har masalada ikki jang bo'ladi.
TekshiruvYigirma darsning beshta blok testidan har birida 8 tadan 6 tasi to'g'ri.
Rekursiya2 hafta
Keyinchalik DFS, backtracking va DP shu bitta g'oyaga suyanadi. Rekursiyani noqulay his qilgan o'quvchi Oltin darajada to'xtaydi.
TekshiruvRekursiv funksiyaning chaqiruv daraxtini qog'ozda chizasiz.
Algoritm nima1 hafta
Kirish, chiqish, to'g'rilik va qadam. «Ishladi» bilan «to'g'ri» orasidagi farq shu darsda qo'yiladi.
TekshiruvYechimingiz nima uchun har kirishda to'g'ri ishlashini bir abzatsda asoslaysiz.
Bosqich sinoviSikl, ro'yxat, lug'at va funksiyani yordamsiz, xatosiz yozasiz.
1 · Bronza
Algoritmik fikrlash · maktab olimpiadasi darajasi
~2–3 oy · haftasiga 8–10 soat
To'liq izlash1 hafta
Barcha variantni ko'rib chiqish. Bu «yomon yechim» emas — bu birinchi to'g'ri yechim, va tez yechim har doim shundan tug'iladi.
TekshiruvMasalaning barcha holatlarini sanab chiqadigan yechimni yozib, ishga tushirasiz.
Murakkablik intuitsiyasi1 hafta
Yuz million qoidasi: bir soniyada taxminan shuncha oddiy amal bajariladi. Shu bitta raqam yechim yozishdan OLDIN uni rad etish imkonini beradi.
Tekshiruvn = 200 000 berilganda O(n²) sig'maslikni hisob bilan ko'rsatasiz.
Massiv va prefiks yig'indi1 hafta
Oldindan hisoblab qo'yish g'oyasi. Har so'rovga javob bir amalda beriladi — bu keyin Fenwick daraxtigacha davom etadigan yo'lning birinchi qadami.
TekshiruvMillion elementli massivda 10⁵ ta oraliq so'roviga vaqt chegarasida javob berasiz.
Saralashni ishlatish1 hafta
Saralash algoritmini yozish emas, uni QUROL sifatida ishlatish. Ko'p masala saralangandan keyin o'z-o'zidan yechiladi.
TekshiruvKalit bo'yicha saralab, masalani chiziqli o'tish bilan yakunlaysiz.
Ikkilik qidiruv1 hafta
Har savolda imkoniyat yarmiga kamayadi. Oddiy ko'ringan bu g'oya keyin javob bo'yicha qidiruvda butunlay boshqa kuchga ega bo'ladi.
TekshiruvSaralangan million elementli massivda qidiruvni kutubxonasiz o'zingiz yozasiz.
Ochko'zlik2 hafta
Har qadamda eng yaxshisini tanlash. Muhimi — u qachon ISHLAMASLIGINI bilish; shuning uchun bu darsda isbot ham bor.
TekshiruvOchko'z yechimingiz nima uchun to'g'ri ishlashini almashish argumenti bilan asoslaysiz.
CSES — Introductory Problems3 hafta
O'n to'qqizta masala, hammasi asosiy g'oyalarni tekshiradi. Bu yerda haqiqiy tekshiruvchi bor: «menimcha to'g'ri» degan javob qabul qilinmaydi.
TekshiruvIntroductory bo'limidan kamida 15 masala yashil.
CSES Problem SetBizda hali yo'q — tashqi manba
Codeforces Div3 A–Bhaftasiga 1 musobaqa
Birinchi haqiqiy musobaqa muhiti: vaqt, asabiylik va noto'g'ri javob. Reyting bu bosqichda muhim emas, ISHTIROK muhim.
TekshiruvUchta ketma-ket virtual Div3 da A va B ni 40 daqiqada yechasiz.
CodeforcesBizda hali yo'q — tashqi manba
Bosqich sinoviCodeforces Div3 ning A va B masalalarini 40 daqiqada yechasiz.
2 · Kumush
Usullar to'plami · tuman va shahar bosqichi
~3–4 oy · haftasiga 10–12 soat
To'plam va lug'at1 hafta
Hash asosidagi tuzilmalar: tekshirish va sanash bir amalda. Ko'p Div3 C masalasi aynan shu bilan yopiladi.
TekshiruvMassivda takrorlangan juftliklarni chiziqli vaqtda sanaysiz.
Ikki ko'rsatkich2 hafta
Ikki indeks bir yo'nalishda siljiydi va kvadratik izlash chiziqliga aylanadi. Siljiydigan oyna shu g'oyaning nomi.
TekshiruvYig'indisi berilgan qiymatdan oshmaydigan eng uzun oynani chiziqli topasiz.
Stek, navbat va deque2 hafta
Uch oddiy tuzilma, uchta katta usul: qavslar, keyingi katta element va oynadagi maksimum.
TekshiruvHar element uchun keyingi katta elementni chiziqli vaqtda topasiz.
Javob bo'yicha ikkilik qidiruv2 hafta
«Eng kichik X ni toping» masalasi «X yetadimi?» savoliga aylanadi. Kumush darajaning eng kuchli bitta usuli shu.
TekshiruvOptimallashtirish masalasini tekshirish funksiyasiga keltirib yechasiz.
Intervallar1 hafta
Kesishish, birlashtirish va supurish chizig'i. Bu mavzu keyin geometriyada ham, rejalashtirish masalalarida ham qaytadi.
TekshiruvYuz ming intervalni birlashtirib, natijani n log n da chiqarasiz.
Stress-test1 hafta
Sekin va tez yechimni tasodifiy testlarda solishtirish. Bu usul «nega WA?» degan savolni ikki daqiqada yopadi.
TekshiruvO'z yechimingizni buzadigan minimal testni skript bilan topasiz.
Invariant va almashish1 hafta
Nima uchun to'g'ri ekanini ayta olmasangiz, yechim emas, taxmin yozgansiz. Bu dars taxminni yechimga aylantiradi.
TekshiruvOchko'z yechimning to'g'riligini almashish argumenti bilan yozasiz.
CSES — Sorting and Searching~1 oy
O'ttiz besh masala, kumush usullarining deyarli hammasi shu bo'limda uchraydi.
TekshiruvBo'limdan kamida 20 masala yashil.
CSES — Sorting and SearchingBizda hali yo'q — tashqi manba
Codeforces Div3 Chaftasiga 1 musobaqa
Uch masala emas, uchinchi masala. Bu yerda birinchi marta g'oyani O'ZINGIZ topishingiz kerak bo'ladi.
TekshiruvUchta ketma-ket Div3 da C ni musobaqa vaqtida yechasiz.
Codeforces Div3Bizda hali yo'q — tashqi manba
Bosqich sinoviSinfdoshingiz yechimini buzadigan testni stress-test bilan topasiz.
3 · Oltin
Graflar · viloyat bosqichi
~4–6 oy · haftasiga 10–14 soat
Graf nima1 hafta
Tugun va qirra. Ko'p masala graf haqida emas, lekin graf tilida yozilganda birdan oson bo'lib qoladi — asosiy ko'nikma aynan shu tarjima.
TekshiruvShahar va yo'llar masalasini qo'shnilar ro'yxatiga o'girib yozasiz.
DFS2 hafta
Chuqurlikka izlash: bog'lanish komponentlari, sikl aniqlash va daraxt bo'ylab o'tish shundan chiqadi.
TekshiruvGrafdagi bog'lanish komponentlari sonini rekursiv va steksiz yozasiz.
BFS va eng qisqa yo'l2 hafta
Og'irliksiz grafda eng qisqa yo'l. Panjarada bu «eng kam qadamda chiqish» masalasining standart javobi.
TekshiruvLabirintdan eng qisqa chiqish yo'lini topib, uni ham qayta tiklaysiz.
Flood fill va panjara1 hafta
Panjara ham graf. Orollarni sanash, sohalarni bo'yash va chegaralarni topish shu bitta shablon bilan yopiladi.
Tekshiruv1000×1000 panjarada orollar sonini vaqt chegarasida sanaysiz.
Backtracking2 hafta
To'liq izlash, lekin kesish bilan. N-vazir va sudoku shu usulning klassik namunalari.
Tekshiruv8-vazir masalasini yechib, kesish qanchalik foyda berganini o'lchaysiz.
Topologik saralash1 hafta
Bog'liqliklar tartibi: qaysi ish qaysidan keyin. Bu keyin DP ning grafdagi ko'rinishiga ham asos bo'ladi.
TekshiruvKurslar bog'liqligidan to'g'ri tartib chiqarasiz yoki sikl borligini isbotlaysiz.
Daraxtlar2 hafta
Sikli yo'q bog'langan graf. Balandlik, ota-tugun, diametr va daraxt bo'ylab DP shu yerdan boshlanadi.
TekshiruvDaraxt diametrini ikki marta DFS bilan topasiz va nima uchun ishlashini aytasiz.
Dijkstra2 hafta
Og'irlikli grafda eng qisqa yo'l. Ustuvor navbat bilan birga bu Oltin darajaning eng ko'p uchraydigan algoritmi.
TekshiruvYuz ming qirrali grafda eng arzon yo'lni vaqt chegarasida topasiz.
CSES — Graph Algorithms~1,5 oy
O'ttizdan ortiq graf masalasi. Bu bo'limni yopgan o'quvchi viloyat bosqichida graf masalasidan qo'rqmaydi.
TekshiruvBo'limdan kamida 18 masala yashil.
CSES — Graph AlgorithmsBizda hali yo'q — tashqi manba
Bosqich sinoviYangi graf masalasida usulni o'zingiz tanlab, yechimni oxirigacha olib borasiz.
4 · Platina
Dinamik programmalash va tuzilmalar · respublika bosqichi
~6–9 oy · haftasiga 12–15 soat
DP — memoizatsiya2 hafta
Rekursiya plus xotira. DP shu yerdan boshlanadi, chunki bu ko'rinishda u yangi narsa emas — takrorlanadigan hisobni saqlash.
TekshiruvRekursiv yechimga memoizatsiya qo'shib, tezlanishni o'lchaysiz.
Bir o'lchovli DP2 hafta
Holat, o'tish va boshlang'ich qiymat. Uch savolga javob berilsa, DP yozilgan bo'ladi.
TekshiruvEng uzun o'suvchi ketma-ketlikni n log n da yozasiz.
Knapsack2 hafta
Ikki o'lchovli holat. Bu masala DP ning «alifbosi»: undan keyingi ko'p masala shunga o'xshab ko'rina boshlaydi.
TekshiruvSig'im 10⁴ va 100 buyum bilan masalani vaqt chegarasida yechasiz.
Panjarada DP va LCS2 hafta
Ikki o'lchovli jadval va ketma-ketliklar ustida DP. Tahrirlash masofasi ham shu oilaga kiradi.
TekshiruvIkki satrning eng uzun umumiy qismini topib, javobni qayta tiklaysiz.
DSU va MST2 hafta
Birlashuvchi to'plamlar va eng kichik qamrovchi daraxt. Kruskal shu ikki g'oyaning uchrashuvi.
TekshiruvYuz ming qirrali grafda MST og'irligini vaqt chegarasida hisoblaysiz.
Fenwick daraxti2 hafta
Yig'indi so'rovi va nuqtaviy yangilanish — ikkalasi ham log n da. Prefiks yig'indi g'oyasining dinamik davomi.
Tekshiruv10⁵ yangilanish va 10⁵ so'rovni vaqt chegarasida bajarasiz.
C++ ga o'tish~1 oy
Bu bosqich boshida Python ba'zi masalalarda vaqt chegarasiga sig'may qoladi. Sabab tilda emas, tezlik farqida — va uni tan olish kerak.
TekshiruvOldin Python'da yozgan uchta yechimingizni C++ da qayta yozib, vaqtini solishtirasiz.
CSES — Dynamic Programming~1,5 oy
Yigirmata masala, DP ning asosiy shakllari deyarli to'liq qamrab olingan.
TekshiruvBo'limdan kamida 14 masala yashil.
CSES — Dynamic ProgrammingBizda hali yo'q — tashqi manba
USACO Golddavomiy
Amerika olimpiadasi arxivi. Masalalar uzun matnli va real: modellashtirish ko'nikmasini aynan shu yerda charxlaysiz.
TekshiruvGold darajadagi uchta masalani mustaqil yechasiz.
USACO GuideBizda hali yo'q — tashqi manba
Bosqich sinoviYangi DP masalasida holat va o'tishni o'zingiz topasiz — namunaga qaramasdan.
5 · Olimpiada
Maxsus mavzular va musobaqa strategiyasi · milliy tanlov va IOI
davomiy · haftasiga 15+ soat
Bit va bitmask2 hafta
To'plamni bitta songa joylash. Kichik n da bu DP ni butunlay boshqa tezlikka olib chiqadi.
Tekshiruvn ≤ 20 uchun kommivoyajer masalasini bitmask DP bilan yechasiz.
Sonlar nazariyasi3 hafta
Tub sonlar, elak, EKUB va modul arifmetikasi. IOI Syllabus da bu mavzular chegarasi aniq belgilangan.
Tekshiruv10⁶ gacha tub sonlarni elak bilan topib, bo'luvchilar sonini hisoblaysiz.
Kombinatorika2 hafta
Sanash: joylashtirish, tanlash, Paskal uchburchagi va modul bo'yicha bo'lish.
TekshiruvKatta n uchun binomial koeffitsiyentni modul arifmetikasida hisoblaysiz.
Geometriya asoslari2 hafta
Vektor, ko'paytma, yo'nalish va kesishish. Aniqlik xatosi bu mavzuning asosiy tuzog'i.
TekshiruvUch nuqtaning yo'nalishini butun sonlarda, kasrsiz aniqlaysiz.
Masaladan algoritmga2 hafta
Musobaqada eng qiyin qism algoritm yozish emas, QAYSI algoritm kerakligini topish. Bu dars shu xaritani beradi.
TekshiruvNotanish masalani o'qib, 5 daqiqada usulni to'g'ri nomlaysiz.
Musobaqa strategiyasi1 hafta
Masalalarni o'qish tartibi, vaqt taqsimoti, qachon tashlab ketish va qachon qaytish. Ko'pincha reyting shu yerda yutiladi.
TekshiruvMusobaqadan keyin vaqtingizni masalalar bo'yicha yozib, nima noto'g'ri ketganini aytasiz.
Upsolving — majburiy odatdavomiy
Musobaqadan keyin yechilmagan masalani oxirigacha yechish. O'sishning asosiy manbai shu, musobaqaning o'zi emas.
TekshiruvHar musobaqadan keyin kamida bitta yechilmagan masalani yopasiz.
AtCoder va IOI arxividavomiy
AtCoder masalalari toza va matematik. IOI arxivi esa haqiqiy daraja o'lchagichi.
TekshiruvAtCoder Beginner Contest da to'rtta masala yechasiz.
AtCoderBizda hali yo'q — tashqi manba
Milliy tanlovyiliga 1 marta
Respublika bosqichi va terma jamoa saralashi. Bu yerda tayyorgarlik emas, muntazamlik hal qiladi.
TekshiruvViloyat yoki respublika bosqichida qatnashgansiz.
Bosqich sinovi5 masalali 3 soatlik musobaqada 2 tadan ko'p masala yechasiz.
Haftalik rejim
“Haftalik rejim” bo'limiga havolaBosqichlar mavzuni ko’rsatadi, rejim esa tezlikni belgilaydi. Xaritadagi vaqtlar aynan shu rejimda hisoblangan — undan sekinroq ketilsa, muddatlar ham cho’ziladi.
- Kuniga 1–2 masala, haftasiga 10–14 ta. Kuniga o’nta masala yechib, keyin ikki hafta yo’qolgandan ko’ra shu tartib ancha samarali.
- Haftasiga bitta virtual musobaqa. Vaqt bosimi alohida ko’nikma va uni faqat vaqt bosimi ostida mashq qilish mumkin.
- Upsolving majburiy. Musobaqadan keyin yechilmagan masalani oxirigacha yechish — o’sishning asosiy manbai. Musobaqaning o’zi emas.
- Har masaladan keyin bir qator. «Nima o’rgandim» degan savolga bitta gap bilan javob yozib boring. Uch oydan keyin bu daftar sizning eng foydali darsligingizga aylanadi.
Nima uchun bosqichni o’tkazib yubormaslik kerak
“Nima uchun bosqichni o’tkazib yubormaslik kerak” bo'limiga havolaEng ko’p uchraydigan xato — Bronza tugamasdan dinamik programmalashga o’tish. Natijasi har safar bir xil: yodlangan kod, tushunilmagan g’oya va yangi masalada boshi berk ko’cha.
Sabab oddiy. DP holatini topish uchun avval to’liq izlashni ko’rish kerak — DP aslida o’sha to’liq izlashning takrorlanadigan qismini saqlab qo’yishdan boshqa narsa emas. To’liq izlash mustahkam bo’lmasa, DP sehrli formulaga aylanadi va sehrli formulani yangi masalaga qo’llab bo’lmaydi.
Har daraja oxirida Algorithms modulining daraja testi turadi. Sakkiztadan to’rttadan ko’p xato bo’lsa — o’sha daraja hali tugamagan.
C++ ga qachon o’tiladi
“C++ ga qachon o’tiladi” bo'limiga havolaPlatina bosqichi boshida. Sabab yashirilmaydi: Python ba’zi masalalarda vaqt chegarasiga sig’maydi va bu tilning kamchiligi emas, uning tabiati. Bronza va Kumush darajada bu deyarli hech qachon muammo bo’lmaydi, shuning uchun oldinroq o’tishning ma’nosi yo’q.
Batafsil taqqoslash va birinchi qadamlar: C++ ga bir qarash.
Bu yo'l qayerdan olingan
Xarita quyidagi ochiq manbalardan yig'ildi va o'zbek maktabi sharoitiga moslandi. Har biriga bevosita borishingiz mumkin; aksariyati ingliz tilida.
- USACO Guideusaco.guide
- IOI Syllabusioinformatics.org
- Antti Laaksonen — Competitive Programmer's Handbookcses.fi
- CSES Problem Setcses.fi
- Codeforcescodeforces.com
- AtCoderatcoder.jp
Yo'l xaritasi eskiradi — ayniqsa AI yo'nalishida vositalar tez o'zgaradi. Shu sababli har sahifada yangilangan sanasi turadi va yo'llar olti oyda bir qayta ko'riladi.