Хоёр дахь тэмцээн маань амжилтттай болж өнгөрлөө. Тэмцээнд нийт 29 хүн бүртгүүлж 13 оролцогч оролцлоо. Цаг заваа зохицуулан хэрэг гаргаж оролцсон оролцогч нартаа их баярлалаа.
Ингээд эхний 3-н байр:
1-р байранд _mrsn_ 340 оноотой
2-р байранд MazaalaiMNGL 330 оноотой
3-р байранд Turkhuu 330 оноотой
тэмцээнийг тэргүүллээ. Дээрх оролцогч нар тэмцээний facebook хуудсаар холбогдож шагналаа авна уу.
Бодлогын анализдаа ороё.
Энэ удаагийн тэмцээний хамгийн амархан бодлого. Шууд симулац хийгээд хэвлэчихэж болно эсвэл жижигхэн мат ашиглаад шинээр үүсэх текстийн (i, j) дэх тэмдэгт нь хуучин текстийн (i/zr, j/zc)дэх тэмдэгт гэдэгийг харчихвал арай бага код бичиж болох юм.
Зөв хаалт зохион байгуулах бодлого. Иймэрхүү бодлого ихэвчлэн рекурс буюу стэк өгөгдөлийн бүтэцээр шийдэгддэг.
Шууд хүчээр шалгаад бодвол квадрат бодолт үүсэж хугацааны хязгаарлалт хэтэрсэн алдаа авна.
Эхлээд бодлогоо дараалалд байгаа бүх хүн ялгаатай өндөртэй үед бодоё.
Бодлогын өгүүлбэрээс ажиглавал А гэсэн хүн өөрөөс нь хойно зогсож байгаа хүмүүсээс хамгийн эхний өөрөөс нь эрс өндөр Б гэсэн хүнээс хойно зогсож байгаа хүмүүсийг харахгүй нь тодорхой буюу А-н хувьд Б-ээс хойно зогсох хүмүүс хамаагүй болж байгаа юм: Тэгэхээр яг ийм А Б гэсэн интервалыг дэд дараалал гэж үзье.
Хүмүүсийг зогсож буй дарааллаар нь 1, 1-ээр нь шалгаад явая. Дэд дараалалд шинээр орж ирэх хүн дандаа хамгийн хойно зогсож байгаа хүнээс намхан эсвэл ижил өндөртэй хүн байх нь ойлгомжтой. Мөн дэд дараалалд хүн шаардлага хангаад нэмж орж ирэх болгонд бодлогын хариу 1-ээр нэмэгдэнэ. Яагаад гэвэл хөрш хүмүүс бүгд бие биенээ харах учир.
Одоо дэд дараалалд маань хамгийн хойно зогсож байгаа хүнээс өндөр хүн ороод ирэхэд яах вэ? тэгвэл бид дахиад шинэ дэд дараалал үүсгэнэ. Ингэхдээ, өмнөх дэд дараалалд байгаа хүмүүсээс хамгийн хойно зогсох гэхдээ шинэ орж ирж байгаа хүнээс өндөр, тэр хүний хойно энэ шинэ хүн зогсож дахин дэд шинэ дараалал үүснэ. Тэгэхээр хэрэв дэд дараалалын хойно байгаа хүн шинэ хүнээс намхан бол хасаад явна, ингэх тоолонд бодлогын хариу бас 1-ээр нэмэгдэнэ. Яагаад гэвэл энэ шинэ хүнийг эдгээр хасагдаж байгаа хүмүүс бүгд харж чадах ёстой, яагаад гэхээд манай дэд дараалал угийн буурахаар эрэмбэлэгдсэн байгаа.
Дээрэх алгоритмыг стек ашиглаж дэд дараалалд хүн нэмэх болон хүн хасах үйлдлийг O(1)т хийж чадвал шугаман бодолт болно.
Одоо, дарааллаж зогсож буй хүмүүс ижил өндөртэй үед яах вэ? Ер нь ижил өндөртэй үед дээрх алгоритмаар бодвол яагаад болохгүй вэ? Үнэндээ дарааллаж зогсож буй хүмүүс ижил өндөртэй л биш бол бүх хүмүүсийн өндөр ялгаатай байх нь чухал биш, яагаад?
Part II-р дараагийн 2 бодлогын анализыг хийе
No comments:
Post a Comment