Хичээлийн шинэ жилийн нээлт (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 нь модны өндөр).
  • Мєнх-Очир said... October 2, 2010 at 3:06 AM
    1-t orsond chini bayar hurgeye! Bodlogiin analys-uud ih tovchhon sanagdlaa! keep blogging!
  • Хонгор said... October 2, 2010 at 3:35 AM
    @Мөнх-Очир : Баярлалаа, удахгүй илүү дэлгэрүүлж бичнэ ээ.
  • Alaka said... October 2, 2010 at 6:21 AM
    TC SRM bichxee bolison yumuu
  • Anonymous said... October 2, 2010 at 8:36 AM
    @Хонгор : Таниас хэдэн юм асуух гэсэн юмаа. "Модтой тоглоё 1" дээр бодлогын нийт complexity нь хэд болох бол. Бас "Модтой тоглоё 2" дээр Lowest Common Ancestor гэдгийг тайлбарлаад өгөөч.(wiki дээд үзсэн ч ойлгодоггүй).
  • Хонгор said... October 2, 2010 at 7:13 PM
    @Alaka: Ойрд medium бодож чадахгүй болохоор биччихээр ч юм олдохгүй юм.

    @Anonymous: Нэрээ биччихэж байгаарай, хэнд тайлбарлаж өгч байгаагаа мэдэх хэрэгтэй. Модтой тоглоё 1 дээр Rooted tree болгохын тулд dfs хийгээд O(N), динамик програмчлал дээр орой болгоны хувьд түүний зөвхөн хүүхдүүд дэх мэдээллийг хадгална, энэ нь нийт ирмэгийн тоотой тэнцүү буюу O(N) болно, ингээд нийт O(N). Модтой тоглоё 2 дээр Lowest Common Ancestor гэдэг нь модны 2 оройн хувьд тэр 2 той хамгийн ойрхон орших ерөнхий эцэг ба үүнийг олох асуудал нь Range Minimum Query-тэй холбогддог. Эндээс гоё тайлбарыг олж болох байх - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
  • Anonymous said... October 2, 2010 at 8:10 PM
    DP DP l geh yum. ter chin l sonin bain. bichchij boldoggui yumuu.
  • Anonymous said... October 2, 2010 at 8:26 PM
    @Anonymous : Ter Dp chi uuruu l oljdee
  • Anonymous said... October 2, 2010 at 8:31 PM
    @Anonymous : Enenees sain tailbar gej haashaa harsan yum baihav de . :D
  • Хонгор said... October 2, 2010 at 11:18 PM
    @Шүүмжилсэн Anonymous: Энэ блог анхан шатны хүмүүст зориулаагүй бөгөөд бодлогын ерөнхий санааг л тайлбарлан бичсэн байгаа.
    @Өмөөрсөн Anonymous: Сайн тайлбар биш ээ, нэлээд товчхон байгаа.
  • Anonymous said... October 3, 2010 at 2:26 AM
    Hongort amjilt husie
    chi pascal deer bdag daraah funtsuudiig c++ deer jisheetei ni bichij ywuulbal ih sain bn Bi pascalaas c++ surch bgaa yum l daa6
    1. delete(st,n,k)-st тэмдэгт мөрийн n-р байрлалаас K-ширхэг тэмдэгт устгана
    2. insert(st1,st2,n)
    3. copy(st,n,k)
  • Tugsuu said... October 3, 2010 at 2:36 AM
    Санаа өгсөнд баярлалаа. Монгол мэдээллийн технологын чиглэлээр дэлхийд тэргүүлэх болтугай!
  • Хонгор said... October 3, 2010 at 3:25 AM
    @Anonymous: Уг нь иймэрхүү юмыг http://www.cplusplus.com -с харчихвал зүгээр, бүх жишээтэйгээ байдаг болохоор. Жишээ нь string-н тухай гэвэл
    http://www.cplusplus.com/reference/string/string/
  • Shurenchuluun said... October 4, 2010 at 4:57 AM
    Товч бөгөөд тодорхой, их юм ойлгож авлаа, баярлалаа, амжилт хүсье.
  • Suba said... October 4, 2010 at 7:08 PM
    Түрүүлсэнд чинь Баяр хүргэе..

Post a Comment