2 ч хүн энэ бодлогын бодолтыг асуусан байсан. Өгүүлбэр
Динамик програмчлал буюу DP-н гоё бодлого, Монголд оюутан байхдаа өөрөө бол бодож чаддаггүй л байсан санагдаж байна.
Бодолт:
2n хүмүүс байгаа гэж үзье. Аль нэг O цэг/хүнийг сонгож аваад аль аль хүнтэй гар барьж болохыг судлаж үзье. Ямар ч байсан уг O цэгээс өөр тохирох хүнтэй гар барингуут тухайн шулуун нь дугуй ширээг буюу өөрөөр хэлбэл уг 2n цэгийг хоёр хэсэгт хуваана. Ингэхдээ уг хоёр хэсэгт байгаа цэгүүдийн тоо заавал тэгш байх ёстой бас. Цаашаа жаахан бодоод үзэхээр O цэг/хүнтэй гар барьж болох цэгүүдийн/хүмүүсийн тоо нь яг n ширхэг байгаа.
Одоо дан шулуунаар яриад явая. Дээр О цэгээс эхлэлтэй шулуун бүр 2n цэгүүдийг дандаа ялгаатай хэсэгт хуваана, мөн хуваагдсан хэсэг бүрийг дахин дугуй ширээн дээрх хүмүүс мэтээр сэтгээд дэд бодлого болгоод бодно. Тэгвэл аль нэг дээрх шулууныг татахад хуваагдсан хоёр талд тус бүр хичнээн цэгүүд байх ёстойг мэдэх хэрэг гарна. Хэрвээ мэдчихвэл манай бодлогын хариу уг хоёр дэд бодлогын үржвэрүүдээр нэмэгдэх ёстой. Сайн бодож хараарай.
О цэгээс татсан шулууны боломжит нөгөө цэгүүдийг нь K гэе. 0<=K<=n-1, тэгвэл хуваагдсан хоёр талын цэгүүдийн тоо нь тус бүр 2*K, 2*(n-K-1) байна. Тус бүр эдгээр тооны цэгүүдтэй дугуй ширээн дээр суусан хүмүүсийн гар барилтын тоог мэдэж чадвал бодлогын хариу маань уг гар барилтын тоонуудын нийлбэр байна. Дэд бодлогот хэрхэн хувааж байгааg хараарай.
f(n)-ээр n хүмүүс дугуй ширээнд суухад хичнээн гар барилт байгааг тэмдэглэе. Тэгвэл
f(n) += f(2k)*f(2(n-k-1)), k=(0..n-1) байна. Энд нэг гарах ёстой асуулт бол ингэж хоёр хувааж байхад хуваагдсан хэсэгт яаж хуваах нь хамаатай биш билүү? үүнийг тооцох ёстой биздээ? бодолт/тоолот дутуу юм бишүү? гэсэн асуулт гарна. Сайн бодоо үз, өмнөх дэд бодлогын бодолтод тоологдцон байгаа.
Бодлогын бодолтыг C++ дээр доорх линк-ээр орж сонирхоорой(f(n)-ээр огтлоогүй шулуунуудын тоог тэмдэглэж бодсон байгаа, ялгаагүй бодолт).
Source
Monday, November 7, 2016
Thursday, November 3, 2016
QonR
Сайн байцгаана уу
Одоо хэсэгтээ шинэ пост оруулахгүй байх, гэхдээ асуух бодлого, сонирхож хэрэг болсон алгоритм байвал baasanbatp@gmail.com хаягруу явуулвал аль болох хурдан зав гаргаад хариу бичиж эсвэл хэрэгтэй гэж үзвэл энд постоор тайлбарлаж байна аа.
Одоо хэсэгтээ шинэ пост оруулахгүй байх, гэхдээ асуух бодлого, сонирхож хэрэг болсон алгоритм байвал baasanbatp@gmail.com хаягруу явуулвал аль болох хурдан зав гаргаад хариу бичиж эсвэл хэрэгтэй гэж үзвэл энд постоор тайлбарлаж байна аа.
Thursday, May 12, 2016
Графын онол II (Friend IOI14 Part II)
Хэд хэдэн онолын нэрүүдийг монголоор сайн мэдэхгүй юм. Мэдэх нэг нь комментоор үлдээгээрэй.
::Maximum Independent Set
Аль ч хоёр орой нь хөрш байх ёсгүй оройн олонлог гэхээр үүнийг independent set гэдэг. Энэ олонлогийн оройн тоог байж болох хамгийн ихээр нь байлгаж чадвал үүнийг maximum independent set гэдэг. Энэ бодлого бол шийдэгдээгүй бодлого NP буюу одоогоор мэдэгдэж байгаа хамгийн сайн алгоритмын үнэлгээ нь non-polynomal ба олон гишүүнт хэлбэрээр тавигдахгүй гэсэн үг. Үүнийг a(v) гэе.
::Minimum Vertex Cover
Графаас хэд хэдэн оройн сонгон оройн олонлог авах ба үүссэн олонлог дахь орой болгон нь анхны том графын ядаж нэг ирмэгт харьяалагдаж байвал үүнийг vertex cover гэдэг. Бүрхэлт гэх юмуудаа. Мөн уг олонлогийн оройн тоог байж болох хамгийн багад хүргэж чадвал үүнийг minimum vertex cover гэж байгаа юм. Үүнийг b(v) гэе.
Ерөнхий тохиолдолд дээрх хоёр бодлого хоюулаа NP бодлого.
::Konig's theorem
Графын нийт оройн тоо V = a(v) + b(v)
::Bipartite граф
Графыг аль ч хоёр хөрш орой нь ялгаатай өнгөөр будагдсан байхаар будахад яг 2 будаг хэрэг болдог графыг bipartite граф гэдэг. Ийм графын хэрэглээ маш өндөр. Ийм граф дээр b(v) тоог олох нь компьютерийн шинжлэх ухаанд маш их хэрэг болж байгаа, учир нь O(EVf*) хугацаанд b(v)-г олох алгоритм байгаа. a(v) = V-b(v) гээд хялбархан олчиж байгаа биз.
::Maximum Matching
Оюутнууд болон оюутны байр байг. Оюутнууд аль аль өрөөнд орох хүсэлтэй байгаа хүсэлт нь өгөгдсөн, нэг өрөөнд нэг л оюутан байх ёстой бол хамгийн ихдээ хичнээн оюутан өрөөнд орж чадах вэ? гэсэн бодлого байг. Үүнийг зүүн талд нь бүх оюутнуудыг графын оройнууд болгоод цувуулаад тавья. Баруун талд нь бүх өрөөнүүдийг тавье.
Дээр үүссэн граф бол bipartite graph. Дээр тавигдсан бодлогын хариу буюу хамгийн их хоёр хосыг байгуулах бодлого нь maximum matching юм. Хамгийн их хос оройн тоо гэх юмуудаа. Үүнийг network flow ашиглаад олчихдог. Flow-н талаар ЭНД дарж уншина уу. Товчхондоо бол графыхаа хоёр талд нь нэмээд хоёр орой тавиад (зүүн талд нь эхлэл s, баруун талд нь төгсгөлын орой t) ирмэг бүрт урсгалын 1 гэсэн утга өгөөд алгоритмаа гүйлгэчинэ.
Миний бичсэн Ford-Fulkersonий энгийн цэвэрхэн код ЭНД дарж харна уу. Өөрөө гол нь сураарай.
Дэд бодлого 5 дээр анализ хийе
Зөвхөн дүрэм 0 болон 1 гэхээр графаа зураад үздээ. Яаж ч байсан сондгой урттай цикл үүсэхгүйг хараад батлах гээд үзээрэй. Үүсэж болох графын оройн зэрэг дээр тулгуурлаад гарчина. Сондгой цикл байхгүй гэхээр үүсэх граф маань bipartite граф болно. Maximum Matching-г олоод нийт оройн тооноос хасахад манай бодлогын хариу гарж ирнэ. Графаа яаж байгуулж байгаа, бас бус зүйлүүдийг яаж шийдсэнийг кодноос харна уу.
source
::Maximum Independent Set
Аль ч хоёр орой нь хөрш байх ёсгүй оройн олонлог гэхээр үүнийг independent set гэдэг. Энэ олонлогийн оройн тоог байж болох хамгийн ихээр нь байлгаж чадвал үүнийг maximum independent set гэдэг. Энэ бодлого бол шийдэгдээгүй бодлого NP буюу одоогоор мэдэгдэж байгаа хамгийн сайн алгоритмын үнэлгээ нь non-polynomal ба олон гишүүнт хэлбэрээр тавигдахгүй гэсэн үг. Үүнийг a(v) гэе.
::Minimum Vertex Cover
Графаас хэд хэдэн оройн сонгон оройн олонлог авах ба үүссэн олонлог дахь орой болгон нь анхны том графын ядаж нэг ирмэгт харьяалагдаж байвал үүнийг vertex cover гэдэг. Бүрхэлт гэх юмуудаа. Мөн уг олонлогийн оройн тоог байж болох хамгийн багад хүргэж чадвал үүнийг minimum vertex cover гэж байгаа юм. Үүнийг b(v) гэе.
Ерөнхий тохиолдолд дээрх хоёр бодлого хоюулаа NP бодлого.
::Konig's theorem
Графын нийт оройн тоо V = a(v) + b(v)
::Bipartite граф
Графыг аль ч хоёр хөрш орой нь ялгаатай өнгөөр будагдсан байхаар будахад яг 2 будаг хэрэг болдог графыг bipartite граф гэдэг. Ийм графын хэрэглээ маш өндөр. Ийм граф дээр b(v) тоог олох нь компьютерийн шинжлэх ухаанд маш их хэрэг болж байгаа, учир нь O(EVf*) хугацаанд b(v)-г олох алгоритм байгаа. a(v) = V-b(v) гээд хялбархан олчиж байгаа биз.
::Maximum Matching
Оюутнууд болон оюутны байр байг. Оюутнууд аль аль өрөөнд орох хүсэлтэй байгаа хүсэлт нь өгөгдсөн, нэг өрөөнд нэг л оюутан байх ёстой бол хамгийн ихдээ хичнээн оюутан өрөөнд орж чадах вэ? гэсэн бодлого байг. Үүнийг зүүн талд нь бүх оюутнуудыг графын оройнууд болгоод цувуулаад тавья. Баруун талд нь бүх өрөөнүүдийг тавье.
Дээр үүссэн граф бол bipartite graph. Дээр тавигдсан бодлогын хариу буюу хамгийн их хоёр хосыг байгуулах бодлого нь maximum matching юм. Хамгийн их хос оройн тоо гэх юмуудаа. Үүнийг network flow ашиглаад олчихдог. Flow-н талаар ЭНД дарж уншина уу. Товчхондоо бол графыхаа хоёр талд нь нэмээд хоёр орой тавиад (зүүн талд нь эхлэл s, баруун талд нь төгсгөлын орой t) ирмэг бүрт урсгалын 1 гэсэн утга өгөөд алгоритмаа гүйлгэчинэ.
Миний бичсэн Ford-Fulkersonий энгийн цэвэрхэн код ЭНД дарж харна уу. Өөрөө гол нь сураарай.
Дэд бодлого 5 дээр анализ хийе
Зөвхөн дүрэм 0 болон 1 гэхээр графаа зураад үздээ. Яаж ч байсан сондгой урттай цикл үүсэхгүйг хараад батлах гээд үзээрэй. Үүсэж болох графын оройн зэрэг дээр тулгуурлаад гарчина. Сондгой цикл байхгүй гэхээр үүсэх граф маань bipartite граф болно. Maximum Matching-г олоод нийт оройн тооноос хасахад манай бодлогын хариу гарж ирнэ. Графаа яаж байгуулж байгаа, бас бус зүйлүүдийг яаж шийдсэнийг кодноос харна уу.
source
Wednesday, May 11, 2016
Мэдээлэл зүйн олон улсын олимпиадын тухай (Friend part I)
Олон улсын мэдээлэл зүйн олимпиад гэж ямархуу бодлоготой тэмцээн болдогийг сонирхуулах бас ирээдүйд явах хүүхдүүдэд бага ч гэсэн мэдрүүлж тайлбарлах үүднээс уг постыг бичлээ.
Ямар бодлого сонгож авах вэ гэж бодож байгаад 14 оны Friend гэж бодлогыг сонголоо. Бодлогын өгүүлбэрийг нь илүү дутуу зүйлүүдийг хасаж орчууллаа. Граф юмшиг харагдаж байгаа ч дэд бодлого гэж яагаад оруулаад байгаан мөн чанар, яагаад сүүлийн жилүүдэд уг тэмцээн маань илүү шударга олимпиад болоод байгааг харуулахыг хичээлээ. Товчхондоо бол бодлогын өгүүлбэрийг уншаад аан энэ граф байна гээд дүгнэж болно. Бүтэн бодолт маань мэдээж бүх тохиолдлыг давах ёстой. Бүх тохиолдол гэж ярьж байгаа маань тохиолдлуудыг дотор нь дахиад ангилчиж болохыг харж байгаа байх. Хүүхэд хичээж хичээж маш их цаг хугацаа, бэлтгэл зарцуулж энэ тэмцээнд орж байгаа, тодорхой түвшинд уг бодлогыг бодож чадах хэмжээнд байгаа, бүх тохиолдлыг биш ч хэд хэдэн тохиолдолд нь бодолт хийх хэмжээний хүүхдүүд байгаа. Энэ хүүхдүүдийг үнэлэх ёстой гэдэг нь хамгийн чухал зүйл юм. Жишээ нь энэ Friend гээд бодлого графын бодлого мөн нь мөн. Гэхдээ эхний 3-н дэд бодлого нь энгийн цикл, 4 дэх бодолт нь динамик програмчлал, 5 дахь бодлого онол жаахан шаардсан, 6 буюу бүтэн бодолт шаардах дэд бодлого бол сэтгэх, сэтгэлгээ туршлага шаардсан.
Энэ бодлого бол 2014 оны хоёр дахь хамгийн хүнд бодлого. Гэхдээ эхний 4н дэд бодлого нь ямар амархан болохыг хараарай.
Дэд бодлого бүрийг спож дээрх өөрийн хуудсанд тухайн таарсан тесттэй нь хамт оруулж бэлдлээ. Өөрсдийн бодолтоо шалгаарай. Бүгд албан ёсны бэлтгэгдсэн тестүүд байгаа шүү, минийх биш.
Дэд бодлого 4
Дэд бодлого 5 Үүсэх граф нь bipartite буюу дурын хоёр орой нь ялгаатай өнгөөр будахад хоёрхон өнгө хангалттай байх граф байгаа.
N оройтой (оройг 0..N-1 дугаарласан) чиглэлгүй мөн орой болгон нь эерэг тоон жинтэй граф өгөгдсөн. Графаа байгуулахдаа N алхамаар байгуулна, алхамуудаа мөн 0-ээс эхлэж дугаарлана. Хамгийн эхлээд буюу алхам 0-т граф зөвхөн 0 (оройн дугаар шүү!) гэсэн оройг нэмнэ. Дараачын алхам i (1 < i < N) бүрт доорх 3-н дүрмүүдийн нэг нь байна:
Дүрэм 0* HOST 0 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройтой холбоно.
Дүрэм 1* HOST 1 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройн бүх хөрш оройнуудтай холбно. Гэхдээ HOST-той холбохгүй.
Дүрэм 2* HOST 2 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройн бүх хөрш оройнуудтай холбно. Мөн HOST-г ч холбоно.
Дээр бичигдсэн HOST нь дандаа тухайн i тооноос бага тоо байна. Аль нэг аль хэдийн нэмэгдсэн оройнуудын нэг нь байна гэсэн үг.
Энд нэг зүйлийг тодруулахад хөрш орой гэдэг нь зөвхөн нэг ирмэгээр холбогдсон хоёр оройг хөрш орой гэнэ шүү. Илүү дэлгэрэнгүй тайлбар хэрэгтэй бол миний блогийн граф гэсэн постыг уншна уу.
Даалгавар: Үүссэн графаас аль ч хоёр орой нь хоорондоо хөрш биш байхаар оройн олонлог сонгож авая. Уг олононлогийнхаа нийт оройн жингүүдийн нийлбэрийг S гэе. S-н хамгийн их утгыг ол.
Дэд бодлогуудын оролтын өгөгдлийн хязгаарлалтууд:
Дэд бодлого 1: Нийт онооны 11%. 2<=N<=10. 1<=Оройн жингүүдийн утга<=10^6. Бүх 3-н дүрэм ашиглагдна.
Дэд бодлого 2: Нийт онооны 8%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 1 ашиглагдна.
Дэд бодлого 3: Нийт онооны 8%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 2 ашиглагдна.
Дэд бодлого 4: Нийт онооны 19%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 0 ашиглагдна.
Дэд бодлого 5: Нийт онооны 23%. 2<=N<=1,000. Оройн жингүүдийн утга=1. Дүрэм 0 болон 1 ашиглагдна.
Дэд бодлого 6: Нийт онооны 31%. 2<=N<=100,000. 1<=Оройн жингүүдийн утга<=10,000. Бүх дүрэм ашиглагдна.
Оролтын файлын формат:
Эхний мөрөнд N гэсэн ганц тоо
2 дахь мөрөнд N ширхэг тоо байх ба тухайн i дахь тоо нь i (0 <= i < N)дугаартай оройн жин байна.
3 дахь мөрөнд N-1 шихрэг хоёр хос тоо байх ба энэ нь графаа байгуулах алхам бүр юм. i дахь хос тоо нь "HOST A" гэсэн форматтай байна. Энд HOST нь дээр дурьдагдсан HOST, A гэсэн тоо нь дүрмийн дугаар байна.
Гаралтын файлын формат:
Бодлогын хариу болох ганц тоо л байна.
Жишээ оролт:
Жишээ оролтын гаралт:
35
Анализ:
Дэд бодлого 1:
Бүх дүрэм орох тул үүсэж болох граф юу ч байж болно.
N=10 учраас оройн бүх боломжит дэд олонлогуудыг гаргаж байгаад тухайн дэд олонлог бүрт орж байгаа оройнуудын жингийн нийлбэрүүдээс хамгийн ихийг нь авна гэсэн үг. Битмаск ашиглаад бүх дэд олонлогуудыг гаргана. Битмаскын талаар энд дарж уншина уу. Бүх дэд олонлогыг үүсгэхэд O(2^N) хугацаа мөн тухайн дэд олонлогийн дурын хоёр орой нь хөрш биш гэж шалгахад O(N*N) бодолт хийнэ. Нийтдээ бодолтын үнэлгээ O(N^2 * 2^N). Даалгавар, уг бодолтыг сайжруулж O(N*2^N) болгоно уу.
Аль болох ойлгомжтой бичих үүднээс соорс кодыг с дээр бичлээ.
source
Дэд бодлого 2:
Зөвхөн дүрэм 1 тул үүсэх графд ямар ч ирмэг байхгүй, дан тус тусдаа орой гэсэн үг. Бодолт хамгийн амархан, бүх оройн жингийн нийлбэр гэсэн үг. O(N).
source
Дэд бодого 3:
Зөвхөн дүрэм 2 гэхээр үүсэх граф бүтэн граф гэсэн үг. Өөрөөр хэлбэл дурын 2 орой хөрш гэсэн үг. Тэгэхээр зүгээр л бүх орон жингийн хамгийн их утга хариу болно. O(N).
source
Дэд бодлого 4:
Зөвхөн дүрэм 0 гэхээр үүсэж граф мод байна гэсэн үг. Модны dp болж хувирлаа.
Модоо 0 дугаартай оройноос нь барьж байгаад өлгөчихсөн гэж үзье. Үүнийг rooted tree гэдэг. Ерөнхий санаа бол i оройгоос өлгөгдсөн дэд модны хувьд бодлогын хариуг олоод явна гэсэн үг. Нэг тооцох ёстой зүйл бол тухайн i оройн жинг тооцоондоо оруулах эсэх. dp(i, 0), dp(i, 1) гэсэн 2 функц байг.
1 үед тухайн i оройн жинг оруулсан.
0 үед тухайн i оройн жинг оруулаагүй.
dp(i, 0) = sum(max(dp(k, 0), dp(k, 1))), k = i оройн бүх хөрш хүү оройнууд
dp(i, 1) = sum(dp(k, 0))+jin(i). k = мөн i оройн бүх хөрш хүү оройнууд
Бодлогын хариу тэгвэл max(dp(i, 0), dp(i, 1)) байна.
source
За энэ хүрээт түр өндөрлөхгүй бол миний шалгалтандаа бэлдэх өнгөрлөө. Тун ойрын хугацаанд, хагас сайнаас өмнө ч юмуу Part II-г оруулна аа. Амжилт
Ямар бодлого сонгож авах вэ гэж бодож байгаад 14 оны Friend гэж бодлогыг сонголоо. Бодлогын өгүүлбэрийг нь илүү дутуу зүйлүүдийг хасаж орчууллаа. Граф юмшиг харагдаж байгаа ч дэд бодлого гэж яагаад оруулаад байгаан мөн чанар, яагаад сүүлийн жилүүдэд уг тэмцээн маань илүү шударга олимпиад болоод байгааг харуулахыг хичээлээ. Товчхондоо бол бодлогын өгүүлбэрийг уншаад аан энэ граф байна гээд дүгнэж болно. Бүтэн бодолт маань мэдээж бүх тохиолдлыг давах ёстой. Бүх тохиолдол гэж ярьж байгаа маань тохиолдлуудыг дотор нь дахиад ангилчиж болохыг харж байгаа байх. Хүүхэд хичээж хичээж маш их цаг хугацаа, бэлтгэл зарцуулж энэ тэмцээнд орж байгаа, тодорхой түвшинд уг бодлогыг бодож чадах хэмжээнд байгаа, бүх тохиолдлыг биш ч хэд хэдэн тохиолдолд нь бодолт хийх хэмжээний хүүхдүүд байгаа. Энэ хүүхдүүдийг үнэлэх ёстой гэдэг нь хамгийн чухал зүйл юм. Жишээ нь энэ Friend гээд бодлого графын бодлого мөн нь мөн. Гэхдээ эхний 3-н дэд бодлого нь энгийн цикл, 4 дэх бодолт нь динамик програмчлал, 5 дахь бодлого онол жаахан шаардсан, 6 буюу бүтэн бодолт шаардах дэд бодлого бол сэтгэх, сэтгэлгээ туршлага шаардсан.
Энэ бодлого бол 2014 оны хоёр дахь хамгийн хүнд бодлого. Гэхдээ эхний 4н дэд бодлого нь ямар амархан болохыг хараарай.
Дэд бодлого бүрийг спож дээрх өөрийн хуудсанд тухайн таарсан тесттэй нь хамт оруулж бэлдлээ. Өөрсдийн бодолтоо шалгаарай. Бүгд албан ёсны бэлтгэгдсэн тестүүд байгаа шүү, минийх биш.
Дэд бодлого 4
Дэд бодлого 5 Үүсэх граф нь bipartite буюу дурын хоёр орой нь ялгаатай өнгөөр будахад хоёрхон өнгө хангалттай байх граф байгаа.
N оройтой (оройг 0..N-1 дугаарласан) чиглэлгүй мөн орой болгон нь эерэг тоон жинтэй граф өгөгдсөн. Графаа байгуулахдаа N алхамаар байгуулна, алхамуудаа мөн 0-ээс эхлэж дугаарлана. Хамгийн эхлээд буюу алхам 0-т граф зөвхөн 0 (оройн дугаар шүү!) гэсэн оройг нэмнэ. Дараачын алхам i (1 < i < N) бүрт доорх 3-н дүрмүүдийн нэг нь байна:
Дүрэм 0* HOST 0 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройтой холбоно.
Дүрэм 1* HOST 1 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройн бүх хөрш оройнуудтай холбно. Гэхдээ HOST-той холбохгүй.
Дүрэм 2* HOST 2 - гэсэн хоёр тоо байвал тухайн i оройг HOST дугаартай оройн бүх хөрш оройнуудтай холбно. Мөн HOST-г ч холбоно.
Дээр бичигдсэн HOST нь дандаа тухайн i тооноос бага тоо байна. Аль нэг аль хэдийн нэмэгдсэн оройнуудын нэг нь байна гэсэн үг.
Энд нэг зүйлийг тодруулахад хөрш орой гэдэг нь зөвхөн нэг ирмэгээр холбогдсон хоёр оройг хөрш орой гэнэ шүү. Илүү дэлгэрэнгүй тайлбар хэрэгтэй бол миний блогийн граф гэсэн постыг уншна уу.
Даалгавар: Үүссэн графаас аль ч хоёр орой нь хоорондоо хөрш биш байхаар оройн олонлог сонгож авая. Уг олононлогийнхаа нийт оройн жингүүдийн нийлбэрийг S гэе. S-н хамгийн их утгыг ол.
Дэд бодлогуудын оролтын өгөгдлийн хязгаарлалтууд:
Дэд бодлого 1: Нийт онооны 11%. 2<=N<=10. 1<=Оройн жингүүдийн утга<=10^6. Бүх 3-н дүрэм ашиглагдна.
Дэд бодлого 2: Нийт онооны 8%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 1 ашиглагдна.
Дэд бодлого 3: Нийт онооны 8%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 2 ашиглагдна.
Дэд бодлого 4: Нийт онооны 19%. 2<=N<=1,000. 1<=Оройн жингүүдийн утга<=10^6. Зөвхөн дүрэм 0 ашиглагдна.
Дэд бодлого 5: Нийт онооны 23%. 2<=N<=1,000. Оройн жингүүдийн утга=1. Дүрэм 0 болон 1 ашиглагдна.
Дэд бодлого 6: Нийт онооны 31%. 2<=N<=100,000. 1<=Оройн жингүүдийн утга<=10,000. Бүх дүрэм ашиглагдна.
Оролтын файлын формат:
Эхний мөрөнд N гэсэн ганц тоо
2 дахь мөрөнд N ширхэг тоо байх ба тухайн i дахь тоо нь i (0 <= i < N)дугаартай оройн жин байна.
3 дахь мөрөнд N-1 шихрэг хоёр хос тоо байх ба энэ нь графаа байгуулах алхам бүр юм. i дахь хос тоо нь "HOST A" гэсэн форматтай байна. Энд HOST нь дээр дурьдагдсан HOST, A гэсэн тоо нь дүрмийн дугаар байна.
Гаралтын файлын формат:
Бодлогын хариу болох ганц тоо л байна.
Жишээ оролт:
6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0
Жишээ оролтын гаралт:
35
Анализ:
Дэд бодлого 1:
Бүх дүрэм орох тул үүсэж болох граф юу ч байж болно.
N=10 учраас оройн бүх боломжит дэд олонлогуудыг гаргаж байгаад тухайн дэд олонлог бүрт орж байгаа оройнуудын жингийн нийлбэрүүдээс хамгийн ихийг нь авна гэсэн үг. Битмаск ашиглаад бүх дэд олонлогуудыг гаргана. Битмаскын талаар энд дарж уншина уу. Бүх дэд олонлогыг үүсгэхэд O(2^N) хугацаа мөн тухайн дэд олонлогийн дурын хоёр орой нь хөрш биш гэж шалгахад O(N*N) бодолт хийнэ. Нийтдээ бодолтын үнэлгээ O(N^2 * 2^N). Даалгавар, уг бодолтыг сайжруулж O(N*2^N) болгоно уу.
Аль болох ойлгомжтой бичих үүднээс соорс кодыг с дээр бичлээ.
source
Дэд бодлого 2:
Зөвхөн дүрэм 1 тул үүсэх графд ямар ч ирмэг байхгүй, дан тус тусдаа орой гэсэн үг. Бодолт хамгийн амархан, бүх оройн жингийн нийлбэр гэсэн үг. O(N).
source
Дэд бодого 3:
Зөвхөн дүрэм 2 гэхээр үүсэх граф бүтэн граф гэсэн үг. Өөрөөр хэлбэл дурын 2 орой хөрш гэсэн үг. Тэгэхээр зүгээр л бүх орон жингийн хамгийн их утга хариу болно. O(N).
source
Дэд бодлого 4:
Зөвхөн дүрэм 0 гэхээр үүсэж граф мод байна гэсэн үг. Модны dp болж хувирлаа.
Модоо 0 дугаартай оройноос нь барьж байгаад өлгөчихсөн гэж үзье. Үүнийг rooted tree гэдэг. Ерөнхий санаа бол i оройгоос өлгөгдсөн дэд модны хувьд бодлогын хариуг олоод явна гэсэн үг. Нэг тооцох ёстой зүйл бол тухайн i оройн жинг тооцоондоо оруулах эсэх. dp(i, 0), dp(i, 1) гэсэн 2 функц байг.
1 үед тухайн i оройн жинг оруулсан.
0 үед тухайн i оройн жинг оруулаагүй.
dp(i, 0) = sum(max(dp(k, 0), dp(k, 1))), k = i оройн бүх хөрш хүү оройнууд
dp(i, 1) = sum(dp(k, 0))+jin(i). k = мөн i оройн бүх хөрш хүү оройнууд
Бодлогын хариу тэгвэл max(dp(i, 0), dp(i, 1)) байна.
source
За энэ хүрээт түр өндөрлөхгүй бол миний шалгалтандаа бэлдэх өнгөрлөө. Тун ойрын хугацаанд, хагас сайнаас өмнө ч юмуу Part II-г оруулна аа. Амжилт
Saturday, April 30, 2016
Мэдээлэл зүйн улсын олимпиад, сурагчидын 2 дугаар өдрийн бодлогын бодолтууд
Бүх оролцогчидод баяр хүргье. Мундаг байсан шүү та нар.
Өөрийн бодолтоо анализын хамт сонирхуулая:
1-р бодлого:
Өгүүлбэр: Утгаараа мянгаас хэтрэхгүй N (N<=10^6) ширхэг тоон дараалал өгөгдсөн. Q (Q<=10^1) ширхэг хүсэлтэнд хариулах ба энэ нь дээрх дарааллын A, B индэкс завсарт байрлаж байгаа тоонууд дунд хамгийн их давтагдсан, хамгийн бага давтагдсан мөн нийт хичнээн ялгаатай тоо байгааг олох юм байна. Жишээнээс тодорхой форматыг нь харна уу
input:
10
5 5 5 5 6 4 1 2 20
3
mn 1 10
mx 1 10
ct 1 10
output:
1
5
7
Анализ:
Миний хувьд энэ бол хоёр дахь өдрийн хамгийн хүнд бодлого. Гэхдээ, нийт хүсэлтийн тоо хамгийн ихдээ 10, утгаараа тоонууд нь мянгаас бага гэхээр хүсэлт болгонд A-аас B дунд гүйгээд тоолчиж болно. Тоолохдоо a[1000] урттай массив авж байгаад i гэсэн тоо орж ирвэл a[i]++ нэмээд байна гэсэн үг. Хүсэлт болгонд A=1, B=10^6 байж болох тул O(N)-д хариулна. Нийт бодолтын үнэлгээ O(Q*N) буюу 10-н сая үйлдэл хангалттай 0.3 секундэд амжиж байгаа юмшиг байна.
O(M*Q*logN) бодолт сонирхоё, мөн бичихэд маш хурдан нь.
1...M ширхэг массив авая. Тухайн k дугаар дахь массив бүрт уг к тоо маань хэд хэд гэсэн индекст байрлаж байгааг нь хадгалчия. Яг орж ирсэн дарааллаар нь массивын араас нь элементээ нэмээд явахад эрэмблэгдсэн массив үүснэ. Тэгвэл одоо хүсэлт A B орж ирэхэд бүх массив дотор хоёртын хайлт хийнэ. Ойлгомжтой болгохын үүднээс зөвхөн макс-г нь олоё. lower_bound(left, right, k) функц нь к дахь массивт (left, right) завсарт багтах тоонуудын хамгийн багых нь дугаарыг олно.
upper_bound(left, right, k) нь уг завсарт багтах тоонуудаас хамгийн ихийх нь дугаарыг олно.
Одоо ингээд dif = upper_bound(left, right, k)-lower_bound(left, right, k) - г бүх k-н хувьд минимумчилна гэсэн үг.
source - хоёртын хайлтыг чөлөөтэй бичдэг байх хэрэгтэй шүү!
Бодлого 2:
Өгүүлбэр: дараах байдлаар нийлбэрийг задласан юм байна. Аль нэгэн нийлбэр нь өгөгдөхөд доорх нийлбэрийг нь ол.
Анализ: нийлбэр үүсгэж байгаа гишүүдийг нь эхнээс нь массивт хийцэн гэж үзье. Зөрөө нь хоёроос их байх хамгийн эхний дараалсан хоёр гишүүний олъё k, k+1 гэе. Уг хоёр гишүүн хүртлэх гишүүдийн нийлбэрийг мэднэ гэж үзье. Одоо к дахь гишүүнээ нэгээр нэмэгдүүлээд уг хоёр гишүүн хүртлэх гишүүдийн нийлбэрийг бүх гишүүдийн нийлбэрээс хасая diff гэе. Одоо бид diff-г аль болох урт мөн хамгийн эхний гишүүн нь k дахь гишүүнтэй тэнцүү байхаар задлана гэсэн үг. Бодолтоос дэлгэрэнгүй харна уу.
Бодлого 3:
Зөвхөн N ширхэг 1 байхад хэд гэсэн тоог гаргаж авч чадах вэ? N*(N-1)/2
Зөвхөн M ширхэг -1 байхад хэд гэсэн тоог гаргаж авч чадав вэ? M*(M-1)/2
Одоо тэгвэл N ширхэг 1 мөн M ширхэг -1 байхад хэд гэсэн тоог гаргаж авч чадах вэ?
N*(N-1)/2 + M*(M-1)/2 - N*M.
S өгөгдөхөд S=N*(N-1)/2 + M*(M-1)/2 - N*M байх M-г ол гэсэн бодлого. N, S-г мэдэж байгаа тул квадрат тэгшитгэл бодоод M-г олно. Гарсан хоёр язгуурын аль нь манай хариу болж болох бол? бодоод үзээрэй.
source
За нэг иймэрхүү. Надад эхний өдрийн бодлогууд олдвол ингээд анализ хийчиж болох л байх.
Sunday, April 24, 2016
Зөвлөгөө
Хүнд бодлого бодохын ач тус байхгүй
Хорвоо дэлхийн бүх бодлогуудыг түвшингээр нь 1, 2, ..., N гээд дугаарлая (N мэдээж төгсгөлгүй жижиг тоо, өө бишээ том тоо, гэхдээ тэр төгсгөлгүй том тоо чинь төгсгөлгүй том тоон ширхэг төгсгөлгүй том тооны хажууд төгсгөлгүй жижиг тооштэй? парадоксуу эсвэл харьцангуйн онол уу? за тэр яахав). Дугаар нь том тусмаа хүнд бодлого гэж үзье. Би өмнөх постын төгсөлд бичсэнчлэн ямар нэгэн бодлогонд 24-н цаг зарцуулаагүй л бол хүнд гэж бууж өгөх хэрэг байхгүй.
-xx-: 24-н цагийн дараа бодож чадсангүй, яах уу дурак аа?
-Baska-: kk цагаа л дэмий үрлээдээ хө.
-xx-: ямар хогийн хариулт вэ?
Манай 10-н жилийхэн, оюутнууд өөрсдөө нэгэнт хүнд бодлого барьж аваад байдаг болохоор би аргаа бараад ингэж зөвлөсөн юм. Яс юман дээрээ тэр 24-н цагтаа эргэлзээтэй сэдвүүдээ бататгаад эсвэл амархан санагдах бодлогуудаа бодсон бол тэр хүнд бодлого бодох хугацаагаа арай наашлуулах л байсан байх. Ер нь бол бүх зүйл явж явж рефлэкс байдаг шиг санагдаад байгаа, бодит амьдрал дээр ч тэр. Хэн асар их тооны бодлого бодно тэр хүн хурдтай сэтгэж хурдан бодно. Олимпиадын үеэр шинэ юм сурна гэж байхгүй, юу чаддагаа л хийдэг газар, чаддаг зүйлээ хэдэн мянга давтаж байж өөрийн болгож авна ингэж байж тэрийгээ хэрэгтэй газар нь хийж чадна.
-xx-: Олимпиадад хэн түрүүлж чаддаггүй вэ?
-: бодлогыг амархан гэж орхисон нөхдүүд л цагаа тулахаар чадах юмаа хийж чадаагүйд л байдагштээ.
-xx: Маш энгийн юмыг мартчихсан байдаг штээ? энэ нь би муу гэсэн үг биш :(
-x: чи энгийн юмыг энгийн гэж бодоод хаясан л байхгүй юу.
-xx-: Тэгээд дандаа амархан бодлого бодох ёстой юмуу?
--: Мэдээж чи ном уншдаг болчоод үсэг цээжлэх дасгал хийнэ гэж байхгүй. Амархан бодлого бодох ёстой гэдэг нь К түвшний бодлого бодчоод K+1 түвшнийхийг л бодох хэрэгтэй.
-xx-: Яаж дараагийн түвшний бодлогыг олох вэ? надад багш байхгүй, би ганцаараа..
Энэ ганцаараа гэдэг зүйл яг манайд их түгээмэл ярьдаг шалтгаан. Манайд гэдэг нь мэдээлэл зүй, програмчлалд шүү.
Одоо гэхдээ нэг таатай зүйл нь бодлогын маш олон онлайн сайтууд байна. Бүгд тухайн ямар нэгэн бодлогыг хэдэн хүн бодсон, хэдэн хүн оролдоод хэд нь бодсон гээт статистикууд байгаа. Эдгээрийг нь харж байгаад хамгийн их хүн бодсоноор нь эрэмблээд бодвол арай цэгцтэй цаг хэмнээд маргааш гэхэд нэгнээсээ түрүүлж алхах л байх шүү.
Хүнд гээд байгаа бодлого чинь чиний тууштай, тэвчээртэй өнгрүүлсэн урт биш хугацааны дараа амархан бодлого болох байхгүй юу, гол санаа маань энэ.
10-н жилийхэн надаас бодлого их асууж холбогдож байгаа. Сайн байна, юм хийх гээд л байна гэсэн үг. Гэхдээ бүгдэнд нь нэг дутагдал байна. Дандаа маш хүнд бодлого барьчихсан байдаг. Би зааж өгөөд бодолтыг нь хэлсэн ч бай эндээс үлдэх юм юу л бол. Улсын олимпиадад орох гэж байгаа бол заавал улсын олимпиадын бодлого бодоод байх хэрэг байхгүй. Тэднарыг чаддаг ч байх албагүй. Гол нь чи мэдэх юмаа баталгаатай чаддаг л байх хэрэгтэй.
Нэмээд хэлэхэд өөрийн мэдэх зүйлээ хангалттай чаддаг болчоод тэмцээнд орвол ядаж халтар хултар ганц хоёр хүнд сэдэвтэй бодлого бодсон лаг нөхдүүдийн дээр гарах магадлал их шүү.
Гэхдээ ичиж санаа зовох зүйлгүй аль болох нээлттэй сайн юм асууцгаагаарай.
За амжилт хүсье.
(Зөвхөн олимпиад тэмцээн, алгоритмд дуртай хүмүүст зориулж энэ постыг бичлээ. Битгий тэгээд тэмцээн уралдаан нэг нэгнийхээ дээр гарах ямар хэрэгтэйн гээд нэгнээ шүүмжлээд байгаарай. Энэ бол шал өөр сэдэв болно)
Хорвоо дэлхийн бүх бодлогуудыг түвшингээр нь 1, 2, ..., N гээд дугаарлая (N мэдээж төгсгөлгүй жижиг тоо, өө бишээ том тоо, гэхдээ тэр төгсгөлгүй том тоо чинь төгсгөлгүй том тоон ширхэг төгсгөлгүй том тооны хажууд төгсгөлгүй жижиг тооштэй? парадоксуу эсвэл харьцангуйн онол уу? за тэр яахав). Дугаар нь том тусмаа хүнд бодлого гэж үзье. Би өмнөх постын төгсөлд бичсэнчлэн ямар нэгэн бодлогонд 24-н цаг зарцуулаагүй л бол хүнд гэж бууж өгөх хэрэг байхгүй.
-xx-: 24-н цагийн дараа бодож чадсангүй, яах уу дурак аа?
-Baska-: kk цагаа л дэмий үрлээдээ хө.
-xx-: ямар хогийн хариулт вэ?
Манай 10-н жилийхэн, оюутнууд өөрсдөө нэгэнт хүнд бодлого барьж аваад байдаг болохоор би аргаа бараад ингэж зөвлөсөн юм. Яс юман дээрээ тэр 24-н цагтаа эргэлзээтэй сэдвүүдээ бататгаад эсвэл амархан санагдах бодлогуудаа бодсон бол тэр хүнд бодлого бодох хугацаагаа арай наашлуулах л байсан байх. Ер нь бол бүх зүйл явж явж рефлэкс байдаг шиг санагдаад байгаа, бодит амьдрал дээр ч тэр. Хэн асар их тооны бодлого бодно тэр хүн хурдтай сэтгэж хурдан бодно. Олимпиадын үеэр шинэ юм сурна гэж байхгүй, юу чаддагаа л хийдэг газар, чаддаг зүйлээ хэдэн мянга давтаж байж өөрийн болгож авна ингэж байж тэрийгээ хэрэгтэй газар нь хийж чадна.
-xx-: Олимпиадад хэн түрүүлж чаддаггүй вэ?
-: бодлогыг амархан гэж орхисон нөхдүүд л цагаа тулахаар чадах юмаа хийж чадаагүйд л байдагштээ.
-xx: Маш энгийн юмыг мартчихсан байдаг штээ? энэ нь би муу гэсэн үг биш :(
-x: чи энгийн юмыг энгийн гэж бодоод хаясан л байхгүй юу.
-xx-: Тэгээд дандаа амархан бодлого бодох ёстой юмуу?
--: Мэдээж чи ном уншдаг болчоод үсэг цээжлэх дасгал хийнэ гэж байхгүй. Амархан бодлого бодох ёстой гэдэг нь К түвшний бодлого бодчоод K+1 түвшнийхийг л бодох хэрэгтэй.
-xx-: Яаж дараагийн түвшний бодлогыг олох вэ? надад багш байхгүй, би ганцаараа..
Энэ ганцаараа гэдэг зүйл яг манайд их түгээмэл ярьдаг шалтгаан. Манайд гэдэг нь мэдээлэл зүй, програмчлалд шүү.
Одоо гэхдээ нэг таатай зүйл нь бодлогын маш олон онлайн сайтууд байна. Бүгд тухайн ямар нэгэн бодлогыг хэдэн хүн бодсон, хэдэн хүн оролдоод хэд нь бодсон гээт статистикууд байгаа. Эдгээрийг нь харж байгаад хамгийн их хүн бодсоноор нь эрэмблээд бодвол арай цэгцтэй цаг хэмнээд маргааш гэхэд нэгнээсээ түрүүлж алхах л байх шүү.
Хүнд гээд байгаа бодлого чинь чиний тууштай, тэвчээртэй өнгрүүлсэн урт биш хугацааны дараа амархан бодлого болох байхгүй юу, гол санаа маань энэ.
10-н жилийхэн надаас бодлого их асууж холбогдож байгаа. Сайн байна, юм хийх гээд л байна гэсэн үг. Гэхдээ бүгдэнд нь нэг дутагдал байна. Дандаа маш хүнд бодлого барьчихсан байдаг. Би зааж өгөөд бодолтыг нь хэлсэн ч бай эндээс үлдэх юм юу л бол. Улсын олимпиадад орох гэж байгаа бол заавал улсын олимпиадын бодлого бодоод байх хэрэг байхгүй. Тэднарыг чаддаг ч байх албагүй. Гол нь чи мэдэх юмаа баталгаатай чаддаг л байх хэрэгтэй.
Нэмээд хэлэхэд өөрийн мэдэх зүйлээ хангалттай чаддаг болчоод тэмцээнд орвол ядаж халтар хултар ганц хоёр хүнд сэдэвтэй бодлого бодсон лаг нөхдүүдийн дээр гарах магадлал их шүү.
Гэхдээ ичиж санаа зовох зүйлгүй аль болох нээлттэй сайн юм асууцгаагаарай.
За амжилт хүсье.
(Зөвхөн олимпиад тэмцээн, алгоритмд дуртай хүмүүст зориулж энэ постыг бичлээ. Битгий тэгээд тэмцээн уралдаан нэг нэгнийхээ дээр гарах ямар хэрэгтэйн гээд нэгнээ шүүмжлээд байгаарай. Энэ бол шал өөр сэдэв болно)
Тэмцээн 2016 бодолтууд
За тэмцээнд оролцсон бүх оролцогчиддоо их баярлалаа. Сайн байсан шүү та нар бүгдээрэй.
Шууд анализдаа ороё. Мөн C++ код тавьлаа. Аль болох ойлгож мөн хэлнийхээ мэдлэгийг сайжруулах үүднээс ямар асуудлыг яаж шийдэж гэдэг байдлаар код уншаарай. Амжилт
Bodlogo 1
Байж болон хамгийн том тоо 10^9 - г хоёртын тоололруу шилжүүлэхэд 30-н оронтой тоо гарна. Гуравтын тоололд шилжүүлэхэд мөн хамаагүй бага оронтой тоо гарна. Бүх боломжийг шалгахад O(2*30*30) аас ихгүй үйлдэл хийнэ, энэ хугацаандаа хангалттай амжих бодолт. Гол асуудал нь дурын тоо өгөгдөхөд хоёртуу мөн гуравтын тоололруу шилжүүлдэг байх хэрэгтэй.
source
Bodlogo 2
Энэ бас л шууд хэлснийг нь хийхэд болох бодлого. A олонлогоо шууд эрэмблэе. Одоо M тоон дарааллын C урттай дараалалсан гишүүд болгоныг тусад нь эрэмбэлээд A олонлогийн харгалзах дугаартай элементүүдийн зөрүү бүгд тэнцүү байх ёстой. Бодолтын хугацаа O(10*N) = O(N).
source
Bodlogo 3
Рекурс ашиглаад хоёр арлаа 0, 1-ээр ялгаад будчиж чадна. Үүсэх графын хязгаарлалт бага тул шууд бүх хоё 0 1-үүдийн хоорондох зайг олоод хамгийн багыг авчихад болно.
source
Bodlogo 4
Бас л шууд хэлснээр нь хийгээд шалгачина. Нэг асуудал нь тухайн толь дээр хаанаас нь ирснийг мөн ямар толь байвал хаашаа явахыг нь яаж мэдэх вэ? тухайн ямар нэгэн x гэсэн нүдний хувьд чиглэлүүдийг нь дараах байдлаар тодорхойлоё.
2
3x1
0
Одоо bounce1[i]=k-аар '/' ингэж тавьсан толинд i чиглэлээс ирэхэд к чиглэлрүү явна гэдэгийг нь тэмдэглэе. Мөн bounce2[i]=k-аар '\' толинд i чиглэлээс ирэхэд к чиглэлрүү явахыг тэмдэглэе.
Мөн xx[]={1, 0, -1, 0}, yy[]={0, 1, 0, -1} энэ хоёр массивыг ашиглаад x+xx[k], y+yy[k] гэсэн k чиглэлрүү очиж чадна.
source
Bodlogo 5
dictionary дахь үгнүүдийг өөрийх нь байрлалтай нь хамт хадгалаад үгнүүдийх нь хувьд эрэмбэлэе. prefix үг орсон байх үгний хамгийн эхнийхийг нь хоёртын хайлт хийж дугаарыг нь олоод k-г нэмэхэд гарах үгний prefix нь манай хайж байгаа prefix-тэй тэнцүү байна уу гээд шалгачина. Бодолт O(NLogN+q*LogN).
source
Bodlogo 6
Ямар нэгэн түвшинд байгаа (x, y) цэг нь дараагийн түвшиндээ (2*x, 2*y) координадтай болно
source
Bodlogo 7
Энэ бол "two pointers" гэх ангилалд орох сонгодог бодлого. start, end гэх интервал аваад явъя. Тухайн өнгийг одоогийн интервалд хэд орсныг нь мөн тоолно. Бүх өнгө ортол end=end+1 гэе. Одоо start дээр байгаа өнгийг хассан ч бүх өнгө ядаж нэг орсон байвал start=start+1 гээд байя. Одоо end-start манай хариу байж магадгүй тул өмнө олсон хариунаас их бага эсэхийг шалгаад болоо.
source
Дараагийн маш сонирхолтой бодолт бол өнгө болгоны хувьд хамгийн сүүлд олдсон байрлалыг нь хадгалаад явна, A-д хадгалав. Өнгө бүрийн хувьд хамгийн анхны утга нь -INF байг. Одоо бөмбөлөг байгаа цэг бүрийн хувьд эхнээс нь гүйх ба (х цэг) тухайн өнгөний байрлалыг нь шинэчилчээд үүний дараа A-н хамгийн бага утгыг олоод min гэе. x-min манай бодлогын хариу байж магадгүй. Тэгэхээр энэ бодолтын хувьд A-г шинэчлэх мөн хамгийн бага утгыг хангалттай хурдан олж чадвал, heap, O(NLogN)-д бодогдно.
source
Гэвч дээрх хоёр бодолт хоюулаа хамгийн эхний үйлдэл нь цэгүүдээ эрэмбэлэх тул O(NlogN)-г би дурьдсангүй шүү
Bodlogo 8
Энэ бодлогын хариуг бид олохын тулд хоёр зүйлийг минимумчлал ёстой.
1: Аль ч аралд харьяалагдахгүй бүх цэгийн 3-н арал хүртлэх зайнаас хамгийн багыг нь олоё. Үүнийг 3*2500-д олж чадна. Үүнийгээ m1 гэе
2: 1-р арлаас 2-р арал хүртлэх хамгийн богино зайг (1, 2), 2-оос 3-г (2, 3), 1-ээс 3-г (1, 3) гэе. Энэ 3-н аль нэг хоёрын нийлбэр нь мөн манай хариу болж магадгүй, үүнийг m2 гэе. 2500^2-д олж чадна
Бодлогын хариу min(m2, m1).
source
Bodlogo 9
Энэ бол dp. Best[i][j]-ээр i гэсэн тоог 1..j хүртлэх гишүүдийг ашиглан зардал хамгийн бага байлгахыг тэмдэглэе. Тэгвэл Best[i][j] = min(k-A[k])^2+Best[i-k*k][j-1], (1..k k*k<=i)
source
Bodlogo 10
Энэ бодлогыг та бүхнийг өөрсдөө дахин сайн нухаж бодохыг хүсэж байна. Ер нь ямар нэгэн бодлого дээр 24-н цаг суугаагүй л бол хэцүү бодлого гэж хэлэхгүй шүү
За асуух юм байвал комментоор асууж бариараа. Амжилт хүсье.
Шууд анализдаа ороё. Мөн C++ код тавьлаа. Аль болох ойлгож мөн хэлнийхээ мэдлэгийг сайжруулах үүднээс ямар асуудлыг яаж шийдэж гэдэг байдлаар код уншаарай. Амжилт
Bodlogo 1
Байж болон хамгийн том тоо 10^9 - г хоёртын тоололруу шилжүүлэхэд 30-н оронтой тоо гарна. Гуравтын тоололд шилжүүлэхэд мөн хамаагүй бага оронтой тоо гарна. Бүх боломжийг шалгахад O(2*30*30) аас ихгүй үйлдэл хийнэ, энэ хугацаандаа хангалттай амжих бодолт. Гол асуудал нь дурын тоо өгөгдөхөд хоёртуу мөн гуравтын тоололруу шилжүүлдэг байх хэрэгтэй.
source
Bodlogo 2
Энэ бас л шууд хэлснийг нь хийхэд болох бодлого. A олонлогоо шууд эрэмблэе. Одоо M тоон дарааллын C урттай дараалалсан гишүүд болгоныг тусад нь эрэмбэлээд A олонлогийн харгалзах дугаартай элементүүдийн зөрүү бүгд тэнцүү байх ёстой. Бодолтын хугацаа O(10*N) = O(N).
source
Bodlogo 3
Рекурс ашиглаад хоёр арлаа 0, 1-ээр ялгаад будчиж чадна. Үүсэх графын хязгаарлалт бага тул шууд бүх хоё 0 1-үүдийн хоорондох зайг олоод хамгийн багыг авчихад болно.
source
Bodlogo 4
Бас л шууд хэлснээр нь хийгээд шалгачина. Нэг асуудал нь тухайн толь дээр хаанаас нь ирснийг мөн ямар толь байвал хаашаа явахыг нь яаж мэдэх вэ? тухайн ямар нэгэн x гэсэн нүдний хувьд чиглэлүүдийг нь дараах байдлаар тодорхойлоё.
2
3x1
0
Одоо bounce1[i]=k-аар '/' ингэж тавьсан толинд i чиглэлээс ирэхэд к чиглэлрүү явна гэдэгийг нь тэмдэглэе. Мөн bounce2[i]=k-аар '\' толинд i чиглэлээс ирэхэд к чиглэлрүү явахыг тэмдэглэе.
Мөн xx[]={1, 0, -1, 0}, yy[]={0, 1, 0, -1} энэ хоёр массивыг ашиглаад x+xx[k], y+yy[k] гэсэн k чиглэлрүү очиж чадна.
source
Bodlogo 5
dictionary дахь үгнүүдийг өөрийх нь байрлалтай нь хамт хадгалаад үгнүүдийх нь хувьд эрэмбэлэе. prefix үг орсон байх үгний хамгийн эхнийхийг нь хоёртын хайлт хийж дугаарыг нь олоод k-г нэмэхэд гарах үгний prefix нь манай хайж байгаа prefix-тэй тэнцүү байна уу гээд шалгачина. Бодолт O(NLogN+q*LogN).
source
Bodlogo 6
Ямар нэгэн түвшинд байгаа (x, y) цэг нь дараагийн түвшиндээ (2*x, 2*y) координадтай болно
source
Bodlogo 7
Энэ бол "two pointers" гэх ангилалд орох сонгодог бодлого. start, end гэх интервал аваад явъя. Тухайн өнгийг одоогийн интервалд хэд орсныг нь мөн тоолно. Бүх өнгө ортол end=end+1 гэе. Одоо start дээр байгаа өнгийг хассан ч бүх өнгө ядаж нэг орсон байвал start=start+1 гээд байя. Одоо end-start манай хариу байж магадгүй тул өмнө олсон хариунаас их бага эсэхийг шалгаад болоо.
source
Дараагийн маш сонирхолтой бодолт бол өнгө болгоны хувьд хамгийн сүүлд олдсон байрлалыг нь хадгалаад явна, A-д хадгалав. Өнгө бүрийн хувьд хамгийн анхны утга нь -INF байг. Одоо бөмбөлөг байгаа цэг бүрийн хувьд эхнээс нь гүйх ба (х цэг) тухайн өнгөний байрлалыг нь шинэчилчээд үүний дараа A-н хамгийн бага утгыг олоод min гэе. x-min манай бодлогын хариу байж магадгүй. Тэгэхээр энэ бодолтын хувьд A-г шинэчлэх мөн хамгийн бага утгыг хангалттай хурдан олж чадвал, heap, O(NLogN)-д бодогдно.
source
Гэвч дээрх хоёр бодолт хоюулаа хамгийн эхний үйлдэл нь цэгүүдээ эрэмбэлэх тул O(NlogN)-г би дурьдсангүй шүү
Bodlogo 8
Энэ бодлогын хариуг бид олохын тулд хоёр зүйлийг минимумчлал ёстой.
1: Аль ч аралд харьяалагдахгүй бүх цэгийн 3-н арал хүртлэх зайнаас хамгийн багыг нь олоё. Үүнийг 3*2500-д олж чадна. Үүнийгээ m1 гэе
2: 1-р арлаас 2-р арал хүртлэх хамгийн богино зайг (1, 2), 2-оос 3-г (2, 3), 1-ээс 3-г (1, 3) гэе. Энэ 3-н аль нэг хоёрын нийлбэр нь мөн манай хариу болж магадгүй, үүнийг m2 гэе. 2500^2-д олж чадна
Бодлогын хариу min(m2, m1).
source
Bodlogo 9
Энэ бол dp. Best[i][j]-ээр i гэсэн тоог 1..j хүртлэх гишүүдийг ашиглан зардал хамгийн бага байлгахыг тэмдэглэе. Тэгвэл Best[i][j] = min(k-A[k])^2+Best[i-k*k][j-1], (1..k k*k<=i)
source
Bodlogo 10
Энэ бодлогыг та бүхнийг өөрсдөө дахин сайн нухаж бодохыг хүсэж байна. Ер нь ямар нэгэн бодлого дээр 24-н цаг суугаагүй л бол хэцүү бодлого гэж хэлэхгүй шүү
За асуух юм байвал комментоор асууж бариараа. Амжилт хүсье.
Tuesday, April 19, 2016
Тэмцээн 2016
UPDATE: Тэмцээн болох хаяг
https://www.hackerrank.com/mongolian-pupils
За тэгэхээр www.algorithm.mn гэсэн хаягаа авч чадсан тул тэмдэглээд тэмцээн зохиохоор шийдлээ.
Зорилго:
Удахгүй улсын олимпиад цаашлаад шалгарсан шилдэг хүүхдүүд олон улсын тэмцээнд явах тул ерөнхий хүүхдүүд, дасгалжуулагч багш нарын чадварыг харах зорилгоор энэ тэмцээнээ зохиож байна. Тэгэхээр аль болох олон хүмүүст хүргэж идэвхтэй оролцуулна уу.
Хэзээ:
Энд дарна уу. Улаанбаатарын цагаар шүү
Тэмцээнээ hackerrank дээр зохиох байх, хэдэн өдрөөс линкийг нь тавина. Бодлогуудын хувьд 10-н бодлоготой 5-н цагийн хугацаатай болно. Бодлогын түвшин нь амарханаас хүндрүү байх болно тэгэхээр хамгийн эхний бодлогууд амархан тэгээд хүндрэнэ шүү. Хамгийн хүнд бодлого нь олон улсын мэдээлэл зүйн олимпиадын хамгийн амархан бодлогын түвшинд байх тул тийм ч хүнд тэмцээн болохгүй байх. Улсын олимпиадын өмнөх сорилго гээд ойлгочихоорой.
Шагнал: эхний 5-н байрт шалгарсан монголд байдаг "хүн төрлхтөн"-д доорх подволкыг өгнө өө. Би өөрөө зунаас очиж шагналаа өгөх байх шүү.
Тэмцээний дараа тэмцээнд оролцсон 10-н жилийн хүүхдүүд өөрсдөө холбогдвол тус бүрт нь зөвлөгөө өгнө өө.
https://www.hackerrank.com/mongolian-pupils
За тэгэхээр www.algorithm.mn гэсэн хаягаа авч чадсан тул тэмдэглээд тэмцээн зохиохоор шийдлээ.
Зорилго:
Удахгүй улсын олимпиад цаашлаад шалгарсан шилдэг хүүхдүүд олон улсын тэмцээнд явах тул ерөнхий хүүхдүүд, дасгалжуулагч багш нарын чадварыг харах зорилгоор энэ тэмцээнээ зохиож байна. Тэгэхээр аль болох олон хүмүүст хүргэж идэвхтэй оролцуулна уу.
Хэзээ:
Энд дарна уу. Улаанбаатарын цагаар шүү
Тэмцээнээ hackerrank дээр зохиох байх, хэдэн өдрөөс линкийг нь тавина. Бодлогуудын хувьд 10-н бодлоготой 5-н цагийн хугацаатай болно. Бодлогын түвшин нь амарханаас хүндрүү байх болно тэгэхээр хамгийн эхний бодлогууд амархан тэгээд хүндрэнэ шүү. Хамгийн хүнд бодлого нь олон улсын мэдээлэл зүйн олимпиадын хамгийн амархан бодлогын түвшинд байх тул тийм ч хүнд тэмцээн болохгүй байх. Улсын олимпиадын өмнөх сорилго гээд ойлгочихоорой.
Шагнал: эхний 5-н байрт шалгарсан монголд байдаг "хүн төрлхтөн"-д доорх подволкыг өгнө өө. Би өөрөө зунаас очиж шагналаа өгөх байх шүү.
Тэмцээний дараа тэмцээнд оролцсон 10-н жилийн хүүхдүүд өөрсдөө холбогдвол тус бүрт нь зөвлөгөө өгнө өө.
Monday, April 4, 2016
Мат - 2
Доорх бодлогуудыг бодно уу. Энэ удаа би анализ болон код тавихгүй, дараагийн постоор тавина. Уг нь маш олон хүн постуудыг уншиж байгаа даанч баярлаж байгаа хүн, юм сурах гэж мэрийж байгаа хүн байгаа эсэхэд мэдэгдэх юм алга.
Миний постуудад бодлогууд ерөнхийдөө амарханаас хэцүүрүү эрэмблэгдэж байгаа шүү.
1799 - Бодит 1<=R<=100 болон бүхэл 2<=n<=100 хоёр тоо өгөгдсөн. R радиустай тойрог дотор зурагт харагдаж байгаа шиг n ширхэг ижил радиустай тойрог хооронд нь ямар ч зайгүй тавих гэж байгаа бол тэр тойргийн радиусын хамгийн уртыг нь ол. Оролт гаралтых нь форматыг өөрсдөө хараад ойлгочоорой.
1401 - 1<=N<=10^9 өгөгдөхөд N! сүүлийн хэдэн орон нь тэг байхыг тоолно уу.
2262 - 1<=N<=10^6 тоо өгөгдөхөд уг тоо a+b гэсэн хоёр анхны тоонд тавигдах эсэхийг ол. Тавигдах бол хоёр тоог N = a + b форматтай хэвлэнэ үгүй бол "Goldbach's conjecture is wrong." гэж хэвлэ. Хэрэв бодлого олон хариутай бол (b-a) хамгийн их байхыг нь хэвлэнэ.
2242 - 3н цэг координат нь өгөгдсөн бол уг гурван цэгийг дайрах тойргийн радиусыг ол. Координатуудын утга саяас хэтрэхгүй.
1654 - Зөвхөн 8 2 6 4 9 7 3 1 5 аас бүрдэх тэмдэгт мөр өгөгдөв. 8-хойд, 7-баруун хойд, 4-баруун , 1-баруун урд, 2-урд, 3-зүүн урд, 6-зүүн, 9-зүүн хойд тус тус илэрхийлэх ба координатын систем дээр аль нэг цэгээс эхлээд тухайн тоонд харгалзах зүгрүү нэг нэг нэгжээр хөдлөж олон өнцөгт үүсгэнэ. Үүсэх олон өнцөгтийн талбайг ол. 5 гэсэн тоо нь хөдлөж дууссныг илэрхийлнэ.
2084 - 1<=n<=100 өгөгдөхөд 1 2 .. 2n-1 2n гэх байдлаар цагийн зүүний дагуу тойрог үүсгэн бичив. Тоо бүрийг яг нэг өөр тоотой харгалзуулан шулуун татав, ингэхдээ шулуунууд хоорондоо огтлолцохгүй. Нийт хичнээн янзаар шулуун татаж болох вэ?
1426 - 1<=n<=200 өгөгдөхөд аравтын бичлэг нь зөвхөн тэг эсвэл нэгээс бүрдэх n=q*m+0 байх m-г ол. Бодлогын хариу 100 оронгоос бага байна.
За амжилт.
Миний постуудад бодлогууд ерөнхийдөө амарханаас хэцүүрүү эрэмблэгдэж байгаа шүү.
1799 - Бодит 1<=R<=100 болон бүхэл 2<=n<=100 хоёр тоо өгөгдсөн. R радиустай тойрог дотор зурагт харагдаж байгаа шиг n ширхэг ижил радиустай тойрог хооронд нь ямар ч зайгүй тавих гэж байгаа бол тэр тойргийн радиусын хамгийн уртыг нь ол. Оролт гаралтых нь форматыг өөрсдөө хараад ойлгочоорой.
1401 - 1<=N<=10^9 өгөгдөхөд N! сүүлийн хэдэн орон нь тэг байхыг тоолно уу.
2262 - 1<=N<=10^6 тоо өгөгдөхөд уг тоо a+b гэсэн хоёр анхны тоонд тавигдах эсэхийг ол. Тавигдах бол хоёр тоог N = a + b форматтай хэвлэнэ үгүй бол "Goldbach's conjecture is wrong." гэж хэвлэ. Хэрэв бодлого олон хариутай бол (b-a) хамгийн их байхыг нь хэвлэнэ.
2242 - 3н цэг координат нь өгөгдсөн бол уг гурван цэгийг дайрах тойргийн радиусыг ол. Координатуудын утга саяас хэтрэхгүй.
1654 - Зөвхөн 8 2 6 4 9 7 3 1 5 аас бүрдэх тэмдэгт мөр өгөгдөв. 8-хойд, 7-баруун хойд, 4-баруун , 1-баруун урд, 2-урд, 3-зүүн урд, 6-зүүн, 9-зүүн хойд тус тус илэрхийлэх ба координатын систем дээр аль нэг цэгээс эхлээд тухайн тоонд харгалзах зүгрүү нэг нэг нэгжээр хөдлөж олон өнцөгт үүсгэнэ. Үүсэх олон өнцөгтийн талбайг ол. 5 гэсэн тоо нь хөдлөж дууссныг илэрхийлнэ.
2084 - 1<=n<=100 өгөгдөхөд 1 2 .. 2n-1 2n гэх байдлаар цагийн зүүний дагуу тойрог үүсгэн бичив. Тоо бүрийг яг нэг өөр тоотой харгалзуулан шулуун татав, ингэхдээ шулуунууд хоорондоо огтлолцохгүй. Нийт хичнээн янзаар шулуун татаж болох вэ?
1426 - 1<=n<=200 өгөгдөхөд аравтын бичлэг нь зөвхөн тэг эсвэл нэгээс бүрдэх n=q*m+0 байх m-г ол. Бодлогын хариу 100 оронгоос бага байна.
За амжилт.
Мат
За анхны тооноос эхлье даа.
- N натурал тооны хамгийн бага анхны тоон хуваагч нь түүнээс язгуур авсан sqrt(n)-ээс хэтрэхгүй. Эндээс харвал тухайн тооны язгуур хүртлэх бүх тоон дунд ядаж нэг тоо N-г хувааж байвал энэ тоон анхны тоо биш.
- Дараагийн түгээмэл хэрэглэгдэх бодлого бол N хүртлэх бүх анхны тоог олох.
Монголоор анхны тоон тор гэж нэрлэдэг. Sieve-н алгоритм нь дараах байдлаар ажилдаг.
N хүртлэх бүх тоог анхны тоо гэж үзье. i тоологчоо 2-оос эхлээд N хүртэл гүйлгэе. Ингэхдээ хэрэв тухайн i тоо анхны тоо байвал түүнд хуваагдах өөрөөс нь бусад бүх тоог ахны тоо биш болгоно. i=N үед үлдсэн тоонууд анхны тоонууд байна. Алгоритм ингээд болоо.
Дасгал асуулт: i-г хэд хүртэл гүйлгэхэд хангалттай вэ? Мөн ажиллах хугацааны үнэлгээг олно уу.
- Өгөгдсөн хоёр тооны, a b, хамгийн их ерөнхий хуваагчийг ол. Үүнийг англиар greatest common divisor (gcd) гэнэ. a, b хоёрыг хоюуланг нь хуваадаг хамгийн том тоог ол л гэсэн үг. Brute-force хийж үзье.
a = b*q+r хэлбэрт тавигдана. r тэгээс ялгаатай байвал b r хоёрын gcd нь манай бодлогын хариу болно. Иймээс дараах рекурсив функцыг бичиж чадна. Нэг жишээ ажиллаж үзье.
gcd(2336, 1314) ?
2336 = 1314*1 + 1022
1314 = 1022*1 + 292
1022 = 292*3 + 146
292 = 146*2 + 0
- a, b хоёр тоо байхад gcd(a, b) = x*a + y*b байх x, y хоёр тоо олдно. x, y-г олно уу.
Бодолт: a = q*b + r, r!=0 үед gcd(a, b) = gcd(b, r) = b*x` + r*y` байх x`, y` хоёр тоо олдно гэсэн үг. Тэгэхээр:
r = a-q*b
gcd(a, b) = b*x` + r*y` = b*x` + (a-q*b)*y` = y`*a + (x`-q*y`)*b
эндээс
x = y`
y = x` - q*y`
гэсэн үг. Үүнийг өөрөө сайн хийж харна уу!!
- Модулар алгебра.
Чанар болон онолын зүйл бичилгүй шууд хамгийн хэрэглээтэй бодлого бодолтыг нь бичье.
Энгий алгебрад a!=0 байх a нь дурын b-н хувьд a*b=1 байхаар цор ганц утгатай тодорхойлогддог. Харин модулар алгебрад ийм байх албагүй. Жишээ авч үзье.
a=2, mod 26 үед хариу байхгүй. Дээрх b тэгшитгэл биелэх b тоог a-н урвуу тоо гэж нэрлэдэг.
Дараах тоон олонлогийг авч үзье.
Zn = {x E {0..n-1}: x болон n -үүд харилцан анхных}
Зөвхөн Zn харьяалагдах тоонууд урвуу тоотой байна. Батлаарай!
Урвуу тоог олох бодлого нь x*a + y*b = 1 тэгшитгэлд a = a, b=N тавиад дээрх код хүчинтэй.
- Хятадын үлдэгдэлтэй хуваах теорем.
Маш энгийнээр бол a, b, m, n gcd(n, m)=1 бол x=a(mod m) x=b(mod n) байх x-г ол.
Бодолт:
n^(-1) - г n-н урвуу тоо
m^(-1) -г m-н урвуу тоо
тэгвэл x=a*n*n^(-1) + b*m*m^(-1) байна.
source
За маш энгийн болоод маш товч бичлээ. Асуух зүйлүүдээ комментоор бичээрэй. Дуртай хариулна. Матын бодох бодлогуудыг маргааш тавина. Амжилт.
- N натурал тооны хамгийн бага анхны тоон хуваагч нь түүнээс язгуур авсан sqrt(n)-ээс хэтрэхгүй. Эндээс харвал тухайн тооны язгуур хүртлэх бүх тоон дунд ядаж нэг тоо N-г хувааж байвал энэ тоон анхны тоо биш.
- Дараагийн түгээмэл хэрэглэгдэх бодлого бол N хүртлэх бүх анхны тоог олох.
Монголоор анхны тоон тор гэж нэрлэдэг. Sieve-н алгоритм нь дараах байдлаар ажилдаг.
N хүртлэх бүх тоог анхны тоо гэж үзье. i тоологчоо 2-оос эхлээд N хүртэл гүйлгэе. Ингэхдээ хэрэв тухайн i тоо анхны тоо байвал түүнд хуваагдах өөрөөс нь бусад бүх тоог ахны тоо биш болгоно. i=N үед үлдсэн тоонууд анхны тоонууд байна. Алгоритм ингээд болоо.
Дасгал асуулт: i-г хэд хүртэл гүйлгэхэд хангалттай вэ? Мөн ажиллах хугацааны үнэлгээг олно уу.
- Өгөгдсөн хоёр тооны, a b, хамгийн их ерөнхий хуваагчийг ол. Үүнийг англиар greatest common divisor (gcd) гэнэ. a, b хоёрыг хоюуланг нь хуваадаг хамгийн том тоог ол л гэсэн үг. Brute-force хийж үзье.
a = b*q+r хэлбэрт тавигдана. r тэгээс ялгаатай байвал b r хоёрын gcd нь манай бодлогын хариу болно. Иймээс дараах рекурсив функцыг бичиж чадна. Нэг жишээ ажиллаж үзье.
gcd(2336, 1314) ?
2336 = 1314*1 + 1022
1314 = 1022*1 + 292
1022 = 292*3 + 146
292 = 146*2 + 0
- a, b хоёр тоо байхад gcd(a, b) = x*a + y*b байх x, y хоёр тоо олдно. x, y-г олно уу.
Бодолт: a = q*b + r, r!=0 үед gcd(a, b) = gcd(b, r) = b*x` + r*y` байх x`, y` хоёр тоо олдно гэсэн үг. Тэгэхээр:
r = a-q*b
gcd(a, b) = b*x` + r*y` = b*x` + (a-q*b)*y` = y`*a + (x`-q*y`)*b
эндээс
x = y`
y = x` - q*y`
гэсэн үг. Үүнийг өөрөө сайн хийж харна уу!!
- Модулар алгебра.
Чанар болон онолын зүйл бичилгүй шууд хамгийн хэрэглээтэй бодлого бодолтыг нь бичье.
Энгий алгебрад a!=0 байх a нь дурын b-н хувьд a*b=1 байхаар цор ганц утгатай тодорхойлогддог. Харин модулар алгебрад ийм байх албагүй. Жишээ авч үзье.
a=2, mod 26 үед хариу байхгүй. Дээрх b тэгшитгэл биелэх b тоог a-н урвуу тоо гэж нэрлэдэг.
Дараах тоон олонлогийг авч үзье.
Zn = {x E {0..n-1}: x болон n -үүд харилцан анхных}
Зөвхөн Zn харьяалагдах тоонууд урвуу тоотой байна. Батлаарай!
Урвуу тоог олох бодлого нь x*a + y*b = 1 тэгшитгэлд a = a, b=N тавиад дээрх код хүчинтэй.
- Хятадын үлдэгдэлтэй хуваах теорем.
Маш энгийнээр бол a, b, m, n gcd(n, m)=1 бол x=a(mod m) x=b(mod n) байх x-г ол.
Бодолт:
n^(-1) - г n-н урвуу тоо
m^(-1) -г m-н урвуу тоо
тэгвэл x=a*n*n^(-1) + b*m*m^(-1) байна.
source
За маш энгийн болоод маш товч бичлээ. Асуух зүйлүүдээ комментоор бичээрэй. Дуртай хариулна. Матын бодох бодлогуудыг маргааш тавина. Амжилт.
Saturday, April 2, 2016
Хамтдаа хөгжицгөөе
Зав зай арай гайгүй болсон дээрээ хэдэн юм хүүхдүүдэд заагаад өгье гэж хэдэн материал бэлдлээ. Доорх хэдэн сэдэв дээр шаардлагатай онол, алгоритмыг заагаад 8-10н бодлого бэлдсэн байгаа. Шууд онлайн линкийг нь тавих болно, гэхдээ би өөрөө бодлогын өгүүлбэрийг нь орчуулаад блог дээрээ тавина, мөн бодолтын ерөнхий санаа, анализыг нь хэлж өгнө, шаардлагатай гэвэл C++ дээрх бодолтоо тавина.
1. Coding exercise - энд нээх онол шаардахгүй, гэхдээ хоёртын хайлт гэх мэтчилэн арга техникууд хэрэгтэй, гэхдээ зөвхөн анхан шатны мэдлэг л хэрэг болно.
2. Mathematics - Хэрэгтэй мат-уудыг шаардах бодлогууд байх болно. Мэдээж эхлээд өөрөө тайлбарлана.
3. Data Structures - өгөгдөлийн бүтэц
4. Dynamic programming - динамик програмчлал
5. Basic graph algorithms - графын энгийн алгоритмууд
6. Shortest Path algorithms - богино замын алогритмууд
7. String Algorithms
8. Computational Geometry
Бодлогууд бүгд http://poj.org/ - дээр байгаа тул энд бүртгүүлнэ үү.
За шууд эхний сэдэв болох Coding Exercise-руу ороё
Энд онол гэх заагаад байх юм байхгүй байх. Гэхдээ миний блогийг доош нь гүйлгээд C++ STL I, II гэсэн пост мөн бодлогуудын анализуудыг уншчихад гэмгүй.
Доорх бодлогуудыг бодно уу.
1004 - Нэгэн хүний сүүлийн нэг жилийн сар бүрийн орлого өгөгдсөн бол тухайн жилийн орлогын дундажийг олох. Оролт 12 ширхэг бутархай тоо, гаралт бодлогын хариултыг 2 орны нарийвчлалтай $тэмдэгийн араас шууд хэвлэнэ.
Анализ: Оролтын бүх тоог нэмээд 12т хуваах байх аа.
source
----
1003 - Зурагт үзүүлсний дагуу N хөзрийг хөзрийн урттай тэнцүү урттай тавцан дээр давхарлан унагалгүй байж болох хамгийн уртаар нь дээр дээрээс нь тавив. Ингэхийн тулд хэрэв нэг хөзөр байвал тавцангийн 1/2 хэсэг дээр хөзрөө тавина, хэрэв 2 хөзөр байвал хамгийн доод талын хөзрийг тавцангийн 1/3 дээр, 2дахь хөзрийг 1дэх хөзрын 1/2 дээр тавьснаар 1/2+1/3=5/6 уртыг үүсгэж чадна. Ерөнхий тохиолдолд N хөзөр байхад 1/2+1/3+..+1/(N+1) урт үүсгэж чадна гэж үзье. Тэгвэл с гэх ганц бутархай тоо өгөгдсөн бол ядаж с урт үүсгэхийн талд хамгийн багадаа хичнээн хөзөр хэрэгэй болохыг олно уу.
Оролт нь олон тестээс бүрдэх ба 0.00 үед тест дуусна. Мөн тест бүр [0.01;5.20] байна.
Гаралт нь мөр бүрт тухайн тестийн хариуг нэг мөрөнд хэвлэнэ.
Анализ: с тоо хамгийн ихдээ 5.20 тул бодлогын хариу тийм ч том тоо биш байгаа нь харагдах байх. Тэгвэл шууд К-г 1-ээс авахуулаад тухайн К хөзөр с-ээс их буюу тэнцүү хүртэл урттай байх хүртэл нь шууд хайгаад явчихад болно. Энэ хайлт нь утга бүрийг нэг бүрчилэн шалгаж байгаа тул шугаман хайлт гэж нэрлэж байгаа юм. Код дээр search_linear гэсэн функцыг харна уу. Энэ бодолт шууд давна, бодлогын хязгаарлалт хамаагүй бага байгаа тул O(K). Ерөнхийдөө бодлогыг бодож, тухайн хязгаарлалт, хугацаанд амжуулж л байвал болоо гэсэн бодолтой байх хэрэгтэй. Хамгийн чухал нь юу сурч авав гэдэгээ байнга эргэж харж байгаарай.
Бодолтыг илүү хурдан болгож чадах уу? Хоёртын хайлт ашиглана. Бид К-г хамгийн багадаа 1, хамгийн ихдээ -276 гэдэгийг эхний бодолтыг хийгээд харчиж чадна.
compute_length(N) гэсэн функц нь N ширхэг хөзөр өгөгдсөн үед үүсгэж чадах уртыг нь олдог байг. Тэгвэл бодлого маань c<=compute_length(K) байх хамгийн бага К-г ол гэсэн үг. Тэгэхээр К маань өөрөө 1-ээс 276-н хооронд байж болох тул энэ завсарт хоёртын хайлтыг хийнэ гэсэн үг. O(Log(K)).
source
--
1007 - зөвхөн A C G T гэсэн тэмдэгтүүдээс бүрдэх n урттай m шихрэг тэмдэгт мөрүүд өгөгдсөн. Тэмдэгт мөр бүрийн хувьд К гэсэн тоог бодож олно. Энэ нь ямар нэгэн с тэмдэгт нь хичнээн ширхэг өөрөөс нь урд байрлах ёстой тэмдэгтийн урд байрлаж байгаа вэ гэдэгийг тоолно. Тухайн тэмдэгт мөрийн хувьд бүх тэмдэгтүүдийн хувьд дээрх тоог олоод нэмэхэд гарах утгаар К-г тодорхойлно. Тэгвэл тэмдэгт мөр бүрийн хувьд К-г бодож олоод К-уудын хувьд өсөхөөр эрэмблэ гэсэн бодлого. Жишээг нь сайн харж бодлогоо бүрэн ойлгоно уу.
Анализ: Хамгийн энгийн бодолт бол C++ дээр compare функц үүсгэж эрэмблэх бодлого.
source
Анализ2 К-г ямар нэгэн тоон дарааллын хувьд инверс тоо гэдэг. Бидний өмнөх бодолт маань бүх хосуудыг шалгаж байгаа тул хугацааны үнэлгээ нь квадрат O(N^2). Үүнийг рекурс ашиглан O(NlogN)-д бодож болно. Үндсэн санаа нь
F(S) функц нь S-г эрэмблээд мөн тухайн S-н инверсийг тоолдог гэж үзье, (S.sorted, inverse).
S тэмдэгт мөрийн эхний хагасыг left, үлдсэн тэмдэгт мөрийг right гэе, S=left+right. Хэрэв left, right хоёр хоюулаа эрэмлбэгдсэн бол энэ хоёрыг нэгтгэж эрэмбэлсэн шинэ тэмдэгт мөр үүсгэхдээ K-г тоолчиж чадна. Тэгвэл рекурсик хамаарал буюу бодлогын хариу маань
F(S)=>
-> ll = F(left), rr = F(right)
-> S.sorted = left.sorted+right.sorted.
-> S.inverse = left.inverse+right.inverse+K
-> return (S.sorted, S.inverse)
Анзаарч чадсан бол дээрх алгоритм маань merge_sort байгаа. Тэгэхээр merge_sort ашиглан инверсийг O(NlogN)-д олж чадахнээ. source
Анализ3 Ер нь бол энэ бодлогоны хамгийн хурдан бодолт нь Trie өгөгдөлийн бүтэц ашиглах.
--
2140 - N<10 br="" n="">
Анализ Дараалсан тооны нийлбэрт тавихын тулд хамгийн том тоо нь N/2+1 байх нь ойлгомжтой. Шууд бүх боломжийг нь шалгана уу.
source
--
2136 - Өгөгдлөөс зөвхөн том үсэгнүүдийт тус бүр хэд байгааг тоолоод жишээний гаралт шиг хэвлэ.
Анализ Том үсэгнүүдийг A-0, B-1, .., Z-25 гэж дугаарлая. cnt[26] массив дотор үсэг тус бүр хэдэн удаа орсныг нь тоолоод харгалзах дугаараар нь массивын индекс болгож хадгалана. Энэ санаа маш олон бодлого, алгоритмд ашиглагддаг.
source
--
1504 хоёр тоо өгөгдсөн бол энэ хоёр тооны цифрүүдийг урвуулаад хооронд нь нэмээд гарсан хариуг бас дахин урвуулаад хэвлэ. Аль ч тохиолдолд тоо 0-ээр эхэлсэн байж болохгүй.
Анализ шууд хэлснээр нь хий
source
--
1001 R бодит тоо болон N натурал тоо өгөгдсөн бол R^N-г ол. Хэрэв хариу бүхэл тоо бол цэг тавих хэрэггүй. Мөн хариу урт, ардаа 0 агуулах хэрэггүй
Анализ Залхууралгүй, мөн үнэхээр сурмаар мөн өөрийхөө C++ мэдлэгээ сайжруулж сайн код бичдэг болмоор байвал энэ бодох ёстой. Цаас үзэг бариад өөрийг компьютер гэж бодоод алгоритмыг нь гарга.
source
--
3251 - NxN (N<=100) хэмжээтэй хөлөг өгөгдсөн, нүд бүр B, J, * аль нэг нь байна. Тэгвэл * бусад тэмдэгтүүд ямар нэгэн квадрат дүрсийн 4-н булан болж чадахыг олоод хамгийн том квадратын талын уртыг олно уу. Үүсэж болох квадрат нь заавал x, y тэнхлэгтэй параллел байх албагүй.
Энэ бодлогыг хэр бодохнуу хармаар байна. Бодсон нь доор коммент үлдээж санаа бодол, мөн асуух юмаа асуувал дуртай хариулна. Амжилт
Дараагийн пост Математик байх болно.
1. Coding exercise - энд нээх онол шаардахгүй, гэхдээ хоёртын хайлт гэх мэтчилэн арга техникууд хэрэгтэй, гэхдээ зөвхөн анхан шатны мэдлэг л хэрэг болно.
2. Mathematics - Хэрэгтэй мат-уудыг шаардах бодлогууд байх болно. Мэдээж эхлээд өөрөө тайлбарлана.
3. Data Structures - өгөгдөлийн бүтэц
4. Dynamic programming - динамик програмчлал
5. Basic graph algorithms - графын энгийн алгоритмууд
6. Shortest Path algorithms - богино замын алогритмууд
7. String Algorithms
8. Computational Geometry
Бодлогууд бүгд http://poj.org/ - дээр байгаа тул энд бүртгүүлнэ үү.
За шууд эхний сэдэв болох Coding Exercise-руу ороё
Энд онол гэх заагаад байх юм байхгүй байх. Гэхдээ миний блогийг доош нь гүйлгээд C++ STL I, II гэсэн пост мөн бодлогуудын анализуудыг уншчихад гэмгүй.
Доорх бодлогуудыг бодно уу.
1004 - Нэгэн хүний сүүлийн нэг жилийн сар бүрийн орлого өгөгдсөн бол тухайн жилийн орлогын дундажийг олох. Оролт 12 ширхэг бутархай тоо, гаралт бодлогын хариултыг 2 орны нарийвчлалтай $тэмдэгийн араас шууд хэвлэнэ.
Анализ: Оролтын бүх тоог нэмээд 12т хуваах байх аа.
source
----
1003 - Зурагт үзүүлсний дагуу N хөзрийг хөзрийн урттай тэнцүү урттай тавцан дээр давхарлан унагалгүй байж болох хамгийн уртаар нь дээр дээрээс нь тавив. Ингэхийн тулд хэрэв нэг хөзөр байвал тавцангийн 1/2 хэсэг дээр хөзрөө тавина, хэрэв 2 хөзөр байвал хамгийн доод талын хөзрийг тавцангийн 1/3 дээр, 2дахь хөзрийг 1дэх хөзрын 1/2 дээр тавьснаар 1/2+1/3=5/6 уртыг үүсгэж чадна. Ерөнхий тохиолдолд N хөзөр байхад 1/2+1/3+..+1/(N+1) урт үүсгэж чадна гэж үзье. Тэгвэл с гэх ганц бутархай тоо өгөгдсөн бол ядаж с урт үүсгэхийн талд хамгийн багадаа хичнээн хөзөр хэрэгэй болохыг олно уу.
Оролт нь олон тестээс бүрдэх ба 0.00 үед тест дуусна. Мөн тест бүр [0.01;5.20] байна.
Гаралт нь мөр бүрт тухайн тестийн хариуг нэг мөрөнд хэвлэнэ.
Анализ: с тоо хамгийн ихдээ 5.20 тул бодлогын хариу тийм ч том тоо биш байгаа нь харагдах байх. Тэгвэл шууд К-г 1-ээс авахуулаад тухайн К хөзөр с-ээс их буюу тэнцүү хүртэл урттай байх хүртэл нь шууд хайгаад явчихад болно. Энэ хайлт нь утга бүрийг нэг бүрчилэн шалгаж байгаа тул шугаман хайлт гэж нэрлэж байгаа юм. Код дээр search_linear гэсэн функцыг харна уу. Энэ бодолт шууд давна, бодлогын хязгаарлалт хамаагүй бага байгаа тул O(K). Ерөнхийдөө бодлогыг бодож, тухайн хязгаарлалт, хугацаанд амжуулж л байвал болоо гэсэн бодолтой байх хэрэгтэй. Хамгийн чухал нь юу сурч авав гэдэгээ байнга эргэж харж байгаарай.
Бодолтыг илүү хурдан болгож чадах уу? Хоёртын хайлт ашиглана. Бид К-г хамгийн багадаа 1, хамгийн ихдээ -276 гэдэгийг эхний бодолтыг хийгээд харчиж чадна.
compute_length(N) гэсэн функц нь N ширхэг хөзөр өгөгдсөн үед үүсгэж чадах уртыг нь олдог байг. Тэгвэл бодлого маань c<=compute_length(K) байх хамгийн бага К-г ол гэсэн үг. Тэгэхээр К маань өөрөө 1-ээс 276-н хооронд байж болох тул энэ завсарт хоёртын хайлтыг хийнэ гэсэн үг. O(Log(K)).
source
--
1007 - зөвхөн A C G T гэсэн тэмдэгтүүдээс бүрдэх n урттай m шихрэг тэмдэгт мөрүүд өгөгдсөн. Тэмдэгт мөр бүрийн хувьд К гэсэн тоог бодож олно. Энэ нь ямар нэгэн с тэмдэгт нь хичнээн ширхэг өөрөөс нь урд байрлах ёстой тэмдэгтийн урд байрлаж байгаа вэ гэдэгийг тоолно. Тухайн тэмдэгт мөрийн хувьд бүх тэмдэгтүүдийн хувьд дээрх тоог олоод нэмэхэд гарах утгаар К-г тодорхойлно. Тэгвэл тэмдэгт мөр бүрийн хувьд К-г бодож олоод К-уудын хувьд өсөхөөр эрэмблэ гэсэн бодлого. Жишээг нь сайн харж бодлогоо бүрэн ойлгоно уу.
Анализ: Хамгийн энгийн бодолт бол C++ дээр compare функц үүсгэж эрэмблэх бодлого.
source
Анализ2 К-г ямар нэгэн тоон дарааллын хувьд инверс тоо гэдэг. Бидний өмнөх бодолт маань бүх хосуудыг шалгаж байгаа тул хугацааны үнэлгээ нь квадрат O(N^2). Үүнийг рекурс ашиглан O(NlogN)-д бодож болно. Үндсэн санаа нь
F(S) функц нь S-г эрэмблээд мөн тухайн S-н инверсийг тоолдог гэж үзье, (S.sorted, inverse).
S тэмдэгт мөрийн эхний хагасыг left, үлдсэн тэмдэгт мөрийг right гэе, S=left+right. Хэрэв left, right хоёр хоюулаа эрэмлбэгдсэн бол энэ хоёрыг нэгтгэж эрэмбэлсэн шинэ тэмдэгт мөр үүсгэхдээ K-г тоолчиж чадна. Тэгвэл рекурсик хамаарал буюу бодлогын хариу маань
F(S)=>
-> ll = F(left), rr = F(right)
-> S.sorted = left.sorted+right.sorted.
-> S.inverse = left.inverse+right.inverse+K
-> return (S.sorted, S.inverse)
Анзаарч чадсан бол дээрх алгоритм маань merge_sort байгаа. Тэгэхээр merge_sort ашиглан инверсийг O(NlogN)-д олж чадахнээ. source
Анализ3 Ер нь бол энэ бодлогоны хамгийн хурдан бодолт нь Trie өгөгдөлийн бүтэц ашиглах.
--
2140 - N<10 br="" n="">
Анализ Дараалсан тооны нийлбэрт тавихын тулд хамгийн том тоо нь N/2+1 байх нь ойлгомжтой. Шууд бүх боломжийг нь шалгана уу.
source
--
2136 - Өгөгдлөөс зөвхөн том үсэгнүүдийт тус бүр хэд байгааг тоолоод жишээний гаралт шиг хэвлэ.
Анализ Том үсэгнүүдийг A-0, B-1, .., Z-25 гэж дугаарлая. cnt[26] массив дотор үсэг тус бүр хэдэн удаа орсныг нь тоолоод харгалзах дугаараар нь массивын индекс болгож хадгалана. Энэ санаа маш олон бодлого, алгоритмд ашиглагддаг.
source
--
1504 хоёр тоо өгөгдсөн бол энэ хоёр тооны цифрүүдийг урвуулаад хооронд нь нэмээд гарсан хариуг бас дахин урвуулаад хэвлэ. Аль ч тохиолдолд тоо 0-ээр эхэлсэн байж болохгүй.
Анализ шууд хэлснээр нь хий
source
--
1001 R бодит тоо болон N натурал тоо өгөгдсөн бол R^N-г ол. Хэрэв хариу бүхэл тоо бол цэг тавих хэрэггүй. Мөн хариу урт, ардаа 0 агуулах хэрэггүй
Анализ Залхууралгүй, мөн үнэхээр сурмаар мөн өөрийхөө C++ мэдлэгээ сайжруулж сайн код бичдэг болмоор байвал энэ бодох ёстой. Цаас үзэг бариад өөрийг компьютер гэж бодоод алгоритмыг нь гарга.
source
--
3251 - NxN (N<=100) хэмжээтэй хөлөг өгөгдсөн, нүд бүр B, J, * аль нэг нь байна. Тэгвэл * бусад тэмдэгтүүд ямар нэгэн квадрат дүрсийн 4-н булан болж чадахыг олоод хамгийн том квадратын талын уртыг олно уу. Үүсэж болох квадрат нь заавал x, y тэнхлэгтэй параллел байх албагүй.
Энэ бодлогыг хэр бодохнуу хармаар байна. Бодсон нь доор коммент үлдээж санаа бодол, мөн асуух юмаа асуувал дуртай хариулна. Амжилт
Дараагийн пост Математик байх болно.
Subscribe to:
Comments (Atom)