38-dars: Masaladan algoritmga

5-darajaOlimpiada — musobaqa mahorati33–40 darslar

HayotdaShifoxona

Tajribali shifokor bemorni ko’rishi bilan taxminini aytadi, keyin tekshiruv bilan tasdiqlaydi. U barcha kasalliklarni birma-bir sinamaydi — alomatlarga qarab ro’yxatni qisqartiradi. Masala yechish ham xuddi shunday: hamma algoritmni sinash emas, alomatga qarab tanlash.

Bu darsdan keyin siz

• shartni o’qib, chegaralarni birinchi navbatda yozib olasiz
• chegaraga qarab yaramaydigan yechimlarni chetlab o’tasiz
• masaladagi alomatlarni usulga bog’laysiz

Avval qo’lda

Avval qo‘lda

~7 daqiqa·juftlikda·Uchta CSES masala sharti

CSES saytidan uchta masalani tanlab, faqat shartini o’qing — yechishga urinmang.

Har biri uchun ikki narsani qog’ozga yozing: chegara raqami va sizning taxminingiz («bu DP», «bu graf», «bu saralash»). Keyin sinfdoshingiz bilan taxminlarni solishtiring.

Nimani sezishingiz kerak

Taxminlaringiz to’g’ri chiqmasligi mumkin — bu muhim emas. Muhimi siz kod yozmasdan qaror qabul qildingiz. Olimpiadada bu qaror birinchi besh daqiqada qabul qilinadi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Uchta savol

Har masala uchun uchta savol, aynan shu tartibda.

Birinchi: chegara qancha? Bu raqam qaysi murakkablik sig’ishini aytadi va variantlarning yarmini darhol o’chiradi.

Ikkinchi: nima so’ralgan? Eng kattasi, eng kami, nechtasi, bormi, qaysi biri — savol turi usulni keskin toraytiradi.

Uchinchi: kirish qanday tuzilgan? Ro’yxat, panjara, uchlar va bog’lanishlar, satr, intervallar — tuzilma o’z usullarini olib keladi.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 10**52print(n * n, n * 17, n)

Sizning bashoratingizTekshirish

Javobni ko'rish

10000000000 1700000 100000

Bir xil chegarada n² 10 milliard, n log n 1,7 million. Birinchisi umuman sig'maydi — demak u haqda o'ylashning ham hojati yo'q.

Chegara jadvali

4-darsdagi jadval bu yerda qayta ishlatiladi, lekin endi teskari tomonga: chegaradan usulga o’tish uchun.

Chegara	Sig’adigan yechim	Odatda nima
n ≤ 12	n!	barcha o’rin almashtirishlar
n ≤ 20	2ⁿ	bitmask, ichki to’plamlar
n ≤ 500	n³	uch sikl, Floyd, panjarada DP
n ≤ 5000	n²	juftliklar, ikki o’lchovli DP
n ≤ 10⁵	n log n	saralash, ikkilik qidiruv, uyum
n ≤ 10⁶	n	bir yurish, prefiks, DSU, elak

Python’da har qatorni bir pog’ona pastga surib o’qing (37-dars).

Alomatdan usulga

Chegara variantlarni qisqartiradi, alomat esa tanlaydi. Bu jadval yodlash uchun emas — masala o’qiyotganda ochib qarash uchun.

Shartdagi alomat	Birinchi taxmin
«eng kam qadam», vaznsiz bog’lanishlar	BFS (19-dars)
«eng arzon yo’l», musbat vaznlar	Dijkstra (24-dars)
«nechta guruh», «bog’langanmi»	DFS yoki DSU (18, 30-darslar)
«nima nimadan keyin»	topologik saralash (22-dars)
«nechta usul», «eng kam narx», javob kichiklardan yig’iladi	DP (25–29-darslar)
«eng kichik yetadigan qiymat», tekshirish oson	javob bo’yicha ikkilik qidiruv (13-dars)
ketma-ket oraliq, «eng uzun», «yig’indisi oshmaydigan»	sirpanuvchi oyna (10-dars)
«oraliq yig’indisi», ma’lumot o’zgarmaydi	prefiks (5-dars)
«oraliq yig’indisi», ma’lumot o’zgaradi	Fenwick (32-dars)
«bormi», «takrorlanganmi»	to’plam yoki lug’at (9-dars)
«eng ko’p tanlash», intervallar	saralash + ochko’zlik (14-dars)
«keyingi katta element»	monoton stek (11-dars)

◆Asosiy g'oya

Jadval birinchi taxmin beradi, javob emas. Taxmin noto’g’ri bo’lishi normal — muhimi siz bo’sh varaqdan boshlamaysiz. Va yana bir narsa: to’liq izlashni har doim eslab turing. U qisman ball keltiradi va tez yechim uchun etalon bo’ladi.

Skiena xaritasi

Bu usul «Algorithm Design Manual» kitobidan olingan va u bitta oddiy fikrga asoslanadi: yangi masala kamdan-kam yangi bo’ladi.

Masalani ko’rganingizda uni tanish masalaga aylantirishga urinib ko’ring. Panjara — grafmi? Satr — ro’yxatmi? «Har juftlik» degan savol saralashdan keyin «har qo’shni» ga aylanmaydimi? Ko’p masalada butun qiyinlik shu bitta aylantirishda.

Sinab ko’r

Vizualda oltita masala uchun faqat chegara ko’rsatiladi va usul tanlanadi. Kod yozilmaydi.

Masaladan algoritmga — chegara nima deydi

Har masala uchun avval chegara o'qiladi, keyingina usul tanlanadi.

Shartdagi chegara raqami qaysi murakkablikdagi yechim sig'ishini aytadi va usul shunga qarab tanlanadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. Oltita masala. Kod yozilmaydi — faqat chegaraga qarab usul tanlanadi. Olimpiadada bu qaror birinchi besh daqiqada qabul qilinadi.
2. 1-masala, chegara 20. Chegara juda kichik. Bunday raqam deyarli har doim to'liq izlashga ochiq taklif: har element uchun ikki variant. Usul: 2^n.
3. 2-masala, chegara 5000. n kvadrat 25 million — sig'adi. Har juftlikni ko'rish mumkin, hiyla shart emas. Usul: n^2.
4. 3-masala, chegara 10^5. n kvadrat 10 milliard bo'lardi. Saralash yoki ikkilik qidiruv kerak. Usul: n log n.
5. 4-masala, chegara 10^5. Shartda uchlar va bog'lanishlar bor, savol esa «eng kam qadam». Vaznsiz graf — BFS. Usul: BFS.
6. 5-masala, chegara 10^6. «Nechta usul» yoki «eng kam narx» so'ralgan va javob kichikroq javoblardan yig'iladi. Usul: DP.
7. 6-masala, chegara 300. n kub 27 million — sig'adi. Kichik chegara qimmatroq yechimga ruxsat beradi. Usul: n^3.
8. Chegara — muallifning ochiq ishorasi. U yechimni aytmaydi, lekin qaysi yechim SIG'MASLIGINI aniq aytadi va bu variantlarni keskin qisqartiradi.

masala

102132435465

chegara

20500010^510^510^6300

usul

Oltita masala. Kod yozilmaydi — faqat chegaraga qarab usul tanlanadi. Olimpiadada bu qaror birinchi besh daqiqada qabul qilinadi.

Tahlil qilingan masala0

OrqagaO‘ynatishOldinga1/8Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

38 / 40

MasalaShartda n ≤ 200000 va «eng ko'p to'qnashmaydigan intervalni tanlang» deb yozilgan.

Taklif qilingan mulohaza

1. 1Intervallar bor — demak bu 14-darsdagi masala.
2. 2Tugash vaqti bo‘yicha saralab, ochko‘z tanlaymiz.
3. 3Murakkablik n log n — chegaraga sig‘adi.
4. 4Demak yechim tayyor, kod yozishni boshlaymiz.

Bu javobning 1-qismi noto'g'ri. Shoshilinch tanish. «Intervallar» so'zi bir necha xil masalani bildiradi: TANLASH (14-dars, ochko'zlik), SANASH (38-dars mashqi, hodisalar), BIRLASHTIRISH (saralash + yurish), ZALLAR SONI (uyum). Avval savolni oxirigacha o'qish kerak: bu yerda «tanlang» deyilgan, lekin ko'p masalada «nechta» deb so'raladi va usul butunlay boshqa bo'ladi.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Masalani o'qigach birinchi navbatda nima yoziladi?

Javobni ko'rish

Chegara raqami. U qaysi murakkablik sig’ishini aytadi va variantlarning yarmini darhol o’chiradi.

2n ≤ 20 chegarasi qanday ishora?

Javobni ko'rish

2ⁿ yechimga: bitmask, barcha ichki to’plamlar. n ≤ 12 bo’lsa n!, ya’ni o’rin almashtirishlar.

3«Eng kichik yetadigan qiymat» degan savol nimani ishora qiladi?

Javobni ko'rish

Javob bo’yicha ikkilik qidiruvni (13-dars) — ayniqsa berilgan javobni tekshirish oson bo’lsa.

4Skiena xaritasining asosiy fikri nima?

Javobni ko'rish

Yangi masalani tanish masalaga aylantirish. Ko’p masalada butun qiyinlik shu aylantirishda, algoritmda emas.

5Alomat jadvali javob beradimi?

Javobni ko'rish

Yo’q, birinchi taxmin beradi. Shartni oxirigacha o’qish shart: bir xil tuzilma bir necha xil savolga xizmat qiladi.

Masalalar

Masalalar — avval usulni ayting, keyin yozing

3 ta

• Restaurant CustomersCSES 1619oson

  Intervallar, lekin savol «nechta» — tanlash emas. Hodisalar bo‘yicha yuring.

• Traffic LightsCSES 1163qiyin

  Teskari o‘ylang: chiroqlarni qo‘shish o‘rniga, oxiridan boshlab olib tashlang.

• Nested Ranges CountCSES 2169qiyin

  Yana intervallar, yana boshqa savol. Saralash + Fenwick (32-dars).

Lokal mashq: mashqlar/38-xona/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Chegara jadvalini va alomat jadvalini daftaringizga ko’chiring. Keyin bu moduldagi o’zingiz yechgan beshta masalani oling va har biri uchun alomatni topib jadval bilan solishtiring — mos keldimi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

CSES saytidan o’nta masala tanlang va faqat shartini o’qib, har biri uchun usulni yozing. Keyin ikkitasini yeching va taxminingiz to’g’ri chiqqanini tekshiring.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Bir masalani ataylab uch xil usulda yechishga urinib ko’ring: to’liq izlash, o’rta yechim va optimal. Uchtasini vaqt bo’yicha o’lchang. Bu mashq olimpiadada qisman ball olishni o’rgatadi.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim