ACM ICPC Regional Dalian 2011

9 сарын 23-25ны хооронд БНХАУ-н Далиан хотноо ACM ICPC бүсийн тэмцээн амжилттай болж өнгөрлөө. Уг тэмцээнд Хонгор, Мөнх-Очир, Баасанбат нарын бүрэлдэхүүнтэй S.M.C.S баг Монгол улсаа (блогоо :P) төлөөлөн оролцоод ирлээ. Манай баг 2009 онд Монгол улсын анхны хүрэл медал, 2010 онд амжилтаа бататган дахин хүрэл медал хүртээд байсан билээ.

9.23:

Бид Бээжин хотоос 12 цаг галт тэргээр явсаар 9.23-ны өглөө Далиан хотод ирлээ. Ингээд тэндээсээ шууд бүртгэлдээ очиж тэмцээний билэгдэл болох футболкоо авцгаалаа. Уг өдрөө тэр хавиараа жаахан танилцсан байдалтай л өнгөрүүллээ.

9.24:

Энэ өдөр бол дасгал тэмцээний өдөр. Дасгал тэмцээний гол зорилго нь систем болон компьютер, эдитор гэх зүйлүүдтэйгээ танилцах зорилготой өдөр юм. Гэхдээ уг өдөр сайн орвол сэтгэл зүйн хувьд дээшлэх байх гэж бодож байлаа. Гэтэл санаснаас хамаагүй тааруу орлоо :(.

9.25:

Жинхэнэ тэмцээний өдөр. Өмнөх дасгал дээр сайн ороогүй учир жаахан эмээж байсан. За тэмцээн эхэллээ.
A-J хүртэл дугаарлагдсан 10 бодлого. Олон бодлогоо хувааж аваад уншиж байх хооронд эхний баг D бодлого дээр AC авлаа. Хамт уншихад үнэхээр хялбархан simulation төрлийн бодлого байсан. Кодоо бичээд submit хийлээ, хариу ирээгүй байхад буруу гэдгээ шууд мэдэв - freopen :). Тэнэг froepen-оо хаагаад явуултал мэдээж AC кк.
Дараагийн бодлогоо хайж байтал E бодлогыг бас л өөр баг AC авчихлаа. Жаахан бодсоны эцэст DP бодолтыг олов. Бичээд явуултал AC. Board хартал 16 хавьцаа явж байна, бөөн баяр .....
Хялбар бодлого хайж нэлээд л удлаа. Гэтэл I бодлогыг E-с ч олон хүн бодсон байх юм. Нэг л барьцгүй эвгүй бодлого байв. Тэгээд G бодлогыг уншихад болмоор санагдаад нэлээд хурдан санаа олохыг оролдсон, эцэст нь санаагаа ч оллоо. Гэхдээ бодлогууд хугацааны хязгаарлалтууд тодорхойгүй болохоор TLE авахаас айж байсан ч бичихээр шийдээд бичлээ. Жишээ тестүүдийг давж байна, өөрсдөө үүсгэсэн tricky тестүүдийг ч давж байна. Submit хийлээ, AC :).
Бодлого хайсаар, I дээр гацсаар. Гэтэл C бодлогыг 2 баг бодсон мөртлөө болмоор санагдаад бодоод бичлээ. Нэлээд удсаны эцэст submit хийхэд WA, бид нэг л юм орхиод байгаа бололтой.
Сүүлийн 1 цаг эхэллээ, 2 цаг зүгээр суучихлаа, байдал эвгүй болж эхэлж байна ккк. Одоо манай эцсийн боломж I гэдгийг мэдэж байсан. I бодлогыг бодоход манайд хэрэгтэй байсан ганц зүйл нь 1^4+2^4+..+n^4 -г O(1)-д олдог томъёо. квадрат зэрэг, куб зэргийг мэдэж байсан ч 4 зэргийг мэддэггүй шүү. Томъёог нь гаргах гэж үзээд ч чадсангүй. n<=10^8 байсан болохоор нэг удаа precomputation хийчихвэл O(1)-д олж чадна. Гэхдээ л memory-д багтсангүй, TLE ч авлаа. 8 минут үлджээ, эцсийн эцсийн эцсийн арга гээд үзлээ. 1..10^8 хүртэл бүх утга биш харин 0-р төгссөн тоонуудыг нь хадгалчихвал ямар ч тоог ихдээ O(10) үйлдэл хийгээд олж чадна. Энэ бодолтоо Submit хийгээд 295 дахь минутанд AC. Хэзээ ч бодлого бодоод ингэж их баярлаж байсангүй кк. Дүнгийн хурал: Манайх мөнгө эсвэл хүрэл медал авах нь ойлгомжтой байсан. Хүрэл медалуудыг дуудсаар, манайх дуудагдсангүй :). Мөнгөн медал дээр S.M.C.S багийг дуудлаа. Ингээд анхны мөнгөн медалыг МУИС-МКС-н S.M.C.S баг хүртлээ.