Хичээлийн шинэ жилийн нээлт (coder.mn)

Энэ удаагийн тэмцээн мөн л шагналтай байлаа.
Анх тэмцээн 9 бодлоготой байсан боловч Гоё дугаар нэртэй бодлого хасагдах нь тодорхой болов. Үлдсэн 8 бодлогын 7-г нь эхний өдөр бодсон ба Сайн тоо гэдэг бодлого 50% даваад тест нь эргэлзээтэй санагдав. Админуудаас асууж байгаад нэг тестийг нь автал яалт ч үгүй зөрөөд байсан бөгөөд тэмцээний 3 дах өдөр зохиогчийн тест буруу гэдгийг нотлож уг бодлого мөн л тэмцээнээс хасагдав. Ингээд тэмцээний сүүлийн өдөр 7 бодлого үлдсэн ч эхний өдөр бүгдийг нь бодчихсон учир сүүлийн өдөр кодуудаа хурдлуулах оролдлого хийсний эцэст түрүүллээ.

Small factorials :

Том тооны үйлдэл.

Цифрүүд :

Эхний оронд 9-д хуваахад гарах үлдэгдэл үлдсэн цифрүүдэд 9 байхад болно.

Нийлбэрүүд :

A[x] тоо нийлбэрт K*N^(K-1) удаа гарч ирнэ, иймд эцсийн хариу (A[1]+A[2]+...+A[n])*K*N^(K-1) гарна, N^(K-1)-г O(log(K))-р олоход хангалттай.

Тойрог дээрх цэгүүд :

Өгөгдсөн c тооны хувьд a^2+b^2=c^2 ба gcd(a,b,c)=1 байх a,b хосын тоог O(sqrt(C))-д олж болно. Анхны бодлогын хувьд R тооны бүх хуваагчдын хувьд дээрх хосын тоог олж нэмэд дөрвөөр үржихэд эцсийн хариу гарна. 4-р үржинэ гэдэг нь (a,b) (-a,b) (a,-b) (-a,-b) цэгүүд гэсэн үг.

Газрын маргаан :

S-г хоёр тооны квадратуудын нийлбэрт тавьж болох уу гэсэн бодлого. Хоёр тооны нэгийг нь бэхлээд S-n*n тоог бүтэн квадрат эсэхийг шалгавал O(sqrt(S)) болох ба арай амжихгүй, иймээд энэ бодолтыг сайжруулах хэрэгтэй. Миний хийсэн сайжруулалт гэвэл жишээ нь S тоо 7-р төгссөн бол N тоо 1-р төгсөж болохгүй гэх мэт.

Модтой тоглоё 1 :

Модыг дурын оройгоос нэвтрэлт хийгээд Rooted tree болгоё. Эхлээд бүх оройн хувьд уг орой ба түүнээс хүрч чадах бүх навчны хоорондох замуудын жингүүдийн нийлбэрийг олъё. Энийг бүх оройн хувьд хялбархан Динамик Програмчлал ашиглан O(N)-д олж чадах ба f(x) гэж тэмдэглэе. Дараа нь ямар нэг оройн хувьд уг оройг дайрдаг бүх хосын замын жингүүдийн нийлбэрийг олох. K орой байг, түүний хүүхдүүд нь c1,c2,... ба ирмэгүүдийн жин нь харгалзан w1,w2,... гэж үзье. Уг оройг дайрах ба мөн харгалзан cx,cy оройг дайрдаг бүх замын жингүүдийн нийлбэр нь (f(cx)+1)*wx*(f(cy)+1)*wy. Ингээд бүх хос хүүхдүүдийн энэ үржвэрүүдийг нэмэхэд дэд бодлого шийдэгдэнэ.

Модтой тоглоё 2 :

RMQ буюу Range Minimum Query төрлийн бодлого, энэ төрлийн бодлогуудыг бодох ерөнхий зарчим нь эхлээд байгуулалт хийгээд хүсэлт болгонд байгуулалтаа ашиглан түргэн олдог. Өгөгдсөн модыг Rooted tree болгоё. X,Y хүсэлтийн хувьд Z=Lowest Common Ancestor(X,Y) гэе. Тэгвэл (X,Z) (Y,Z) -н хувьд олоод min, max-г нь олохтой адилхан. Гэхдээ шинэ (X,Z) хүсэлт нь ямар нэг орой ба түүний эцгийн хувьд хийгдэх юм. Үүнийг Динамик програмчлал ашиглан O(logH)-д олох боломжтой. (H нь модны өндөр).