Rockethon 2014

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

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

A

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

B

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

C1

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

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!