TCO 11 Elimination Round 1

Удаан хугацаанд тэмдэглэл хөтөлсөнгүй, энэ удаад өчигдөр болж өнгөрсөн TCO 11 Elimination Round 1-т хэрхэн орсон тухайгаа бичихээр шийдлээ.

Division 1: Khongor, naranbayar_mon, gmunkhbaatarmn, lmo0731, {Hypuk}

Энэ удаагийн тэмцээнд өмнөх 3 Qualification үеүүдээс шалгарсан тус бүр 600 оролцогч дээр нь өндөр рейтингтэй 200 хүнийг нэмээд 2000 хүн оролцох ёстой байв. Гэхдээ тэмцээн эхлэхэд 1550 хүн бүртгүүлсэн байлаа. Дараагийн тэмцээнд 850 хүн шалгарна.

Ингээд тэмцээнээ эхэлье :). Elimination Round 1 бол миний бодлоор энгийн Division 1-с арай хялбар байдаг. Өмнөх жилээс анзаарахад нэлээд хурдан easy-р 850-д багтдаг, гэвч энэ удаа өөр байж магадгүй гэж бодлоо.
Эхлээд бодлогын оноонуудыг хартал 250, 500, 1000 буюу хэвийн оноонууд. Тийм учраас 250, 500 хоёрыг бодох ёстой.

250:
Танд A,B,C гэсэн 3 queue бүтэцтэй дараалал байгаа. Та A->B, B->A, A->C, C->A хооронд урдаас нь авч нөгөөгийн ард хийж болно. A-д зөвхөн xo-с бүрдсэн тэмдэгт мөр өгөгдсөн бол A-д өөр нэгэн xo-с бүтсэн тэмдэгт мөр үүсгэхийн тулд дээрх 4 үйлдлээс хамгийн цөөндөө хэдийг ашиглах вэ. B,C гэдэг 2 дараалал байгаа нь x,o гэсэн үсгүүдийг тус тусд нь хадгалах боломж олгож байгаа юм. Ингээд A-д байгаа тэмдэгт мөр нь goal-н prefix-тэй таарах хүртэл A->B эсвэл A->C үйлдлийг хийнэ (x эсвэл o гэдгээс хамаарч). Ингээд нэгэнт prefix болсон бол хэрэгтэй x эсвэл o-оо B,C-с буцаан A-д хийнэ. Хүмүүс substring гэх мэт функц ашиглаж нэлээд жижигхэн бодолт хийжээ. Миний хувьд шууд л санаан дээрээ тулгуурлаад жаахан томдуу код биччихсэн. Тестлээд submit = 234 оноо.

500:
Өгүүлбэрээ дажгүй хурдан ойлгочихлоо. N ширхэг дараалсан зам байв. Маргааш тэдгээр нь шавартай байх эсэх тус бүрийн магадлал өгөгдсөн. Эхний болон сүүлийн зам шаваргүй. Та эхний замаас сүүлийн зам руу хүрэх ёстой ба баруун тийш 1 эсвэл 2 зам явж болно. Та эхний хотоос сүүлийн хот руу 1 эсвэл 2 замаар явж хамгийн цөөн шавартай замыг дайрна. Та туулах ёстой шавартай замынхаа дундаж утгыг ол.
Expected буюу дундаж утга нь мэдээж ямар нэгэн тодорхойгүй буюу магадлалтай параметрүүдээс хамаарах ба уг бодлогын хувьд тэр нь зам бүрийн шавартай байх эсэх магадлал. Бүх замын хувьд шавартай эсвэл шаваргүй гэж үзээд 2^n боломж шавхая (хугацаанд амжихгүй ч гэсэн дараагийн бодолтонд хэрэг болно).
Тэгвэл ..XXX.XXX..XX. зам байг X нь шавартай замыг илэрхийлнэ. Энэ үед та хамгийн багадаа [3/2]+[3/2]+[2/2]=1+1+1=3 шавартай зам туулаад зорилгодоо хүрч чадна. Эндээс дараалсан X бүрийн тоог 2т бүхлээр хувааж нэмэхэд туулах ёстой хамгийн цөөн шавартай замын тоо гарна гэсэн үг.
Хэрвээ f(i)-р хамгийн цөөндөө i ширхэг шавартай зам туулдаг замуудын боломжит тоо буюу магадлалыг тэмдэглэе. Жишээ нь 8 замаас 3 замыг бид сонирхож байгаа бол магадал нь 0.375 гэсэн үг. Тэгвэл Summa(f(i))=1.0 {i=0..n} байх нь илт. Мөн эцсийн хариу нь Summa(f(i)*i) {i=0..n}.
Би f(i)-г dp(i,j,k) ашиглан олсон. dp(i,j,k) нь эхний 1..i замын хувьд нийт хамгийн цөөндөө j ширхэг шавартай зам туулдаг ба сүүлийн дараалсан k ширхэг нь шавартай байх замын магадлалыг тэмдэглээд i+1 замын шавартай эсэхийг сонгосноор хялбархан бодсон. Тестлээд submit = 373 оноо.

Нийт 25 минут орчим хугацаа өнгөрчээ. Байраа хартал дажгүй шүү, 180 хавьцаа. Ингээд ерөнхийд нь хартал 230 орчим оноотой байхад дараагийн шатанд тэнцэхээр байлаа. Тиймээс 2 бодлогын аль нэг нь давахад тэнцнэ гэсэн үг. Тэгэхээр ерөнхийдөө итгэлтэй.

Үлдсэн хугацаанд hard-г барсангүй. Challenge Phase-г идэвхгүй байдлаар өнгөрөөж System Test дуусахад 2 бодлого давж 216-р байранд орж дараагийн шатанд тэнцлээ.

Ойрд Rating буураад байгаа шалтгаан нь хайнга easy+дэндүү жижигхэн алдаатай medium юм. Тэгэхээр одооноос жаахан хянуур үзэж хуучин rating-ээ буцааж авна даа :). 1258+174=1432