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

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

Quantium Hack It тэмцээн дээр нэг бодлого их асуудал дагуулсаар байсан. Байнга л форум дээр пост хийсэн байна гээд л и-мейл ирнэ. Ойрд завгүй байсан болохоор ерөөсөө анхаарч хараагүй юм. Нэг өдөр үдээс хойш хорхой хөдлөөд харсан чинь нэлээд хүнд бодлого санагдлаа, хүмүүсийн санал гомдлыг ч уншсан.

Өгүүлбэр:

Нэгэн улс N тооны хоттой ба хот бүр зам бүтээн байгуулдаг болон засварыг хариуцдаг 2 хэсэгтэй. A-B хотуудын хоорондох замыг A эсвэл B хотын бүтээн байгуулалтын хэсэг нь барих ёстой (Зам нь 2 чиглэлдээ баригдана). Шинээр баригдсан зам бүрийг аль нэг хотын (өөрийнх нь ч байж болно) засвар хариуцсан хэсэг нь хариуцна. Аль ч хотын бүтээн байгуулалтын хэсэг хамгийн ихдээ нэг зам барьж чадах ба засварын яам ч гэсэн хамгийн ихдээ нэг зам хариуцах ёстой. Зам барих болон хариуцах өртөг нь харилцан адилгүй. Та хамгийн бага өртгөөр аль ч хотоос аль ч хот руу явах боломжтойгоор замыг барих ёстой. Баригдсан зам бүрийг аль нэг хотын засварын хэсэгт мөн хүлээлгэж өгнө. Хамгийн бага зардлыг ол.

N*N хэмжээтэй A,B хоёр матрицаар өртгийг илэрхийлнэ. A[i,j] нь i-р хотын бүтээн байгуулалтын хэсэг нь i-j хотуудын хоорондох замыг барих өртөг. B[i,j] нь i-р хотын засварын хэсэг нь j-р хотын барьсан замыг хариуцан ажиллах өртөг. N <= 30

Зохиогчийн буюу буруу бодолт:

N хотыг холбоход бидэнд яг N-1 ширхэг зам хэрэгтэй. Өөрөөр хэлбэл бид N оройтой бүтэн графаас мод үүсгэх юм. N-1 тооны хот тус бүр өөр нэгэн хот руу зам барих ба үлдсэн нэг хот нь барихгүй. Бид замаа барьчихсан гэж үзвэл засварын өртөг нь замын бүтцээс бус зөвхөн аль аль хот зам барьсан бэ гэдгээс хамаарна.

int res = infinity; for (int skip = 0; skip <= n; skip++) { res = min(res, construct(skip) + manage(skip)); }

construct(i) нь i-р хотоос бусад хот нь зам бариад хотыг холбох хамгийн бага өртөг ба manage(i) нь i-р хотоос бусад хот зам барьсан үед бүх замыг хариуцах хамгийн бага өртөг гэж үзвэл бодлого маань дээрх алгоритмаар бодогдоно.

Зам хариуцах

Үүнийг бид хамгийн бага өртөгтэй хамгийн их урсгалын алгоритмаар бодож болно. Minimum cost flow (MinCost MaxFlow). Уншигч танд үлдээе гээд залхуурчихъя :).

Зам барих

Энэ хэсэг дээр л зохиогч болон тестлэгч нар алдсан юм.
Оролдлого 1:
Бидэнд аль аль хот зам барих нь мэдэгдэж байгаа. Тэгвэл хот бүрээс хамгийн бага өртөг гарах хот руу нь зам барьчихъя, өртгийн хувьд бол бага л сонсогдож байна тийм үү?

Сайхан оролдлого байлаа.

Оролдлого 2:
Дээрхийг сайжруулаад N-1 ширхэг хот бүр 1 хот руу зам барих ба бүх хот ямар нэгэн замд холбогдсон байхаар замыг байгуулъя.

Зөв юм шиг харагдаж байна. Энэ үед бид мөн Minimum cost flow ашиглаад хариуг олж чадна. Not so fast!

Дээрх жишээнд A,B,D хот бүр нэг зам барьсан, бүгд ямар нэг замд холбогдсон ч хотыг тэр чигт нь холбож чадсангүй.

Оролдлого 3:
Бодлого маань уг нь Minimum Spanning Tree л олох гээд байгаа юм, гэвч A-B хоорондох замыг 2 янзаар барьж болно, A->B эсвэл B->A, өртөг нь ялгаатай. Чиглэлтэй Minimum Spanning Tree нь ер нь тийм ч нийтлэг бодлого биш, хүнд бодлогод ордог. Үүнийг Directed MST буюу Minimum cost arborescence алгоритмаар боддог.

Энэ бүхний эцэст ямар ч байсан бодлогын тестийг засч хэрэглэгчдээс баахан зэмлэл хүртсэн дээ. Буруу тестэнд нь тааруулаад бодчихсон хүмүүс кк.