SRM 477

Монгол улсаас энэ удаа хамгийн олон хүн буюу 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 :).
  • Мєнх-Очир said... July 29, 2010 at 9:08 AM
    div 1 in uguulberiig sonirhoogui bolohoor mediumiin bodoltiig sn oilgodguiee! Yrunhiiduu bodolgiinhoo uguulberiig galit galit bichchuul nice bh bh! MAX-da hursend congratz!!
  • Хонгор said... July 29, 2010 at 10:26 PM
    @Мөнх-Очир : Баярлалаа, өгүүлбэрүүдээ хальт хальт бичье.
  • Alaka said... July 30, 2010 at 6:36 AM
    Oroh bolgondoo MINIMUM avchaad bn tailbaraa jaahan delgerengui bolgood bicheed ugeech
  • Хонгор said... July 30, 2010 at 7:03 AM
    @Alaka: Topcoder-т хурд болон алдаагүй код хамгийн чухал. Practice, Practice and Practice.
  • Anonymous said... July 30, 2010 at 8:49 AM
    PythTriples c too ni hed baih ni hamaagui ymuu? bas tanii bichsen jishee ni deer 5 612 hoyr yagaad hos bolohgui bgaan?
  • Anonymous said... July 30, 2010 at 8:50 AM
    Div1 Medium : c too ni hed baih ni hamaagui ymuu? bas tanii bichsen jishee ni deer 5 612 hoyr yagaad hos bolohgui bgaan?
  • Alaka said... July 30, 2010 at 9:45 AM
    5*5+612*612=374569=612.0204....... tgeed hos bolohgu hariu ali boloh olon hos oloh yotoi yum shig bn daa
  • Хонгор said... July 30, 2010 at 6:51 PM
    @Anonymous: a=5, b=612 байг. 5^2+612^2=c^2 байх c натурал тоо байхгүй.
  • Хонгор said... July 30, 2010 at 7:04 PM
    @Anonymous: Чиний ойлгосноор бодлогын хариу шууд N/2 гарчих гээд байх шиг байна хэхэ
  • Anonymous said... July 31, 2010 at 7:39 AM
    aan za oilgoloo.
  • XaCaHaa said... August 4, 2010 at 11:15 PM
    Div2 & Div1 ee 2 ulang n oruulj bwal buur nice boloh bh ...
  • Хонгор said... August 4, 2010 at 11:29 PM
    Div 2-Easy -с бусдыг нь чадаад байвал оруулж болох байх :D.
  • XaCaHaa said... August 6, 2010 at 1:06 AM
    SRM algasalgui oruulad bgaarai teul udkuu chamaas humuus english deer oruulj bai oilgohgui bn gej huselt iriishd

Post a Comment