3-р сарын тэмцээн бодолт - 1

Jenny and you, BCC :

Энгийн оролт гаралттай ажиллах бодлого.


Хуваалт :

3/4 pizza иддэг хүмүүст тус тусад нь бүтэн pizza өгөхөөс аргагүй билээ. Ингээд үлдэгдэл 1/4 хэсгүүдийг 1/4 иддэг хүмүүст өгөх нь хэрэгтэй.
Тэгэхээр манай бодлого 1/4, 2/4 бодлоготой ижилхэн боллоо л гэсэн үг. 2/4 иддэг хүмүүсийг хоёр хоёроор нь хос болгон авч үзээд пиззаг өгөх хэрэгтэй. Ингэхэд нэг хүн сондгойрч болох ба энэ хүнийг 1/4 иддэг 2 хүнтэй хос болгоод, үлдсэн 1/4 иддэг хүмүүсийг дөрөд дөрвөөр хос болгоход хангалттай.
Баталгаа :
1/4, 2/4 хүмүүст дээрх санаагаар pizza хуваарилахад гагцхүү ганц pizza-с үлдэгдэл гарч болох учир уг бодолт зөв юм.


Хамгийн ойр нийлбэр :

Бүх боломжийн тоо 2^N болох учир хэтэрхий их болно. Гэхдээ N1=N/2, N2-N-N1 байхаар хоёр хэсэгт хуваагаад бүх нийлбэр S1[0..N1-1], S2[0..N2-1] бодож олъё. N1,N2<=19 тул санах ойд ч багтна. Одоо S2-оо эрэмбэлээд бүх i=0..N-1 хувьд S1[i]+S2[j]>=K байх j-г хоёртын хайлтаар олъё.
Бидний сонирхож байгаа нийлбэр j-1, j, j+1 3-н аль нэг болох учир бүгдийг шалгавал бодлого бодогдно.
Шаардагдах хугацаа:
Бүх нийлбэрийг олох - O(2*2^(N/2))
Эрэмбэлэлт - O(2^(N/2)*(N/2)),
Хоёртын хайлтаар бүх боломжит нийлбэрийг олох
O(2^(N/2)*(N/2)*3)
Иймд энэ бодолт O(2^(N/2)*(N/2)) болно.
Тайлбарыг Anonymous хийв. (Чимэд ах???)


Цэцэг тарив :

Зөвлөгөө : Өгөгдлийн бүтэц. ( Interval Tree? ) O(N * sqrt ( N )) эсвэл O(N * log N)


Гайхамшигт хослол :

Хамгийн муу тохиолдолд олонлог маань 8*7*6*5*4=6720 элемэнттэй байж болно.
Эхний буюуу хамгийн муу бодолт нь уг олонлогоос шууд дөрвөн тоо сонгож аваад "гайхамшигт хослол" үүсэх эсэхийг шалгах. Энэ бодолт O (N ^ 4) байх нь ойлгомжтой.
Дараагийн бодолт нь гайхамшигт хослолыг нийлбэрт орж буй 3 тоогоор илэрхийлж болно гэдгийг хараад a+b+c тоо олонлогт орших эсэхийг O(1)-д шалгаснаар O(N ^ 3) болно.
Эцсийн бодолт:
a+b+c=d илэрхийллийг a+b=d-c хэлбэртэй бичээд илэрхийллийн 2 талыг хайснаар O(N ^ 2) -д бодож болно