Skip to main content

Rockethon 2014

Өнгөрсөн бүтэн сайнд болж өнгөрсөн Rockethon 2014 тэмцээнд оролцсон тэмдэглэлээ та бүхэнд хүргэж байна.

Тэмцээн 3 цагийн хугацаатай бөгөөд нийт 12 бодлоготой байсан юм.

A

Хамгийн хялбархан бодлого нь байсан. Ижил үсгээр бүтсэн хэсгүүдээс сондгой урттай хэсгүүдийг тоолоход хангалттай.

B

Өгүүлбэр нь бодлогыг нэлээд төвөгтэй болгож байсан. Анзаарах гол зүйл нь тэмдэгт мөрийг нугалсны дараа 2 үсэг ижил багананд дарааллаж орших зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь уг 2 үсгүүдийн хоорондох зай нь сондгой тоо байх юм. Бид ямар нэг үсгийг хамгийн эхний мөрөнд оршихоор сонгож аваад уг үсэгтэй хамгийн ойрхон орших сондгой зайтай ижил үсгүүдийг сонгоод явна. Нийт N ширхэг үсгийг эхлэл болгон сонгох ба тэр бүртээ O(N) үйлдэл хийх учир энэ бодолт O(N2).

C1

Ямар ч өрсөлдөгчийг ялж эсвэл ялагдаж болно. Тиймээс нийт 2N тохиолдол байж болно. Уг тохиолдол бүртээ өөрийн rank болон шаардагдах effort-г O(N)-д олж болох учраас нийт бодолт маань O(N*2N).

C2

C3

C3-г хэрхэн бодсоноо тайлбарлая.

Өөрийнхөө хэдэн оноог авахаа мэдэж байгаа ба X гэж үзье. Эндээс бид X өрсөлдөгчөө дийлэх ба N-X ширхэг өрсөлдөгчиддөө ялагдах нь хялбархан харагдана. Одоохондоо бид аль N-X ширхэг өрсөлдөгчдийн оноо нэмэгдэхийг мэдэхгүй.

Өөрийгөө X оноотой, бусад хүмүүсийн оноо хэвээрээ гэж үзээд өөрийнхөө байрыг R гэе. Хэрвээ R>K байвал бид яаж ч оновчтой тоглосон X оноогоор эхний K байранд орж чадахгүй нь илэрхий. R<=K гэж үзээд үргэлжлүүлье. Бидэнд K-R ширхэг байр ухрах боломж бий. Оноо нь нэгээр нэмэгдсэнээр бидний урд гарах боломжтой хүмүүс бол X болон X-1 оноотой хүмүүс юм. Эдгээр хүмүүсийн тоог M гэж тэмдэглэе. Бид уг M хүмүүсээс чадахаараа олонг ялаад байхад бидний байр доошлоод K-с хойш орох боломж бий ба энэ нөхцөл нь R + M - X > K байх явдал ба энэ тохиолдолд мөн л боломжгүй. Эндээс цааш ямар нэгэн байдлаар эхний K байранд орох боломжтой ба энэ үед effort-г минимумчлах ёстой. М > K - R үед бид уг М хүнээс ямар нэгэн M - (K - R) хүнийг зайлшгүй ялах ёстой, effort-г минимумчилж байгаа учир хамгийн бага хүч шаардах M - (K - R) ширхэг хүнийг ялах нь ашигтай. Үүнтэй мөн адилаар үлдсэн бүх хүмүүсээс хамгийн бага хүч шаардах хүмүүсийг ялахад шаардагдах effort-г олоход бидний хариу олдоно.

Бид үндсэн бодлогыг ямар нэгэн X онооны хувьд бодсон. Тэмцээний үед X дээр хоёртын хайлт хийж болно гэж бодож байсан ч 2 удаа wrong answer авсны дараа буруу гэдгийг ойлгосон. Гэхдээ бага зэрэг заль хэрэглээд Accepted. Одоо харахад ternary search хангалттай гэж харагдаж байгаа ч яг батлаж чадахгүй байна. Anyone?

Сайжруулалт: Үнэн хэрэгтээ X дээр хоёртын хайлт хийхгүйгээр нэг нэгээр нэмэгдүүлээд өмнөх олсон дэд бодлогын утгаар дараагийн дэд бодлого маанд хариутай байх эсэхийг O(1)-д шийдээд байх боломжтой ба хариутай байх хамгийн бага X-н хувьд O(NlogN)-д (count sort ашиглавал O(N))a хариуг олж болно. O(NlogN) (O(N)).

D1

Шууд brute force-р бодох боломжтой. Бүх N^2 хосын хувьд огтлолцож байгаа эсэхийг шалгаад хамгийн богино талын уртыг O(1)-д олж болно.

D2

Coming soon!

Comments

Post a Comment

Popular posts from this blog

SRM 477

Монгол улсаас энэ удаа хамгийн олон хүн буюу 11 хүн орлоо. Шинэ гишүүд тавтай морил. Division 1: Khongor Division 2: XaCaHaa , lmo0731 , naranbayar_mon , Khuyagbaatar , ChNbLd , gmunkhbaatarmn , gantushig , nursoltan_h , almabek , janchiv

Баяртай мэдээ

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

Сонирхолтой бодлого

Манай компани HackerRank сүүлийн үед тэмцээн ихээр явуулж ирсэн. Үүнийг дагаад бодлого зохиох гэдэг хүнд асуудал байдаг. Дотроосоо болон гаднаас бодлого их авдаг, мэдээж тодорхой хэмжээний тест хийдэг ч гэсэн бодлого алдаатай байх тохиолдол нэлээдгүй гардаг.