2012-11-17 03:53:48
Зайн сургалт
by
Bataa
2010-03-20 18:32:08
Дэмжин туслах хүмүүсийг урьж байна.
by
Bataa
2010-03-10 19:25:57
Greedy Algorithm
by
Bataa
There is a long list of stalls, some of which need to be covered with boards. You can use up to N (1 <= N <= 50) boards, each of which may cover any number of consecutive stalls. Cover all the necessary stalls, while covering as few total stalls as possible. The IdeaThe basic idea behind greedy algorithms is to build large solutions up from smaller ones. Unlike other approaches, however, greedy algorithms keep only the best solution they find as they go along. Thus, for the sample problem, to build the answer for N = 5, they find the best solution for N = 4, and then alter it to get a solution for N = 5. No other solution for N = 4 is ever considered. Greedy algorithms are fast, generally linear to quadratic and require little extra memory. Unfortunately, they usually aren't correct. But when they do work, they are often easy to implement and fast enough to execute. ProblemsThere are two basic problems to greedy algorithms. How to BuildHow does one create larger solutions from smaller ones? In general, this is a function of the problem. For the sample problem, the most obvious way to go from four boards to five boards is to pick a board and remove a section, thus creating two boards from one. You should choose to remove the largest section from any board which covers only stalls which don't need covering (so as to minimize the total number of stalls covered). To remove a section of covered stalls, take the board which spans those stalls, and make into two boards: one of which covers the stalls before the section, one of which covers the stalls after the section. Does it work?The real challenge for the programmer lies in the fact that greedy solutions don't always work. Even if they seem to work for the sample input, random input, and all the cases you can think of, if there's a case where it won't work, at least one (if not more!) of the judges' test cases will be of that form. For the sample problem, to see that the greedy algorithm described above works, consider the following: Assume that the answer doesn't contain the large gap which the algorithm removed, but does contain a gap which is smaller. By combining the two boards at the end of the smaller gap and splitting the board across the larger gap, an answer is obtained which uses as many boards as the original solution but which covers fewer stalls. This new answer is better, so therefore the assumption is wrong and we should always choose to remove the largest gap. If the answer doesn't contain this particular gap but does contain another gap which is just as large, doing the same transformation yields an answer which uses as many boards and covers as many stalls as the other answer. This new answer is just as good as the original solution but no better, so we may choose either. Thus, there exists an optimal answer which contains the large gap, so at each step, there is always an optimal answer which is a superset of the current state. Thus, the final answer is optimal. ConclusionsIf a greedy solution exists, use it. They are easy to code, easy to debug, run quickly, and use little memory, basically defining a good algorithm in contest terms. The only missing element from that list is correctness. If the greedy algorithm finds the correct answer, go for it, but don't get suckered into thinking the greedy solution will work for all problems. Sample ProblemsSorting a three-valued sequence [IOI 1996] You are given a three-valued (1, 2, or 3) sequence of length up to 1000. Find a minimum set of exchanges to put the sequence in sorted order. Algorithm The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1's in the 2 part with 2's in the 1 part, as many as possible 1's in the 3 part with 3's in the 1 part, and 2's in the 3 part with 3's in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1's into place and then all the 2's into place. Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no ``interference'' between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1's are put in place but no others; then all that remains are 2's in the 3's place and vice-versa, and which can be swapped). Friendly Coins - A Counterexample [abridged]Given the denominations of coins for a newly founded country, the Dairy Republic, and some monetary amount, find the smallest set of coins that sums to that amount. The Dairy Republic is guaranteed to have a 1 cent coin. Algorithm: Take the largest coin value that isn't more than the goal and iterate on the total minus this value. (Faulty) Analysis: Obviously, you'd never want to take a smaller coin value, as that would mean you'd have to take more coins to make up the difference, so this algorithm works. Maybe not: Okay, the algorithm usually works. In fact, for the U.S. coin system {1, 5, 10, 25}, it always yields the optimal set. However, for other sets, like {1, 5, 8, 10} and a goal of 13, this greedy algorithm would take one 10, and then three 1's, for a total of four coins, when the two coin solution {5, 8} also exists. Topological SortGiven a collection of objects, along with some ordering constraints, such as "A must be before B," find an order of the objects such that all the ordering constraints hold. Algorithm: Create a directed graph over the objects, where there is an arc from A to B if "A must be before B." Make a pass through the objects in arbitrary order. Each time you find an object with in-degree of 0, greedily place it on the end of the current ordering, delete all of its out-arcs, and recurse on its (former) children, performing the same check. If this algorithm gets through all the objects without putting every object in the ordering, there is no ordering which satisfies the constraints.
2010-03-08 09:32:00
Бүрэн хайлт
by
Bataa
Бүрэн хайлт ашиглан бодлого бодох нь “Энгийн Тэнэг Байх” зарчимд тулгуурладаг. Тэмцээний бодлого бодох гол зорилго илүү оновчтой алгоритм байгааг үл харгалзан өгсөн хязгаарт багтаж ажиллах програм бичих байдаг. Бүрэн хайлт нь brute force, шугаман хайлт, бүгдийг нь турш зэрэг аргуудыг ашигладаг бөгөөд ихэхдээ хамгийн хялбар арга байдаг. Хэрвээ энэ аргаар бодоод цаг болон санах ойн хязгаарт багтаж байвал энэ аргаараа л бод. Энэ нь кодлох болон алдааг илрүүлэхэд хялбар. Ингэснээрээ brute force аргаар бодож болохгүй хүнд бодлогуудад илүү их цаг зарцуулах боложтой болох юм. Хэдэн саяаас бага боломжтой бодлогонд тус бүрчлэн шалгаж бодлогын хариу олдож байгаа эсэхийг шалгана. Хашир байгаарайЗарим тохиолдолд энэ аргаар бодно гэдэг нь илт байдаггүй. Бодлого. Үдэшлэгийн гэрлүүд [IOI 98]Таньд N ширхэг гэрлийн шил болон 4 унтраалга өгөгджээ. Энхий унтраалга бүх гэрлүүдийн, хоёр дахь нь тэгш дугаартай гэрлүүдийн, гурав дахь нь сондгой дугаарай гэрлүүдийн дөрөв дахь нь 1, 4, 7, 10 гэсэн дарааллаар дугаарлагдсан гэрлүүдийн төлвийг тус тус өөрчилнө. Нийт хэдэн удаа унтраалга дарагдсаныг илэрхийлэх N (10000 хүртэлх) тоо болон зарим гэрлийн шилний одоогийн төлвийг (унтраалттай эсвэл асаалттай) өгөхөд гэрлийн шилнүүдийн байж болох бүх боломжит төлвийг харуулна уу. Өнгөцхөн харахад даралт бүрт 4 боломж тэгэхээр нийт 410000 (ойрлцоогоор 106020) боломжтой өөрөөр хэлбэр энэ бодлогонд бүрэн хайлт ашиглах ямарч боломжгүй. Унтраалгуудын дарагдсан дараалал хамаагүй гэдэг нь энэ тоог 100004 болгож багасгана. Энэ нь ойролцоогоор 1016. Гэсэн хэдий ч бүрэн хайлт хийхэд хэтэрхий их байна (гэхдээ урьдын тооцоолсноос даруй 106000 орчим багассан үзүүлэлт). Гэтэл товчийг 2 удаа дарах нь огт дараагүйтэй адилхан тэгэхээр чиний жинхэнэ шалгах ёстой зүйл бол унтраалга бүрийг 0 эсвэл 1 удаа дарах.Энэ нь 24 =16 боломжтой одоо бүрэн хайлтын аргыг ашиглах нь тодорхой харагдаж байгаа биз. Бодлого: Цагнууд [IOI 94]9 ширхэг цаг 3х3 хэмжээтэй хүснэгтэнд байх бөгөөд тус бүр нь 12:00, 3:00, 6:00, 9:00 цагийг заажээ. Чиний даалгавар бол тэдгээр цагийг 12:00 зааж буй мэт харуулан өөрчлөх. Харамсалтай нь чи зөвхөн зөвшөөрөгдсөн 9 үйлдлийг л хийх боломжой. Тэдгээр үйлдэл нь 9 цаг бүрийн аль нэгийг 90 градусаар эргүүлэх болно. Хамгийн цөөн үйлдлээр бүх цагийг 12:00 зааж байгаа болгон хувиргах аргыг ол. Ойлгомжой шийдэл бол 1 үйлдлээр хувиргах боломж байна уу, 2 үйлдлээр хувиргах боломж байнуу гэх мэтчилэн шийдэл олтлоо шалгах рекурсив ашиглах. Энэ нь 9k удаа шалгах болно. K нь нийт үйлдлийн тоо. K нь том тоо байж болох тул хязгаарт багтаж хариуг олж чадахгүй. Эргүүлэлтүүдийн дараалал хамаарахгүй гэдгийг тооцвол энэ нь k9 болтлоо багасах хэдий ч хангалттай бага биш. Гэтэл 4 удаа эргүүлэх нь эргүүлэлт хийгээгүйтэй адил. Тиймээс аль ч цагийг 3-с олон удаа эргүүлэхгүй. Тэгэхээр нийт 49 боломжтой энэ нь 262,072. Процессор секундэнд 10,000,000-с олон үйлдэл хийх чадалтай гэхээр хариуг хангалттай богино хугацаанд гаргаж өгнө. Brute force арга нь энэ тохиолдлуудад тохиромжтой. Жишээ бодлогууд Үнээ саах [USACO 1996 уралдааны шат]Үнээ саах цагийн хуваарь (жишээ нь Саальчин А 300 цагаас 1000, саальчин В 700 цагаас 1200, гэх мэт) өгөгдсөн бол
Бүх хуваагчдых нь нийлбэр өөртэй нь тэнцүү байх тоог төгс тоо гэнэ. Жишээ нь 28=1+2+4+7+14. Төгс хос тоонууд гэж нэгнийх нь худаагчдын нийлбэр нөгөөтэйгээ тэнцүү байдаг хос тоонуудыг хэлнэ. Эхний тооны худаагдчдын нийлбэр нь хоёр дахь тоотой хоёр дахь тооны худаагчдын нийлбэр нь гурав дахь тоотой гэх мэтчилэн сүүлчийн тооны хуваагчдын нийлбэр нь эхний тоотой тэнцүү байх дарааллыг төгс дараалал гэнэ. Фермер Жоны фирм дахь үнээ бүр нь дугаартай бөгөөд. 1-с 32000 хүртэл дугаарлагдсан. Дугаар нь төгс тоо байвал төгс үнээ гэе. Дугаарууд нь төгс тоон дараалал үүсгэх үнээнүүдийг төгс төрөл садан үнээнүүд гэе. Бүх төгс үнээ болон төгс үнээний төрөл садангуудыг ол. Орчуулсан : Б.Даваабаяр
2010-02-21 08:20:24
Төрөл бүрийн бодлогууд / Ad hoc problems
by
Bataa
2010-02-19 14:13:00
USACO Танилцуулга
by
Bataa
2010-02-19 14:04:25
Бодлогын төрлүүд
by
Bataa
2010-02-19 06:01:07
www.usaco.org
by
Bataa
|