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 баг хүртлээ.

Тэмцээн - 1

Юуны өмнө тэмцээнд оролцсон хүмүүст баярлалаа. Бас эхний байруудад орсон idiot, tvvv, Adya 3т баяр хүргэе.
Одооноос кодер дээрх тэмцээнүүдийг Тэмцээн тэд гэж нэрлэнээ. хэхэ, гадны сайтуудыг л дагаж байнадаа. Тэмцээний цагийг бас иймэрхүү орой хийвэл яаж байна саналаа үлдээгэрэй. Бодлогуудын хувьд бас л гадны сайтуудаас бодсон бодлогуудаас ишлэж зохиосон, тэстүүдэд бас их цаг гаргаж TRICKY тэстүүд их оруулсан. Ингээд бодлогын анализ хийе.
Эргэлт
Энэ хамгийн амархан бодлого байсан байх. Мөрийн дагуу хэд эргэх баганы дагуу хэд эргэхийг бодож үзсэн бол хариу: min(n*2-2, m*2-1)
35
Мэдээж цөөн сав хэрэглэхийн тулд аль болох 5-н сав ашиглах хэрэгтэй. Хэрэв N тоо 5-д хуваагдахгүй бол ядаж нэг удаа 3-н сав ашиглаж ёстой.
Бага тоо
Шууд хүчээр тоог 1-ээр ихэсгээд бодлогын шаардлагыг хангах тоог гаргаж авж болно. Хэрэв саяас илүү удаа 1-ээр нэмэгдүүлэх үйлдэл хийсэн бол шийдгүй юм. Өөр нэгэн бодолт өгөгдсөн тоон оронгийн тоонуудыг бүх боломжоор сэлгэж бодлогын хариуг гаргаж болно. N<=999999 учир бид хамгийн ихдээ 6! үйлдэл хийгдэх юм.

Тэгш өнцөгт

Энэ бодлогын өгүүлбэрийг их буруу бичсэнүү, хүмүүс ойлгох гэж цагаа их алдсан байх. Энэ бодлого нь codeforces.com дээр бүх боломжийг шалгахаар бодож болохоор өгөгдсөн ба та эндээс харж болно. Харин би хязгаарлалтыг сая болгож бүх боломжийг шалгах боломжгүй болгосон юм. Миний бодолт бол динамик програмчлал ашиглах ба left[i]-ээр тухайн i-р тэгш өнцөгтийн зүүн талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү урттай тэгш өнцөгтийн тоог тэмдэглэнэ. Үүнтэй адилаар right[i]-ээр i-аар хайрцагны баруун талд орших түүнтэй хөрш бөгөөд дараалсан мөн өөрөөс нь бага буюу тэнцүү өндөртэй тэгш өнцөгтүүдийн тоог тэмдэглэв. Тэгвэл хариу max(left[i]+right[i]) (i=1..n). Бодолт O(N)

Тэгийн тоо

Факториалын сүүлийн 0-үүдийн тоог яаж олдог хүмүүс бол бодох л байсан бодлого. Бодлогын хариунд тооцогдож болох үржвэрийн тэгүүдийн тоо нь min(fac2, fac5) юм. Энд fac2, fac5 нь 2 болон 5ууд тус бүр хэдэн удаа үржвэрт байгааг илэрхийлнэ. Энэ нь бидэнд бодлогыхоо хариуг гаргаж авахад заавал бүх тоог үржүүлэхээс зайлсхийх боломжийг олгох юм. Одоо бодлогоо динамик програмчлал ашиглан хоёр өөр маршрут гаргаж авна. Нэг нь үржвэрт хамгийн бага 2 орсон, нөгөө нь мэдээж хамгийн бага 5 орсон. Тэгвэл хариу нь уг 2 маршрутын бага нь болно. Бодолтыг O(N^2)-аар шийднэ.

Mario on Box
Энэ бодлогыг одоохондоо бичихгүйгээр шийдлээ.