GTC Open October Part II

 10A - Урвууг тоолох

f(n, k)-гаар k урвуу хостой n сэлгэмэлийн тоог тэмдэглэе.

1-ээр эхэлсэн сэлгэмэлийн k урвуу хостой сэлгэмэлийн тоо f(n-1, k). Яагаад?

Харин 1 гэсэн тоо сэлгэмэлийн эхнээсээ 2 дахь байрлалд орвол f(n-1, k-1) байна. Яагаад гэхээр 2 дахь байрлалд орох болгондоо хос үүсгэнэ гэсэн үг.

За үүнтэй ижил 1 гэсэн тоо 3, 4.. гээд байрлаад явбал бодлогын хариу яаж нэмэгдэх вэ гэдэгийг хараарай. Тэгэхээр ерөнхий тохиолдолд:

f(n, k) = sum(f(n-1, k-i)) for (0<=i<n) болно.

Дээрх томъёогоор бодвол бодолт O(N^2 * K) болно. Хугацааны хязгаарлалт хэтрэх нь ойлгомжтой.

Томъёогоо эмхэтгээд үзвэл f(n, k) = f(n, k-1) + f(n-1, k) - f(n-1, k-1) болж бодолт O(N*K). Санах ойгоо хэмнэх үүднээс заавал n*k*sizeof(int) авч явах хэрэг байна уу? f(n-1, k), f(n, k)-г хадгалаад явчихаж бас болно.

Бодолт

10D - Graph

Энэ бодлого бол Articulation Point-той холбоотой бодлого.

За би уг нь Таржаны алгоритмыг энэ пост дээрээ тайлбарлая гэж бодож энэ удаагийн тэмцээний анализыг 2 хэсэгтэй болгосон юм. Даанч ажил ерөөсөө болж өгөхгүй завгүй байгаа тул таржаны алгоритм тайлбарлахыг дараа болоё. Бодолтруугаа шууд ороё, уг нь их амархан.

Аль нэг оройгоос гүний нэвтрэлт хийгээд гүний нэвтрэлтийн модоо үүсгэе

1 дугаартай хүсэлтийн хувьд:

a, b, c, d гэж үзье. Мөн гүний нэвтрэлтийн модны хувьд d орой нь c оройн доор байрлаж байгаа гэж үзье. Үнэндээ бидэнд d орой хамгийн чухал. d орой articulation point биш буюу ямар нэгэн циклд агуулагдсан бол c-d ирмэгийг устгахад a->b очиж чадах нь ойлгомжтой. d орой харин articulation point бол бид a болон b орой d оройн доор хоюул оршиж байна уу эсвэл дээр хоюул оршиж байна уу гэдэгийг шалгах хэрэгтэй.

2 дугаартайг ч гэсэн графын хаана байрлаж байгаагаас шалтгаалаад тооцоолчихно, кодноос дэлгэрэнгүй хараарай. Асууж тодруулах зүйл байвал коммент үлдээгээрэй, дуртай бас шуурхай хариулах болно оо

Бодолт

GTC Open October

 Хоёр дахь тэмцээн маань амжилтттай болж өнгөрлөө. Тэмцээнд нийт 29 хүн бүртгүүлж 13 оролцогч оролцлоо. Цаг заваа зохицуулан хэрэг гаргаж оролцсон оролцогч нартаа их баярлалаа.

Ингээд эхний 3-н байр:

1-р байранд _mrsn_ 340 оноотой

2-р байранд MazaalaiMNGL 330 оноотой

3-р байранд Turkhuu 330 оноотой 

тэмцээнийг тэргүүллээ. Дээрх оролцогч нар тэмцээний facebook хуудсаар холбогдож шагналаа авна уу.

Бодлогын анализдаа ороё.

10B - Zoom

Энэ удаагийн тэмцээний хамгийн амархан бодлого. Шууд симулац хийгээд хэвлэчихэж болно эсвэл жижигхэн мат ашиглаад шинээр үүсэх текстийн (i, j) дэх тэмдэгт нь хуучин текстийн (i/zr, j/zc)дэх тэмдэгт гэдэгийг харчихвал арай бага код бичиж болох юм.

Бодолт

10C - Count

Зөв хаалт зохион байгуулах бодлого. Иймэрхүү бодлого ихэвчлэн рекурс буюу стэк өгөгдөлийн бүтэцээр шийдэгддэг.

Шууд хүчээр шалгаад бодвол квадрат бодолт үүсэж хугацааны хязгаарлалт хэтэрсэн алдаа авна.

Эхлээд бодлогоо дараалалд байгаа бүх хүн ялгаатай өндөртэй үед бодоё.

Бодлогын өгүүлбэрээс ажиглавал А гэсэн хүн өөрөөс нь хойно зогсож байгаа хүмүүсээс хамгийн эхний өөрөөс нь эрс өндөр Б гэсэн хүнээс хойно зогсож байгаа хүмүүсийг харахгүй нь тодорхой буюу А-н хувьд Б-ээс хойно зогсох хүмүүс хамаагүй болж байгаа юм: Тэгэхээр яг ийм А Б гэсэн интервалыг дэд дараалал гэж үзье.

Хүмүүсийг зогсож буй дарааллаар нь 1, 1-ээр нь шалгаад явая. Дэд дараалалд шинээр орж ирэх хүн дандаа хамгийн хойно зогсож байгаа хүнээс намхан эсвэл ижил өндөртэй хүн байх нь ойлгомжтой. Мөн дэд дараалалд хүн шаардлага хангаад нэмж орж ирэх болгонд бодлогын хариу 1-ээр нэмэгдэнэ. Яагаад гэвэл хөрш хүмүүс бүгд бие биенээ харах учир.

Одоо дэд дараалалд маань хамгийн хойно зогсож байгаа хүнээс өндөр хүн ороод ирэхэд яах вэ? тэгвэл бид дахиад шинэ дэд дараалал үүсгэнэ. Ингэхдээ, өмнөх дэд дараалалд байгаа хүмүүсээс хамгийн хойно зогсох гэхдээ шинэ орж ирж байгаа хүнээс өндөр, тэр хүний хойно энэ шинэ хүн зогсож дахин дэд шинэ дараалал үүснэ. Тэгэхээр хэрэв дэд дараалалын хойно байгаа хүн шинэ хүнээс намхан бол хасаад явна, ингэх тоолонд бодлогын хариу бас 1-ээр нэмэгдэнэ. Яагаад гэвэл энэ шинэ хүнийг эдгээр хасагдаж байгаа хүмүүс бүгд харж чадах ёстой, яагаад гэхээд манай дэд дараалал угийн буурахаар эрэмбэлэгдсэн байгаа.

Дээрэх алгоритмыг стек ашиглаж дэд дараалалд хүн нэмэх болон хүн хасах үйлдлийг O(1)т хийж чадвал шугаман бодолт болно.

Одоо, дарааллаж зогсож буй хүмүүс ижил өндөртэй үед яах вэ? Ер нь ижил өндөртэй үед дээрх алгоритмаар бодвол яагаад болохгүй вэ? Үнэндээ дарааллаж зогсож буй хүмүүс ижил өндөртэй л биш бол бүх хүмүүсийн өндөр ялгаатай байх нь чухал биш, яагаад?

Бодолт

Part II-р дараагийн 2 бодлогын анализыг хийе

GTC Open September

 Тэмцээнд оролцсон бүх оролцогч нартаа баяр хүргье.

Тусгайлан, эхний гурван байр болох Төрхүү, Бат-Эрдэнэ, Баттулга баяр хүргье. Энэ удаагийн тэмцээнд нийт 68 оролцогч бүртгүүлж 24 оролцогч бодолт илгээж оролцожээ.

Түрүүлсэн оролцогч Төрхүүгийн хувьд Дархан хот, Оюуны Ирээдүй Цогцолбор сургууль 12-р анги

2т орсон Бат-Эрдэнэ МУИС 1-р курсын оюутан,

3т орсон Баттулгын хувьд програмист залуу байх нь ээ.

Эхний тэмцээнээ ямарч байсан оролцогч нарыхаа түвшинг харах үүднээс хүнд бодлого тавилгүй явууллаа. Хурдаараа л үзэлцлээ гэсэн үг. Бодлогуудын өгүүлбэрт зарим нэг жижиг алдаа гаргасныг эс тооцвол амжилттай сайхан болж өнгөрлөө. Тэмцээнийг ивээн тэтгэсэн Гүүд Ти Си ХХК-н хамт олондоо баярлалаа.

Тэмцээн цаашдаа сар бүр болох болно. Бодлогуудыг би өөрөө бэлдэж оруулаад явна аа.

Жич: Бодлогын анализ, шагнал гардуулах уулзалт зохион байгуулах байсныгаа болиод онлайнаар бодлогын анализаа энд хийгээд байр эзэлсэн оролцогч нарын шагналыг дансаар шилжүүлэхээр боллоо. Учир нь, 1т оролцогч нараас уулзалтанд ирэх нь их хүндрэлтэй байх шиг байна, 2т ихэнх оролцогч нар 10-н жилийх байгаа тул зарим эцэг эх хүүхдээ орой, түгжрэлд явуулах боломжгүйгээ илэрхийлсэн. За тэгээд орчин үе, ихэнх зүйл зайнаас харьцдаг болж байгаагийх заавал цуглах гээд яахавдээ гэж үзлээ.

Бодлогын анализаа эхлэе

Хүрээ

Шууд симулац хийгээд зураад хүрээгээ үүсгээд явчих бодлого. Бодолт

Үлдэгдэл

42т хуваахад гарч болох хамгийн том үлдэгдэл нь 41, хамгийн бага нь 0. Тэгэхээр 42 урттай бүүл массив аваад орж ирсэн тоог хуваагаад үлдэгдэлийг нь массивын индэкс болгоод тэмдэглээд явчихаж болно. Бодолт

Тойрог

Евклидын гёометрт тойргийн талбай pi * r * r.

Евклидын бус гёометрын тойрогийг евклидын гёометрт дүрсэлбэл квадрат болж дүрслэгдэнэ. Яагаад? Тэгэхээр квадратын диагоналийн урт өгөгдсөн бол талбайг олох бодлого болох нь ээ. Бодолт

Вирус

Жингүй чиглэлгүй граф өгөгдөхөд аль нэг оройгоос түвшний нэвтрэлт хийхэд хүрч болох бүх орой хүртэлх хамгийн богино замууд олдоно. Вирус байгаа цэгүүдээс яг саяны хэлсэнчлэн түвшний нэвтрэлт хийж вирус хүрч болох өрөө бүрт хамгийн хурдандаа хэдэн минутанд очихыг нь олчихно.

Үүний дараа S оройгоос дахин нэг түвшний нэвтрэлт хийж D-д хэр хурдан очихыг нь олчихно. Ингэхдээ, түвшний нэвтрэлт хийх явцад, мэдээж дайран өнгөрөх өрөө бүрт вирусаас бага хугацаанд очих ёстой гэдэгээ шалгаад явчихна. Бодолт

180

Шууд хүчээр шалгахад хугацааны хязгаар хүрэхгүй байхаар бодож оруулсан бодлого. Даанч hackerrank-н сервер бодож байснаас хүчтэй байх шиг байна, O(N^4) бодолтууд давсан харагдана лээ.

Ер нь бол үндсэн бодолт O(N^4) зөв. Хугацаандаа багтааж зөв бодохын тулд хэд хэдэн сайжруулалт хийнэ.

Анзаарах ёстой зүйл, 180 эргүүлэхэд ижил байх матриц доторх бүх дэд матрицууд мөн 180 эргүүлэхэд ижил байх матрицууд байна. Гэхдээ эдгээр матрицууд бүгд 1 төвтэй байх ёстой шүү.

Эсрэгээрээ 180 эргүүлэхэд тэнцүү биш матриц байх юм бол энэ матрицыг агуулсан аль ч матриц 180 эргүүлэхэд тэнцүү байж чадахгүй.

Дээрх 2-г анзаараад кодоо цэвэрхэн бичвэл ер нь давчихна.

Дараагийн сайжруулалт бол аль нэг цэг, нүднээс 1, 1-ээр ихэсгэж квадрац матриц үүсгэж шалгах шалгалтыг сайжруулж болно. Санаа бол, аль нэг нүднээс матрицаа томруулахдаа 1, 1-ээр биш 64 бит тооны тоогоор масклаад шалгавал нүднүүдээ 1, 1-ээр биш 64 хэмжээтэй блокоор шалгах боломж гарна. Ийм төрлийн сайжруулалт бодлогуудад их тус болдог. Бодолтноос дэлгэрэнгүй хараарай.

За тэмцээнд оролцсон, санаа тависан мөн сонирхсон бүх хүмүүстээ баярлалаа.

Дараагийн тэмцээнийг facebook хуудсаараа зарлаад хийх болно оо. Бусдадаа түгээж, аль болох олуулаа оролцоод хөгжөөд явцгаая.