SMCS баг

Олимпиадад нийт 7 бодлого ирсэн ба одоогоор файлаар олдсон 3 бодлогыг блогт нэмлээ. Мөн хүмүүст жаахан ч гэсэн сонирхолтой байж магад гэсэн үүднээс өөрийн багийн (Хонгор,Мөнх-Очир,Алмабек) оролцсон тэмдэглэлийг бичье.

Сүүлийн үед өөрийн гэсэн template их хэрэглэдэг болсон учир компъютер дээрээ суугаад шууд template-ээ бичив.
Бодлого ирлээ. Эхлээд нэг нэг бодлогоо уншлаа, миний уншсан бодлого нь Word гэсэн нэртэй бодлого байлаа. Шууд л DP + Matrix байсан учир (гэхдээ DP-ээ хараахан гаргаагүй) Matrix struct - аа бичиж эхлэв, тэгээд байж байтал Алмабек энд граф-н хамгийн их урсгалыг олох бодлого байна гэв. Хартал илүү дутуу юмгүй шууд Maximum Flow байв. Maximum Flow - г хангалттай их бичсэн учир бараг энэ нь гайгүй гэж бодоод дахиад л Maximum Flow бичиж эхлэвээ. Гэтэл Мөнх-Очир нэг бодлого үзүүлээд (a^b)%c олох бодлого байна гэв. Энэ бол хангалттай олон бичиж байсан бодлого учир шууд бичив, гэтэл жаахан bug гарсны гайгаар 22 дах минутанд анхны Yes -г авав.

Үүний дараа бодож санах юмгүй өмнөх Matrix-тай бодлогоо бичлээ, эхний хэдэн минутанд Matrix struct бичээд бараг л дууссан байсан учраас хийх зүйл нь DP байгуулах л байв. Бодлого энгийн байсан учраас үүнийг гялс хийгээд жишээ оролтууд ажиллаж байсан учир 29 дах минутанд submit хийв. Гэтэл No -Wrong Answer :(. Үнэхээр гайхав ..... Гэтэл үнэхээр жижигхэн алдаа байсан ба засаад 31 дах минутанд submit хийлээ. 2 дах Yes.

Одоо өмнө "сэглэсэн" Maximum Flow бодлогоо бичээд submit хийв. 46 дах минутанд Yes авлаа.

Ингээл тэмцээний дүнг хартал Манай баг 3 бодлоготой, бусад баг хараахан бодлого бодоогүй байв. Ингээд жаахан амьсгаа авлаа. Мөнх-Очир нэг бодлого уншиж байх хооронд Алмабек надад нэг бодлого үзүүлэв, тэр бодлого граф-н бүх Articulation Point-г олох бодлого байсан ба азаар би чадахгүй гэдгээ мэдэж байсан учир энэ бодлогыг бүр мөсөн хаяв. Мөнх-Очир оролдож байсан бодлогоо бодох аргыг олоод тэгээд Мөнх-Очир -н заавраар би бичив. 2 хүн бичсэн учир үнэхээр алдаагүй сайхан бичсэн. Тэгээд ганц нэг алдаа засаад жишээ оролт давангууд submit хийв. 72 дах минутанд Yes.

Ингээд 3 бодлого үлдсэн ба 1-г нь бүр мөсөн хаясан учир 2 бодлого үлдэв. Ball & Болхи схем. Ball гэдэг бодлого угийн амар бодогдчих эд биш байсан учир би оролдохоос татгалзаад Мөнх-Очирт өгөв. Мөнх-Очир уншиж байсан бодлогоо надад тайлбарлаж өгөв. Гэхдээ бид 2 Болхи-Схем бодлогыг нэг л ойлгож өгөхгүй байсан. Тэгээд зохиогчийг нь дуудаж тайлбар аваад арай дээрдсэн ч бүтэн ойлгосонгүй. Өрөө олон хүнтэй халууцаад байсан болохоор 00 оронгоо сэрүүцээд авав. Тэгээд орж ирээд бүтэн ойлголоо. Одоо яаж бодох вэ? :D. Ингээд энэ хэсэг дээр ~30 орчим минут болсон байх. Тэгээд бодож байтал бодлогын нөхцөл ёсоор мэдрэгч тавьсан ирмэгүүдийг таславал юу болох вэ? Мэдээж Граф-д цикл үлдэхгүй. Циклгүй чигэлгүй граф = Мод. Уг таслаж байгаа ирмэгүүдийн нийлбэр хамгийн бага учир зүгээр ч Мод биш "Хамгийн их үнэлгээт" мод юм. Мэдээж Kruskal -н алгоритмаар бодож болох байлаа. Гэхдээ хязгаарлалтыг харахад тийм ч амар биш 40000 орой + 160000 ирмэг. Иймээс Disjoint-Set өгөгдлийн бүтцийн тусламжтайгаар O(Ирмэг * log Орой) д бодож болно. Ингээд амжих нь тодорхой учир бичиж эхлэв, бодлогын оролтыг граф болгоход бас л төвөгтэй байсан учир их ч алдаж их ч удлаа. Ингээд жишээ оролт давсны дараа submit хийв. 159 дах минутанд Yes.

Одоо нэг л бодлого үлдсэн ба тэрийг үнэхээр барсангүй. Сүүлийн 2 цаг олон юм хийсэн дээ. Minesweeper+Утасны тоглоом+...... кк.

Submit 1 - Pandora - 22 - Yes
Submit 2 - Word - 29 - No Wrong Answer
Submit 3 - Word - 31 - Yes
Submit 4 - AAN - 46 - Yes
Submit 5 - Meet - 72 - Yes
Submit 6 - Bolhi - 159 - Yes

Энэ манай багийн 5 бодлогыг 159 минутанд бодсон бяцхан түүх байлаа. Одоо бүсийн тэмцээнд илүү амжилттай орохын төлөө.....