11-р сарын тэмцээн (coder.mn)

Энэ удаагийн тэмцээнийг Irmuun гишүүн санаачлан зохион байгуулав. Уг тэмцээн 5 бодлоготой байв.

Ингээд өөрийн бодолтын санаануудыг сонирхуулъя.

Баавгай :

Баавгайн зогсож байгаа мөр баганы дугаарыг мэдэх ба үйлдэл гүйцэтгэх болгонд мөр, эсвэл багана нь нэгээр нэмэгдэнэ, эсвэл хорогдоно. Ингээд ямар нэгэн R,C нүдэнд харгалзах тоог O(1)-д олж чадсанаар анхны бодлогыг O(K)-д бодно.

13-р үе:

Өгөгдсөн тоонуудыг өсөхөөр эрэмбэлээд A дараалал гэе. Тэгвэл анхны бодлого маань B(1)<=B(2)<=...<=B(n) ба B(i)<=A(i) [i=1..n] байх хичнээн янзын B дараалал байгаа вэ гэсэн бодлоготой ижил, энэ бодлогыг хялбархан DP ашиглаад бодож болно.

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

S оройгоос эхлээд ямар нэгэн T орой дээр дуусахад ямар зам туулахыг тооцъё. Замын сүлжээ нь мод бүтэцтэй учир хамгийн дөт зам нь S->T хүрэх замд байгаа ирмэгүүдийг 1 удаа, бусад бүх ирмэгийг 2 удаа дайрна. Хэрвээ нийт ирмэгийн уртын нийлбэрийг A гээд D(S,T)-р S-с T хүрэх замын уртыг тэмдэглэвэл нийт туулах зам нь 2*A-D(S,T) байна. Энэ илэрхийллийн утгыг хамгийн бага байлгахын тулд D(S,T)-г хамгийн их байлгах хэрэгтэй ба энэ нь S-с хамгийн хол зайд байрлах навчны урттай тэнцүү, энэ нь DFS, BFS, DP -н алийг нь ч ашиглан олж болно.

Нийлбэрийг ол:

D(n)-р n тооны хуваагчийн тоог тэмдэглээд, F(n) = Summa(D(i)) {i=1..2*n} гэвэл бодлогийн хариу нь F(1)+F(2)+...+F(n-1).

S=C?:

S-г шууд олно гэвэл N*N хэмжээстэй 2 матрицыг үржихэд O(N^3) учир O(K*N^3) байна (K нь тэмдэгт мөрийн урт). Том тестэн дээр яагаад ч амжихгүй. S=C гэж үзье. Тэгвэл дурын D[1..N] матрицын хувьд D*S=D*C байна. Би D*S=D*C бол YES үгүй бол NO гэж үзсэн, гэхдээ D матрицын сонголтоос хамаарад алдаж болно, Жишээ нь D нь 0 матриц байвал S,C -с үл хамааран тэнцнэ. Энэ бодолт яг зөв гэдэгт эргэлзэж байна. Миний хувьд D-г санамсаргүй үүсгэж бодсон.

P.S: Мөнх-Очир болон Сугардорж нарт баяр хүргэе.