Монгол улсаас энэ удаа хамгийн олон хүн буюу 11 хүн орлоо. Шинэ гишүүд тавтай морил.
Division 1: Khongor
Division 2: XaCaHaa, lmo0731, naranbayar_mon, Khuyagbaatar, ChNbLd, gmunkhbaatarmn, gantushig, nursoltan_h, almabek, janchiv
Coding Phase :
Div 1-Easy/Div 2-Medium :
Өгүүлбэр: Зөгийний үүр хэлбэртэй газар өгөгдөв. Нүд бүр нь далай эсвэл хуурай газар. Далай болон хуурай газрын дунд орших beach гэж үзвэл өгөгдсөн газарт хэдэн beach байгаа ол.
Бодолт: Нүд бүрийн хувьд 6 талыг тоолчиход болно, 6 биш 3 тал тоолсон ч болно. Арай удчихлаа уг нь 5 минутанд бодчихсон бол...(6 минут 36 секунд)
Div 1-Medium :
Өгүүлбэр : a^2+b^2=c^2 нөхцлийг хангах 3 натурал тоог Pythagorean Triple гэдэг. Тэгвэл дээрх нөхцлийг хангах ба мөн gcd(a,b)=1 байх гурвалыг Pythagorean Primitive Triple гэе. Өгөгдсөн N<=200 тоон дотроос (тоонууд 1..999999 хооронд) хамгийн олон хоорондоо үл огтлолцох (disjoint) ба PPT үүсгэх (a,b) хосын тоог ол. a,b хосын хувьд c тоо нь өгөгдсөн тоонууд дотор байх албагүй.
Бодолт : Шууд greedy маягаар сонгоод явбал буруу байх нь ойлгомжтой. Эсрэг жишээ гэвэл 35 12 5 612. Учир нь 35 ба 12 хос болгочихвол 5 ба 612 хос үүсгэхгүй бөгөөд хариу 1 болно. Харин 35 ба 612 хос аваад 12 ба 5 авбал хариу 2 гарна.
Өгөгдсөн тоонуудыг орой гэж үзээд PPT үүсгэх 2 тооны хооронд ирмэг татаад граф байгуулъя. Тэгвэл бодлого маань maximum bipartite matching олох бодлого юм. Гэвч ерөнхий граф дээр matching олох гэдэг маань хэцүү байдаг. Графыг bipartite граф руу хувиргах хэрэгтэй. Анзаарсан зүйл маань a,b 2 тоо нэг нь сондгой, нөгөө нь тэгш байсан юм. Үүнийг a=m*m-n*n, b=2*m*n гэдгээс батлаж болно. Ингээд тэгш ба сондгой тоогоор 2 талаа хийсан bipartite граф дээр matching олоход хангалттай. Ингээд submit хийтэл нэлээд дээгүүр (эхний 100 хавьцаа) орж байлаа. Гэтэл хэсэг тестэлсний дараа алдаа олов. Resubmit :(. Нэлээд хойшиллоо (~150).
2 бодлогоо submit хийсний дараа Medium дээр олон хүн greedy бодолт хийсэн байх гэж бодоод эсрэг тест байгуулав (35 12 5 612 :D). Coding Phase дууссаны дараа Medium дээр маш жижигхэн алдаа гаргаснаа ухаарав, ингээд Challenge Phase-д зайлшгүй амжилттай орох шаардлага тулгарав.
Challenge Phase : Нэг хүний бодолт нээтэл яг миний унагахыг хүсч байсан greedy байв. Ингээд (35 12 5 612) тестээ өгөөд унагав. Дахиад бодолт нээтэл бас л ойролцоо байхаар нь нөгөө тестээрээ гялс унагаад 100 оноо авлаа.
System testing Phase : Бодож байснаар Medium уналаа. Гэвч 198-д ороод rating үл ялиг өслөө, мөн л Maximum Rating :).
Division 1: Khongor
Division 2: XaCaHaa, lmo0731, naranbayar_mon, Khuyagbaatar, ChNbLd, gmunkhbaatarmn, gantushig, nursoltan_h, almabek, janchiv
Coding Phase :
Div 1-Easy/Div 2-Medium :
Өгүүлбэр: Зөгийний үүр хэлбэртэй газар өгөгдөв. Нүд бүр нь далай эсвэл хуурай газар. Далай болон хуурай газрын дунд орших beach гэж үзвэл өгөгдсөн газарт хэдэн beach байгаа ол.
Бодолт: Нүд бүрийн хувьд 6 талыг тоолчиход болно, 6 биш 3 тал тоолсон ч болно. Арай удчихлаа уг нь 5 минутанд бодчихсон бол...(6 минут 36 секунд)
Div 1-Medium :
Өгүүлбэр : a^2+b^2=c^2 нөхцлийг хангах 3 натурал тоог Pythagorean Triple гэдэг. Тэгвэл дээрх нөхцлийг хангах ба мөн gcd(a,b)=1 байх гурвалыг Pythagorean Primitive Triple гэе. Өгөгдсөн N<=200 тоон дотроос (тоонууд 1..999999 хооронд) хамгийн олон хоорондоо үл огтлолцох (disjoint) ба PPT үүсгэх (a,b) хосын тоог ол. a,b хосын хувьд c тоо нь өгөгдсөн тоонууд дотор байх албагүй.
Бодолт : Шууд greedy маягаар сонгоод явбал буруу байх нь ойлгомжтой. Эсрэг жишээ гэвэл 35 12 5 612. Учир нь 35 ба 12 хос болгочихвол 5 ба 612 хос үүсгэхгүй бөгөөд хариу 1 болно. Харин 35 ба 612 хос аваад 12 ба 5 авбал хариу 2 гарна.
Өгөгдсөн тоонуудыг орой гэж үзээд PPT үүсгэх 2 тооны хооронд ирмэг татаад граф байгуулъя. Тэгвэл бодлого маань maximum bipartite matching олох бодлого юм. Гэвч ерөнхий граф дээр matching олох гэдэг маань хэцүү байдаг. Графыг bipartite граф руу хувиргах хэрэгтэй. Анзаарсан зүйл маань a,b 2 тоо нэг нь сондгой, нөгөө нь тэгш байсан юм. Үүнийг a=m*m-n*n, b=2*m*n гэдгээс батлаж болно. Ингээд тэгш ба сондгой тоогоор 2 талаа хийсан bipartite граф дээр matching олоход хангалттай. Ингээд submit хийтэл нэлээд дээгүүр (эхний 100 хавьцаа) орж байлаа. Гэтэл хэсэг тестэлсний дараа алдаа олов. Resubmit :(. Нэлээд хойшиллоо (~150).
2 бодлогоо submit хийсний дараа Medium дээр олон хүн greedy бодолт хийсэн байх гэж бодоод эсрэг тест байгуулав (35 12 5 612 :D). Coding Phase дууссаны дараа Medium дээр маш жижигхэн алдаа гаргаснаа ухаарав, ингээд Challenge Phase-д зайлшгүй амжилттай орох шаардлага тулгарав.
Challenge Phase : Нэг хүний бодолт нээтэл яг миний унагахыг хүсч байсан greedy байв. Ингээд (35 12 5 612) тестээ өгөөд унагав. Дахиад бодолт нээтэл бас л ойролцоо байхаар нь нөгөө тестээрээ гялс унагаад 100 оноо авлаа.
System testing Phase : Бодож байснаар Medium уналаа. Гэвч 198-д ороод rating үл ялиг өслөө, мөн л Maximum Rating :).
div 1 in uguulberiig sonirhoogui bolohoor mediumiin bodoltiig sn oilgodguiee! Yrunhiiduu bodolgiinhoo uguulberiig galit galit bichchuul nice bh bh! MAX-da hursend congratz!!
ReplyDelete@Мөнх-Очир : Баярлалаа, өгүүлбэрүүдээ хальт хальт бичье.
ReplyDeleteOroh bolgondoo MINIMUM avchaad bn tailbaraa jaahan delgerengui bolgood bicheed ugeech
ReplyDelete@Alaka: Topcoder-т хурд болон алдаагүй код хамгийн чухал. Practice, Practice and Practice.
ReplyDeletePythTriples c too ni hed baih ni hamaagui ymuu? bas tanii bichsen jishee ni deer 5 612 hoyr yagaad hos bolohgui bgaan?
ReplyDeleteDiv1 Medium : c too ni hed baih ni hamaagui ymuu? bas tanii bichsen jishee ni deer 5 612 hoyr yagaad hos bolohgui bgaan?
ReplyDelete5*5+612*612=374569=612.0204....... tgeed hos bolohgu hariu ali boloh olon hos oloh yotoi yum shig bn daa
ReplyDelete@Anonymous: a=5, b=612 байг. 5^2+612^2=c^2 байх c натурал тоо байхгүй.
ReplyDelete@Anonymous: Чиний ойлгосноор бодлогын хариу шууд N/2 гарчих гээд байх шиг байна хэхэ
ReplyDeleteaan za oilgoloo.
ReplyDeleteDiv2 & Div1 ee 2 ulang n oruulj bwal buur nice boloh bh ...
ReplyDeleteDiv 2-Easy -с бусдыг нь чадаад байвал оруулж болох байх :D.
ReplyDeleteSRM algasalgui oruulad bgaarai teul udkuu chamaas humuus english deer oruulj bai oilgohgui bn gej huselt iriishd
ReplyDelete