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: Мөнх-Очир болон Сугардорж нарт баяр хүргэе.
  • Irmuun said... November 27, 2010 at 3:49 AM
    Hongor nart bayar hurgeye.
    Hongoriin bodolt zuv.
    Chi Monte Carlo algorithm hereglesen gsn ug.
    Medeej S=C bol duriin x vectoriin huvid Sx=Cx bn.
    Harin S<>C uyed duriin x vectoriin uyed Sx=Cx bh magadlal hed ve?
    Ene magadlal baga uchraas Monte Carlo -doh bolomj garch bn gan ug :)
  • Irmuun said... November 27, 2010 at 3:50 AM
    gsn ug
  • Мєнх-Очир said... November 27, 2010 at 4:22 AM
    Баярлалаа! Чамд бас баяр хүргэе! S=C? ижилхэн бодсон байна. Би D матрицаа {1,1,1,1,1..} гэж үүсгээд бодсон болчихсон. Би бас Monte Carlo-дсон байна. кк
  • Anonymous said... November 30, 2010 at 4:06 AM
    sain baina uu. sugardorj baina. minii huvid ene s=c bodlogiig det(s)=det(c) gedeg shalguur taviad l yavuulsan chini davchihsan. (ehleed mur solihod det=-det boldgiig orhiod undsen testees 1iig l davaad baisan baina lee).
    daraa ni siin ehnii mur, c iin ehnii murtei tentseh eseheer shalguur hiihed davchihaar ni test sul yum gej bodogdson. test zassanii daraa detS=detC gehed davj baisan. harin siin ehnii mur ciin ehnii mur gesen shalguur hugatsaag iluu baga bolgoson. miniih uvid aztai l bailaa gej heley dee
  • Irmuun said... November 30, 2010 at 6:43 PM
    @Sugardorj:
    Test-ee uusgehdee C -g yerunhiiduu random -dson bolohoor sul test uussen.
    Uul ni medej bsan bolovch zalhuuraad bsiimaa. kk
  • one said... December 5, 2010 at 11:48 PM
    monte carlo algorithm yunii algorithmiin .... yostoi medeh yum gj yu ch algaa... suraal bhaas
  • Anonymous said... January 7, 2011 at 9:34 AM
    sain
  • Anonymous said... June 3, 2011 at 5:52 AM
    @Hongor: Goy blog bn :D neleen hedn bodlogo chinii sanag haraad bodchihloo shd

Post a Comment