Topcoder "diary" SRM 468 (division 2)

Өнгөрөгч SRM дээр 500-гаа алдаатай бичиж явуулаад 2 удаа амжилтгүй challenge хийж rating-ээ навс унагасан болохоор энэ удаад аль болох "хашир" тактик баримталж оров :P

Coding Phase

Easy 250:

type: ad hoc, sorting
Уншиж ойлгоход нэлээдгүй хугацаа зарцуулсаныг эс тооцвол хялбархан бодчихсон :)

Medium 500:

type: string parsing, sorting
Гар утасны "T9 dictionary"-н програмчлалыг бичих бодлого. Жаахан түвэгтэй л юм байна лээ. Кодоо бичихэд их хугацаа зарцуулсан. Азаар нэг их мунгинаж олон "debug" хийгээгүй. Бичиж дуусаад submit хийгээд цагаа харвал 17 минут үлдсэн байлаа. Арай л их хугацаа зарцуулчихаж дээ.

Hard 1000:

type: bfs л юм шиг санагдсан :D
Хугацаа бага үлдсэн ч гэсэн амжуулах гэж оролдсон. Цаг дуусахаас хэдхэн минут үлдсэн байхад яагаад ч амжихгүй гэдгээ ойлгоод больсон доо :)

Challenge Phase:

Хальт гүйлгээд л харсан. 250 дээр угаасаа алдсан хүн байхгүй л харагдана лээ. Бусад хүмүүсийн 500-гийн бодолтыг хальт харахад бол ойлгохгүй юм байна лээ. Сайн ойлгоогүй бодлогон дээр challenge хийж азаа үзэх хэрэггүй гэж энэ удаад шийдэв.
Манай өрөөнийхөн ч хашир байна даа. Өрөөнийхөн нийтдээ 3 удаа challenge хийж 3-уулаа амжилтгүй болох шив дээ. Challenge Phase-аа дуусгалгүй үүнийг бичиж эхлэв :P

System Testing Phase:

Хүлээгээд л байж байна :D Хэрвээ 2 бодлого маань 2-уулаа тэстээ давчихвал эхний 70-д орчих л юм шиг байна :)

Програмчлалын улсын 20-р олимпиад

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 минутанд бодсон бяцхан түүх байлаа. Одоо бүсийн тэмцээнд илүү амжилттай орохын төлөө.....

MNPC 2010-н бодлогууд - AAN

Artificial Neural network
Нейрон нь мэдрэлийн эсүүд болон тэдгээрийн хооронд мэдээлэл дамжуулах сувгуудаас тогтоно. Тэдгээр нь хэд хэдэн давхаргуудаас тогтох бөгөөд эхний ба сүүлийн давхарга нь нэг нэг эсээс тогтоно. Эхний ба сүүлийн давхаргуудын хооронд мэдээлэл дамжих боломжтой байдаг байна. Нэг эсээс нөгөө эс рүү сувгаар дамжих мэдээлэл нь хэмжээтэй. Тэгвэл эхний давхаргаас сүүлийн давхарга хүртэл мэдээлэл хүрч болдоггүй байхаар сувгуудыг хасахдаа хассан сувгуудын нийт мэдээллийн хэмжээ нь хамгийн бага байх програм зохио.
Оролт:
Оролт нь 5-аас илүүгүй тест агуулах ба тестийн бүтэц дараах хэлбэртэй байна. Эхний мөрөнд мэдрэлийн эсийн тоо N<=125 болон мэдээлэл дамжуулах сувгуудын нийт тоо M<=300 гэсэн тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Дараагийн М мөр тус бүрт A B W тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. Үүнд: А, B тоонууд нь мэдрэлийн эсийн дугаарууд W (0<=10000 натурал тоо) нь мэдээллийг дамжуулах хэмжээ болно. A-гаас B-д мэдээлэл дамждаг байхад B-гээс A-д мэдээлэл дамжихгүй. Мөн эхний давхарга болон сүүлийн давхарга дахь эсийн дугаар нь 0 ба N-1 байна. Тестийн төгсгөлд N=0 M=0 байна.
Гаралт:
Гаралтанд тест бүрд харгалзах хассан сувгуудын нийт мэдээллийн хэмжээний хамгийн бага утгууд нэг нэг мөрөнд байрлана. Гаралтын төгсгөлд нэг мөр авсан байна.
Жишээ:
Оролт:
7 8
0 1 2
0 2 1
1 3 3
2 3 5
2 4 4
3 6 2
4 5 2
5 6 3
4 4
0 1 3
0 2 4
1 3 5
2 3 2
0 0
Гаралт:
3
5

MNPC 2010-н бодлогууд - Улс

Улс
Улс нь N ширхэг хоттой. Хот бүрээс өөр хот руу очиж болдог замууд (Хэд хэдэн хотоор дамжин очиж болно) байжээ.
Хотуудыг 0 ээс N-1 хүртэл дугаарлажээ. Нэг хотоос нөгөө хотод очих зам олддог бол харилцаатай хотууд гэе. Хэрэв тухайн хотоос гарах бүх замуудыг таслахад ямар нэгэн харилцаатай байсан хоёр хотын харилцаа тасардаг бол энэ хотыг “сайн” хот гэе.
Та “сайн” хотуудыг олох програм бичнэ үү.

Оролт:
Оролт нь нийт 5-аас ихгүй тест агуулах ба тестийн бүтэц нь дараах хэлбэртэй.
Эхний мөрөнд N<175000, M<265000 натурал тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана.
Дараагийн М мөрөнд A,B тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана.
A, B-хотын дугаар бөгөөд A,B хотууд хоорондоо замуудтай болохыг илэрхийлнэ.
Тестийн төгсгөлд N=0 M=0 байна.
Гаралт:
Тестийн тоонд харгалзах тохиолдлууд дараах байдлаар байна.
Тохиолдол бүрт харгалзах тоонуудыг өсөх эрэмбээр нэг нэг мөрөнд гаргана. Гаралтын төгсгөлд нэг мөр авсан байна.
Жишээ:
Оролт:
7 6
0 3
1 2
2 4
3 4
4 6
5 6
5 5
0 1
1 2
1 4
2 3
2 4
0 0
Гаралт:
2
3
4
6
1
2

MNPC 2010-н бодлогууд - Болхи схем

Болхи схем
Болхи схем өгөгджээ. Түүний бүтэц нь зангилаанууд болон тэдгээрийг холбосон холбогчуудаас тогтоно. Хоорондоо параллель N ширхэг утас мөн тэдгээрт перпендукляр M ширхэг утастай.(Зургийг хар)

Зураг

Мэдрэгч нь холбогч дээр байрлах ба холбогч бүр нь мэдрэгч тавихад тодорхой үнэтэй.
Мэдрэгч бүр нь холбогчоор гүйж байгаа электроны дугаар, хугацаа болон хөдөлгөөний чиглэлийг мэдээлнэ.

Мэдрэгчүүдийн мэдээллээр битүү маршрутаар (маршрут нь нэг явсан газраараа дахин явахгүй байна) явж байгаа ямар ч электроны явсан замыг нэг утгатай тодорхойлж чаддаг байхаар хамгийн бага үнэтэйгээр мэдрэгчүүдийг тавих програм бич.

Оролт:
Оролтын эхний мөрөнд T<=5 өгөгдөх ба тест бүр нь дараах бүтэцтэй. Оролтын эхний мөрд N, M (1<=200)гэсэн натурал тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. N нь схемийн хэвтээ утасны тоо, M нь босоо утасны тоо. Дараагийн (M-1)*N мөрөнд хэвтээ холбогчуудын мэдрэгч тавих үнүүд өгөгдөнө. Эдгээрийг нь утаснуудыг дээрээс нь доошоо, холбогчуудыг нь зүүнээс баруун тийшээ байдлаар өгнө. Түүний дараагийн (N-1)*M мөрөнд босоо холбогчуудын мэдрэгч тавих үнүүд өгөгдөнө. Тэдгээрийн хувьд утаснуудыг зүүнээс баруун тийшээ, холбогчуудыг нь дээрээс доошоо байхаар өгнө. Гаралт:

Тестийн тоонд харгалзах тоонууд нэг нэг мөрөнд байрлана.
Эдгээр тоонууд нь битүү марштрутаар явах электроныг нэгэн утгатай илэрхийлж чадах нийт үнэ нь хамгийн бага байхаар байрлуулах мэдрэгчүүдийн үнүүдийг нийлбэр байна. Гаралтын төгсгөлд нэг шинэ мөр байна.
Жишээ:
Оролт:
2
3 3
2
4
7
5
2
5
7
7
3
1
2
2
2 2
3
3
2
1Гаралт:
7
1

Монголын үндэсний програмчлалын олимпиад II

Монголын үндэсний програмчлалын II олимпиад 2010 оны 04 сарын 3-нд амжилттай явагдаж өнгөрлөө. Тэмцээний товч дүнг танилцуулъя.

1. МУИС - МКС 1-р баг - 5 оноо
Бүрэлдэхүүн : Хонгор, Мөнх-Очир, Алмабек
2. МУИС - МТС 2-р баг - 3 оноо
Бүрэлдэхүүн : Өсөхбаатар, Жамсрандорж, Мөнхжаргал
3. МУИС - МКС 2-р баг - 1 оноо
Бүрэлдэхүүн : Нямдаваа, Авирмэд, Ганбат
4. МУИС - МТС 1-р баг - 1 оноо
Бүрэлдэхүүн : Мөнгөншагай, Сүрэн, Хуягбаатар

Багийн гишүүдийг буруу бичсэн бол хэлж засуулна уу?