TCO 11 Elimination Round 2

Энэ үе хүртэл 850 хүн шалгарч үлдсэн ба шилдэг 350 оролцогч цааш оролцох авахаас гадна T-Shirt авна :). Өмнөх үед бусад Монголчууд маань шалгарч чадаагүй учир ганцаараа оролцов. Ганц дайчин юу гэдэг билээ :D.
Division 1: Khongor

Тэмцээн эхэллээ. Бодлогуудын оноо 250, 500, 1000 байсан учраас medium-г бодох боломжтой гэж таамаглалаа. Эхлээд easy буюу 250 онооны бодлогыг нээлээ.
250:
Зөвхөн Y,N үсгээс тогтох тэмдэгт мөрийг "баримт" гэж нэрлэе. Тэмдэгт мөрийг 1-с эхлэн индекслэх ба хэрвээ i-р үсэг Y байвал тоо i-д хуваагдана, N байвал хуваагдахгүй. Өгөгдсөн (<=1000000) урттай өөрт нь ядаж нэг тоо тохирох нийт "баримт"-н тоог ол.
Бодлогыг оролдсоор байсан ч нэг л болж өгөхгүй, санаа орж ирэхгүй, цаг өнгөрсөөр нэг хартал 20 минут өнгөрчээ. Маш олон хүмүүс хурдтай бодож байсан болохоор би одоо энэ бодлогыг бодсон ч цаашид шалгарч чадахгүй нь тодорхой байсан. Тийм учраас эцсийн боломж болох medium-ээ нээлээ.

500:
s,t 2 тэмдэгт мөр өгөгдсөнө. C(i,j) (i=0..n) (j=0..m) тэмдэгт мөрөн хүснэгтийг дараах аргаар үүсгэе. Эхлээд C(0,j) дагуу s тэмдэгт мөрийг, C(i,0) дагуу t тэмдэгт мөрийг бичнэ. Үлдсэн нүднүүдийг C(i,j)=min(C(i,j-1),C(i-1,j))+max(C(i,j-1),C(i-1,j)) буюу зүүн болон дээд талын нүдэн дэх 2 тэмдэгт мөрийн цагаан толгойн дарааллаар бага дээр нь нөгөөг нь залгах байдлаар үүсгэнэ. Таны даалгавар C(n,m) нүдэн дэх тэмдэгт мөрийн ямар нэгэн хэсгийг олох юм. Хэсгийн урт 50-с хэтрэхгүй. Хамгийн хэцүү зүйл нь C(n,m) дээр үүсэх тэмдэгт мөрийн урт 10^18 байж болно. Иймээс шууд үүсгэх боломжгүй. Хэрвээ C(n,m)-н ямар нэг үсгийг олж чаддаг бол бүх үсгүүдийг залгаснаар бодлогыг бодож болно. Ямар нэгэн K дах үсгийг олохдоо зүүн тал эсвэл дээд талын алинд хамаарагдахыг олсноор бодлогыг бодож болно. Хялбар сонсогдож магадгүй ч нэлээд хэцүү бодлого байсан. Хамгийн гол нь Topcoder-н тэмцээн 75 минут үргэлжилдэг учраас хурдан бодох хэрэгтэй. Ямар ч байсан бодлогыг бичиж дууслаа, 4 минут үлджээ :). Тэмцээний дүнг харлаа, хэрвээ medium маань давах юм бол 350-д багтна.

System Test дуусч бодлого минь давлаа, бөөн баяр :). Одоо мэдээж ханах болоогүй шилдэг 150-д орох хэрэгтэй :D.
  • Маахай Л.Очирхуяг said... July 6, 2011 at 2:33 PM
    Сайн байна, Амжилт хүсэе!
  • Alaka said... July 9, 2011 at 11:14 PM
    Bayar hurgye :D gehdee 150d yagaad chadaagui yum be ter 250-iig
  • Хонгор said... July 10, 2011 at 1:36 AM
    @Alaka: 250 хэцүү шдээ кк. Дандаа мундаг хүмүүс орж байгаа болохоор л хурдан бодож байгаа юм. Санаа нтр-г нь яг зөв олчихоод алдчихсан байна лээ.
  • Anonymous said... July 17, 2011 at 6:42 AM
    Ta T-shirt avsan u?
  • Хонгор said... July 17, 2011 at 6:48 PM
    @Anonymous: Аанха, e-mail ирсэн. T-Shirt нь Final нтр дууссаны дараа илгээгдэнэ гэсэн. Одоо хүлээх л үлдлээ :D
  • Anonymous said... July 18, 2011 at 10:26 PM
    @Khongor: Congrats!

Post a Comment