Tadqiqot ishi, ehtimol, bizning treningimizning eng qiziqarli qismidir. Maqsad, hali universitetda o'qish paytida o'zingizni tanlagan yo'nalishda sinab ko'rishdir. Masalan, dasturiy ta'minot muhandisligi va mashinani o'rganish yo'nalishlari talabalari ko'pincha kompaniyalarga tadqiqot qilish uchun boradilar (asosan JetBrains yoki Yandex, lekin nafaqat).
Ushbu postda men kompyuter fanlari bo'yicha loyiham haqida gapiraman. Mening ishimning bir qismi sifatida men eng mashhur NP-qiyin muammolardan birini hal qilishning yondashuvlarini o'rganib chiqdim va amalda qo'lladim: cho'qqilarni qoplash muammosi.
Hozirgi vaqtda NP-qiyin muammolarga qiziqarli yondashuv juda tez rivojlanmoqda - parametrlashtirilgan algoritmlar. Men sizni tezlashtirishga harakat qilaman, sizga bir nechta oddiy parametrlashtirilgan algoritmlarni aytib beraman va menga juda ko'p yordam bergan bitta kuchli usulni tasvirlab beraman. Men o‘z natijalarimni PACE Challenge tanlovida taqdim etdim: ochiq testlar natijalariga ko‘ra, mening yechimim uchinchi o‘rinni egalladi va yakuniy natijalar 1 iyul kuni ma’lum bo‘ladi.
Men haqimda
Mening ismim Vasiliy Alferov, men Sankt-Peterburgdagi Milliy tadqiqot universiteti Oliy iqtisodiyot maktabida uchinchi kursni tamomlayapman. Moskvadagi 179-sonli maktabda o‘qib, informatika bo‘yicha olimpiadalarda muvaffaqiyatli ishtirok etgan maktab davrimdan boshlab algoritmlarga qiziqaman.
Parametrlangan algoritmlar bo'yicha cheklangan miqdordagi mutaxassislar barga kiradi ...
Kitobdan olingan misol
Tasavvur qiling-a, siz kichik shaharchada bar qo'riqchisisiz. Har juma kuni shaharning yarmi sizning baringizga dam olish uchun keladi, bu sizga juda ko'p muammo tug'diradi: janjallarning oldini olish uchun siz bezori mijozlarni bardan chiqarib yuborishingiz kerak. Oxir-oqibat, siz charchadingiz va profilaktika choralarini ko'rishga qaror qilasiz.
Sizning shahringiz kichik bo'lganligi sababli, qaysi juftliklar barda birga bo'lishsa, jang qilishlari mumkinligini aniq bilasiz. ro'yxati bormi n bugun kechqurun barga keladigan odamlar. Siz hech kim janjal qilmasdan, ba'zi shaharliklarni bardan olib tashlashga qaror qildingiz. Shu bilan birga, sizning xo'jayinlaringiz daromadni yo'qotishni xohlamaydilar va agar siz undan ko'p narsaga ruxsat bermasangiz, baxtsiz bo'lishadi. k odamlar.
Afsuski, sizning oldingizda turgan muammo klassik NP-qiyin muammodir. Siz uni shunday deb bilishingiz mumkin , yoki cho'qqilarni qoplash muammosi sifatida. Bunday muammolar uchun, umumiy holatda, maqbul vaqt ichida ishlaydigan algoritmlar mavjud emas. Aniqrog'i, isbotlanmagan va juda kuchli gipoteza ETH (eksponensial vaqt gipotezasi) bu muammoni o'z vaqtida hal qilib bo'lmasligini aytadi. , ya'ni siz to'liq qidiruvdan ko'ra sezilarli darajada yaxshiroq narsani o'ylay olmaysiz. Masalan, baringizga kimdir keladi, deylik n = 1000 Inson. Keyin to'liq qidiruv bo'ladi taxminan mavjud variantlar - aqldan ozgan miqdor. Yaxshiyamki, sizning rahbariyatingiz sizga cheklov berdi k = 10, shuning uchun siz takrorlashingiz kerak bo'lgan kombinatsiyalar soni ancha kichik: o'n elementning kichik to'plamlari soni . Bu yaxshiroq, lekin u hatto kuchli klasterda ham bir kunda hisoblanmaydi.
Barga tashrif buyuruvchilar o'rtasidagi keskin munosabatlarning ushbu konfiguratsiyasida janjal ehtimolini yo'q qilish uchun siz Bob, Daniel va Fedorni chetlab o'tishingiz kerak. Faqat ikkitasi ortda qoladigan hech qanday yechim yo'q.
Bu taslim bo'lish va hammaga ruxsat berish vaqti keldi deganimi? Keling, boshqa variantlarni ko'rib chiqaylik. Masalan, siz faqat juda ko'p odamlar bilan kurashishi mumkin bo'lganlarni kirita olmaysiz. Agar kimdir hech bo'lmaganda jang qila olsa k+1 boshqa odam bo'lsa, unda siz uni ichkariga kirita olmaysiz - aks holda siz hammani olib qo'yishingiz kerak bo'ladi k+1 shahar aholisi, u bilan kurashishi mumkin, bu albatta rahbariyatni xafa qiladi.
Ushbu printsip bo'yicha qo'lingizdan kelganini tashlab keting. Shunda hamma boshqa hech kim bilan kurashishi mumkin k odamlar. Ularni tashqariga tashlash k odam, siz boshqa hech narsa oldini olish mumkin ziddiyatlar. Bu shuni anglatadiki, agar ko'proq bo'lsa Agar biror kishi kamida bitta mojaroga aralashgan bo'lsa, unda siz ularning barchasini oldini ololmaysiz. Albatta, siz mutlaqo ziddiyatli bo'lmagan odamlarni kiritasiz, shuning uchun siz ikki yuz kishidan o'n o'lchamdagi barcha kichik guruhlardan o'tishingiz kerak. Taxminan bor , va bu operatsiyalar soni allaqachon klasterda tartiblangan bo'lishi mumkin.
Agar siz umuman nizo bo'lmagan shaxslarni xavfsiz qabul qila olsangiz, unda faqat bitta mojaroda qatnashganlar haqida nima deyish mumkin? Darhaqiqat, raqibga eshikni yopgan holda ham ularni ichkariga kiritish mumkin. Haqiqatan ham, agar Elis faqat Bob bilan ziddiyatga ega bo'lsa, agar biz Elisni ikkalasidan chiqarib yuborsak, biz yutqazmaymiz: Bobda boshqa mojarolar bo'lishi mumkin, lekin Elisda ular yo'q. Bundan tashqari, ikkalamizni ham ichkariga kiritmaslikning ma'nosi yo'q. Bunday operatsiyalardan keyin boshqa narsa qolmaydi hal qilinmagan taqdiri bilan mehmonlar: bizda faqat bor har birida ikkita ishtirokchi va har biri kamida ikkita ishtirokchi bo'lgan nizolar. Shunday qilib, faqat tartiblash qoladi noutbukda yarim kunni osongina ko'rib chiqish mumkin bo'lgan variantlar.
Aslida, oddiy mulohaza yuritish bilan siz yanada jozibali sharoitlarga erishishingiz mumkin. E'tibor bering, biz barcha nizolarni albatta hal qilishimiz kerak, ya'ni har bir qarama-qarshi juftlikdan biz ruxsat bermaydigan kamida bitta odamni tanlang. Keling, quyidagi algoritmni ko'rib chiqaylik: har qanday to'qnashuvni oling, undan biz bir ishtirokchini olib tashlaymiz va qolgan qismidan rekursiv boshlaymiz, keyin ikkinchisini olib tashlaymiz va rekursiv tarzda boshlaymiz. Biz har qadamda kimnidir tashlab yuborganimiz sababli, bunday algoritmning rekursiya daraxti ikkilik chuqurlik daraxtidir. k, shuning uchun umumiy algoritm ishlaydi qayerda n uchlari soni, va m - qovurg'alar soni. Bizning misolimizda bu o'n millionga yaqin, bu faqat noutbukda emas, balki mobil telefonda ham bir soniya ichida hisoblanishi mumkin.
Yuqoridagi misol misoldir parametrlashtirilgan algoritm. Parametrlangan algoritmlar o'z vaqtida bajariladigan algoritmlardir f(k) poli(n)qayerda p - polinom, f ixtiyoriy hisoblanuvchi funksiyadir va k - muammoning o'lchamidan ancha kichik bo'lishi mumkin bo'lgan ba'zi parametr.
Ushbu algoritm oldidagi barcha mulohazalar misol keltiradi yadrolash parametrlangan algoritmlarni yaratishning umumiy usullaridan biridir. Yadrolash - muammo hajmini parametr funktsiyasi bilan cheklangan qiymatga kamaytirish. Olingan muammo ko'pincha yadro deb ataladi. Shunday qilib, cho'qqilarning darajalari haqida oddiy fikr yuritish orqali biz Vertex Cover muammosi uchun javobning o'lchami bilan parametrlangan kvadrat yadro oldik. Bu vazifa uchun tanlashingiz mumkin boʻlgan boshqa sozlamalar ham mavjud (masalan, Vertex Cover Above LP), lekin bu biz muhokama qiladigan sozlama.
Pace Challenge
Raqobat (The Parameterized Algorithms and Computational Experiments Challenge) 2015 yilda parametrlashtirilgan algoritmlar va hisoblash muammolarini hal qilishda amalda qoʻllaniladigan yondashuvlar oʻrtasidagi aloqani oʻrnatish uchun yaratilgan. Dastlabki uchta musobaqa grafikning daraxt kengligini topishga bag'ishlandi (), Shtayner daraxtini qidirish () va tsikllarni kesuvchi cho'qqilar to'plamini qidirish (). Bu yil siz o'zingizni sinab ko'rishingiz mumkin bo'lgan muammolardan biri yuqorida tavsiflangan cho'qqilarni qoplash muammosi edi.
Musobaqa har yili mashhurlik kasb etmoqda. Agar dastlabki ma'lumotlarga ishonsangiz, bu yil faqat cho'qqilarni qoplash muammosini hal qilish uchun musobaqada 24 ta jamoa ishtirok etdi. Ta'kidlash joizki, tanlov bir necha soat yoki hatto bir hafta emas, balki bir necha oy davom etadi. Jamoalar adabiyotni o‘rganish, o‘zlarining original g‘oyasini o‘ylab topish va uni amalga oshirishga harakat qilish imkoniyatiga ega. Aslini olganda, bu tanlov tadqiqot loyihasidir. Eng samarali yechimlar boʻyicha gʻoyalar va gʻoliblarni taqdirlash konferentsiya bilan birgalikda oʻtkaziladi. (Parametrlangan va aniq hisoblash bo'yicha xalqaro simpozium) Evropadagi eng yirik yillik algoritmik yig'ilishning bir qismi sifatida . Tanlovning o'zi haqida batafsil ma'lumotni quyidagi manzildan olishingiz mumkin , va o'tgan yillar natijalari yolg'on .
Yechim diagrammasi
Cho'qqilarni qoplash muammosini hal qilish uchun men parametrlangan algoritmlardan foydalanishga harakat qildim. Ular, odatda, ikki qismdan iborat: soddalashtirish qoidalari (bu ideal holda yadroga olib keladi) va bo'linish qoidalari. Soddalashtirish qoidalari polinom vaqtida kirishni oldindan qayta ishlashdir. Bunday qoidalarni qo'llashdan maqsad muammoni ekvivalent kichikroq muammoga qisqartirishdir. Soddalashtirish qoidalari algoritmning eng qimmat qismidir va bu qismni qo'llash umumiy ish vaqtiga olib keladi. oddiy polinom vaqti o'rniga. Bizning holatda, bo'linish qoidalari har bir cho'qqi uchun siz uni yoki uning qo'shnisini javob sifatida qabul qilishingiz kerakligiga asoslanadi.
Umumiy sxema quyidagicha: biz soddalashtirish qoidalarini qo'llaymiz, keyin biz ba'zi bir cho'qqini tanlaymiz va ikkita rekursiv qo'ng'iroq qilamiz: birinchisida biz uni javob sifatida qabul qilamiz, ikkinchisida esa uning barcha qo'shnilarini olamiz. Bu cho'qqi bo'ylab bo'linish (tarmoqlanish) deb ataladigan narsa.
Keyingi xatboshida ushbu sxemaga aynan bitta qo'shimcha kiritiladi.
Qoidalarni ajratish (brunching) uchun g'oyalar
Keling, bo'linish sodir bo'ladigan tepalikni qanday tanlashni muhokama qilaylik.
Asosiy g'oya algoritmik ma'noda juda ochko'zdir: keling, maksimal darajadagi cho'qqini olamiz va u bo'ylab ajratamiz. Nima uchun u yaxshiroq ko'rinadi? Chunki rekursiv qo'ng'iroqning ikkinchi tarmog'ida biz shu tarzda juda ko'p cho'qqilarni olib tashlaymiz. Siz qolgan kichik grafikga ishonishingiz mumkin va biz tezda uning ustida ishlashimiz mumkin.
Ushbu yondashuv, allaqachon muhokama qilingan oddiy yadrolash usullari bilan o'zini yaxshi ko'rsatadi va o'lchamdagi bir necha ming cho'qqilarning ba'zi sinovlarini hal qiladi. Ammo, masalan, kubik grafiklar uchun (ya'ni, har bir uchining darajasi uchta bo'lgan grafiklar) yaxshi ishlamaydi.
Juda oddiy fikrga asoslangan yana bir g'oya bor: agar grafik uzilgan bo'lsa, uning bog'langan komponentlari bo'yicha muammoni oxirida javoblarni birlashtirib, mustaqil ravishda hal qilish mumkin. Aytgancha, bu sxemadagi kichik va'da qilingan modifikatsiya bo'lib, u yechimni sezilarli darajada tezlashtiradi: ilgari, bu holda, biz komponentlarning javoblarini hisoblash uchun vaqt mahsuloti uchun ishlaganmiz, ammo hozir biz ishlaymiz. summasi. Va dallanishni tezlashtirish uchun siz bog'langan grafikni uzilganga aylantirishingiz kerak.
Buni qanday qilish kerak? Agar grafikda artikulyatsiya nuqtasi bo'lsa, siz unga qarshi kurashishingiz kerak. Artikulyatsiya nuqtasi shunday cho'qqi bo'lib, u olib tashlanganida, grafik aloqani yo'qotadi. Grafikdagi barcha ulanish nuqtalarini chiziqli vaqtda klassik algoritm yordamida topish mumkin. Ushbu yondashuv dallanishni sezilarli darajada tezlashtiradi.
Tanlangan cho'qqilarning birortasi olib tashlanganida, grafik bog'langan komponentlarga bo'linadi.
Biz buni qilamiz, lekin biz ko'proq narsani xohlaymiz. Misol uchun, grafikdagi kichik cho'qqilarni kesib oling va undan cho'qqilar bo'ylab ajrating. Men biladigan minimal global cho'qqilarni kesishning eng samarali usuli bu kubik vaqt ichida qurilgan Gomori-Xu daraxtidan foydalanishdir. PACE Challenge dasturida grafikning odatiy o‘lchami bir necha ming cho‘qqidan iborat. Bunday vaziyatda rekursiya daraxtining har bir tepasida milliardlab operatsiyalar bajarilishi kerak. Ma'lum bo'lishicha, muammoni ajratilgan vaqt ichida hal qilishning iloji yo'q.
Keling, yechimni optimallashtirishga harakat qilaylik. Bir juft cho'qqi o'rtasida kesilgan minimal cho'qqini maksimal oqimni tuzadigan har qanday algoritm orqali topish mumkin. Siz uni bunday tarmoqqa kiritishingiz mumkin , amalda u juda tez ishlaydi. Ish vaqti uchun taxminni nazariy jihatdan isbotlash mumkinligiga shubham bor , bu allaqachon juda maqbuldir.
Men bir necha marta tasodifiy cho'qqilar juftlari orasidagi kesmalarni izlashga va eng muvozanatlisini olishga harakat qildim. Afsuski, bu ochiq PACE Challenge testida yomon natijalar berdi. Men buni eng yuqori darajadagi cho'qqilarni ajratuvchi algoritm bilan solishtirdim, ularni tushish chuqurligi bo'yicha cheklov bilan boshqardim. Shu tarzda kesimni topishga urinayotgan algoritm kattaroq grafiklarni ortda qoldirdi. Buning sababi shundaki, kesmalar juda muvozanatsiz bo'lib chiqdi: 5-10 ta burchakni olib tashlaganingizdan so'ng, faqat 15-20 tasini ajratish mumkin edi.
Shuni ta'kidlash kerakki, nazariy jihatdan eng tezkor algoritmlar haqidagi maqolalarda bo'linish uchun cho'qqilarni tanlashning ancha ilg'or usullari qo'llaniladi. Bunday texnikalar juda murakkab amalga oshirishga ega va ko'pincha vaqt va xotira nuqtai nazaridan yomon ishlashga ega. Amaliyot uchun juda maqbul bo'lganlarni aniqlay olmadim.
Soddalashtirish qoidalarini qanday qo'llash kerak
Bizda yadrolash bo'yicha g'oyalar allaqachon mavjud. Sizga eslatib o'taman:
- Agar izolyatsiya qilingan cho'qqi bo'lsa, uni o'chiring.
- Agar 1-darajali cho'qqi bo'lsa, uni olib tashlang va javob sifatida qo'shnisini oling.
- Hech bo'lmaganda darajaning cho'qqisi bo'lsa k+1, uni qaytarib oling.
Birinchi ikkitasida hamma narsa aniq, uchinchisida bitta hiyla bor. Agar bar haqidagi kulgili muammoda bizga yuqori chegara berilgan bo'lsa k, keyin PACE Challenge-da siz faqat minimal o'lchamdagi vertex qopqog'ini topishingiz kerak. Bu qidiruv muammolarining qarorlar muammosiga o'zgarishi; ko'pincha muammolarning ikki turi o'rtasida farq yo'q. Amalda, agar biz cho'qqilarni qoplash muammosi uchun hal qiluvchi yozayotgan bo'lsak, farq bo'lishi mumkin. Masalan, uchinchi nuqtada bo'lgani kabi.
Amalga oshirish nuqtai nazaridan, davom etishning ikki yo'li mavjud. Birinchi yondashuv iterativ chuqurlashtirish deb ataladi. Bu quyidagicha: biz javobni pastdan oqilona cheklash bilan boshlashimiz mumkin va keyin bu cheklovdan rekursiyada bu cheklovdan pastroq bo'lmasdan, yuqoridan javobga cheklov sifatida ushbu cheklovdan foydalanib, algoritmimizni ishga tushirishimiz mumkin. Agar biz qandaydir javobni topgan bo'lsak, u optimal bo'lishi kafolatlanadi, aks holda biz bu chegarani bittaga oshirib, yana boshlashimiz mumkin.
Yana bir yondashuv joriy optimal javobni saqlash va topilganda bu parametrni o'zgartirib, kichikroq javobni izlashdir k qidiruvda keraksiz novdalarni ko'proq kesish uchun.
Bir necha tungi tajribalarni o'tkazganimdan so'ng, men ushbu ikki usulning kombinatsiyasiga qaror qildim: birinchidan, men algoritmimni qidiruv chuqurligining qandaydir chegarasi bilan ishlataman (uni asosiy yechimga nisbatan ahamiyatsiz vaqt talab qiladigan tarzda tanlayman) va eng yaxshisini ishlataman. javobning yuqori chegarasi sifatida topilgan yechim - ya'ni xuddi shu narsaga k.
2-darajali cho'qqilar
Biz 0 va 1 darajali cho'qqilarni ko'rib chiqdik. Ma'lum bo'lishicha, buni 2-darajali cho'qqilar bilan bajarish mumkin, ammo bu grafikdan murakkabroq operatsiyalarni talab qiladi.
Buni tushuntirish uchun biz cho'qqilarni qandaydir tarzda belgilashimiz kerak. 2-darajali cho'qqini cho'qqi deb ataymiz v, va uning qo'shnilari - tepaliklar x и y. Keyinchalik bizda ikkita holat bo'ladi.
- qachon x и y - qo'shnilar. Keyin javob berishingiz mumkin x и yva v o'chirish. Darhaqiqat, bu uchburchakdan kamida ikkita cho'qqi evaziga olinishi kerak va agar biz olsak, albatta yo'qotmaymiz. x и y: ular, ehtimol, boshqa qo'shnilari bor, va v ular yo'q.
- qachon x и y - qo'shnilar emas. So'ngra barcha uch uchlarini bittaga yopishtirish mumkinligi aytiladi. G'oya shundan iboratki, bu holda optimal javob bor, biz ham qabul qilamiz v, yoki ikkala uchi x и y. Bundan tashqari, birinchi holda, biz javob sifatida barcha qo'shnilarni qabul qilishimiz kerak x и y, lekin ikkinchisida bu kerak emas. Bu biz yopishgan cho'qqini javob sifatida qabul qilmagan va biz qabul qilgan holatlarga to'liq mos keladi. Shuni ta'kidlash kerakki, ikkala holatda ham bunday operatsiyadan javob bittaga kamayadi.
Shuni ta'kidlash kerakki, ushbu yondashuvni adolatli chiziqli vaqtda aniq amalga oshirish juda qiyin. Cho'qqilarni yopishtirish murakkab operatsiya bo'lib, siz qo'shnilar ro'yxatini nusxalashingiz kerak. Agar bu beparvolik bilan amalga oshirilsa, siz asimptotik suboptimal ish vaqtiga ega bo'lishingiz mumkin (masalan, har bir yopishtirishdan keyin ko'plab qirralarning nusxasini olsangiz). Men 2-darajali cho'qqilardan to'liq yo'llarni topishga va bir qator maxsus holatlarni tahlil qilishga qaror qildim, masalan, bunday cho'qqilardan yoki bittadan tashqari barcha shunday cho'qqilardan aylanishlar.
Bundan tashqari, rekursiyadan qaytganimizda, biz grafikni asl ko'rinishiga qaytarishimiz uchun, bu operatsiya teskari bo'lishi kerak. Buni ta'minlash uchun men birlashtirilgan cho'qqilarning chekka ro'yxatlarini tozalamadim, keyin esa qaysi qirralarning qayerga borishi kerakligini bilardim. Grafiklarning bunday amalga oshirilishi ham aniqlikni talab qiladi, ammo u adolatli chiziqli vaqtni ta'minlaydi. Va bir necha o'n minglab qirralarning grafiklari uchun u protsessor keshiga mos keladi, bu tezlikda katta afzalliklarni beradi.
Chiziqli yadro
Va nihoyat, yadroning eng qiziqarli qismi.
Avvaliga shuni esda tutingki, ikki tomonlama grafiklarda minimal cho'qqi qoplamasi yordamida topish mumkin . Buning uchun siz algoritmdan foydalanishingiz kerak u erda maksimal moslikni topish uchun va keyin teoremadan foydalaning .
Chiziqli yadro g'oyasi quyidagicha: birinchi navbatda biz grafikni ikkiga ajratamiz, ya'ni har bir cho'qqi o'rniga. v ikkita tepalikni qo'shamiz и , va har bir chekka o'rniga u - v ikkita qovurg'a qo'shamiz и . Olingan grafik ikki tomonlama bo'ladi. Undagi minimal cho'qqi qoplamini topamiz. Asl grafikning ba'zi uchlari u erga ikki marta, ba'zilari faqat bir marta, ba'zilari esa hech qachon etib boradi. Nemxauzer-Trotter teoremasida aytilishicha, bu holda bir marta ham urmagan cho'qqilarni olib tashlash va ikki marta urilganlarni qaytarib olish mumkin. Bundan tashqari, uning aytishicha, qolgan cho'qqilarning (bir marta urilgan) kamida yarmini javob sifatida qabul qilishingiz kerak.
Biz endigina ortiq qoldirmaslikni o'rgandik 2k cho'qqilari Haqiqatan ham, agar qolgan javob barcha cho'qqilarning kamida yarmi bo'lsa, unda jami cho'qqilardan ko'pi yo'q. 2k.
Bu erda men oldinga kichik qadam tashlashga muvaffaq bo'ldim. Shu tarzda tuzilgan yadro ikki tomonlama grafikda qanday minimal cho'qqi qoplamini olganimizga bog'liqligi aniq. Qolgan cho'qqilar soni minimal bo'lishi uchun bittasini olishni xohlayman. Ilgari ular buni faqat o'z vaqtida amalga oshirishlari mumkin edi . O'sha paytda men ushbu algoritmni amalga oshirishni o'ylab topdim , shunday qilib, bu yadroni har bir tarmoqlanish bosqichida yuz minglab cho'qqilarning grafiklarida izlash mumkin.
natija
Amaliyot shuni ko'rsatadiki, mening yechimim bir necha yuz cho'qqi va bir necha ming qirralarning sinovlarida yaxshi ishlaydi. Bunday sinovlarda yarim soat ichida yechim topilishini kutish mumkin. Qabul qilinadigan vaqt ichida javob topish ehtimoli, qoida tariqasida, agar grafada etarlicha ko'p miqdordagi yuqori darajadagi, masalan, 10 daraja va undan yuqori burchaklar bo'lsa, ortadi.
Tanlovda ishtirok etish uchun yechimlar yuborilishi kerak edi . U erda taqdim etilgan ma'lumotlarga qaraganda , ochiq testlardagi yechimim yigirmatadan uchinchi o'rinni egallaydi, ikkinchidan katta bo'shliq. Rostini aytsam, tanlovning o'zida yechimlar qanday baholanishi to'liq aniq emas: masalan, mening yechimim to'rtinchi o'rindagi yechimga qaraganda kamroq sinovlardan o'tadi, ammo o'tganlarida u tezroq ishlaydi.
Yopiq test natijalari XNUMX iyul kuni ma'lum bo'ladi.
Manba: www.habr.com