[Rešenja zadataka] 2021/2022 SIO - dan 2

Algoritam
1

Дугмићи

Аутор: Павле Мартиновић
Текст и тест примери: Алекса Милојевић
Тестирање: Момчило Тошић
Анализа решења: Момчило Тошић

Решење када T_i \leq 6, и Z_i \leq 6 за X_i = 1:

У овом случају треба разматрати једино кратке сегменте [L,R], јер уколико је одговор ДА, мораћемо у једном тренутку да одемо од крајњег левог до крајњег десног дугмета, што би угасило почетни тајмер уколико је T_L < (R-L). На овим сегментима можемо да покушамо да идемо лево-десно пар пута, мењајући на сваком кораку све тајмере у сегменту.

Решење када N,Q \leq 2000:

Уочимо да, уколико постоји решење, ћемо до сваког дугмета морати у неком тренутку да дођемо до левог, као и до десног краја сегмента, и назад. Дакле, за трајање сваког тајмера у траженом сегменту мора да важи T_i \geq 2(i-L) (дугме-леви крај-дугме) и T_i \geq 2(R-i) (аналогно за десни крај). Обилазак ‘лево-десно’ нам управо гарантује да успевамо чак и ако важи T_i = 2(i-L) и T_i = 2(R-i). Ове неједнакости можемо ручно да проверимо за свако дугме у сегменту.

Решење када X_i = 2

Чињеница да нема промена у низу имплицира offline решење. Наиме, потребно је наћи одговоре за све сегменте [L,R] проласком кроз низ једном. Приметимо да ако важи неједнакост T_i \geq 2(i-L), за неко L, она важи и за све мање L. Сходно томе, обилазимо све дугмиће од 1 ка N и на сваком додајемо у неку структуру све леве крајеве сегмената који у њему почињу, док бришемо редом (од мањих ка већим) све леве почетке за које не важи T_i \geq 2(i-L) (што постижемо тако што нпр. у multiset држимо вредности 2L и поређујемо их са 2i-T_i), а потврђујемо могућност решења за неки сегмент кад дођемо до дугмета које представља његов десни крај. Ово је потребно урадити и у другом смеру (од краја ка почетку).

Решење за пун број поена

Како у свим дугмићима сегмента треба да важи T_i \geq 2(i-L), T_i \geq 2(R-i) (што је еквивалентно са 2L \geq 2i-T_i, 2R \leq T_i+2i), то значи да нам је потребан начин да одредимо да ли постоји вредност 2i-T_i \leq 2L и 2i+T_i \geq 2R за i у сегменту [L, R] (вредност за које не важи неједнакост), као и да променимо вредност на некој позицији. Ово нам омогућавају два сегментна стабла, где чувамо вредности 2i+T_i и 2i-T_i и поређујемо максимум, односно минимум на траженим сегментима са 2R и 2L.

2

Ју-ес опен

Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Тестирање: Тадија Шебез
Анализа решења: Младен Пузић

Прва ствар коју је потребно да приметимо јесте како да доделимо време трајања неком конкретним мечу. Приметимо да нам се увек исплати да то буде време трајања првог меча победника. Такав меч још увек има потенцијал да буде интересантан, а не ограничавамо се за будуће мечеве више него што морамо. Сада је потребно само одредити победника сваког меча док замишљамо да се његово време пропагира на следеће коло.

Решење када N \leq 4

Пошто има 16 преосталих играча, постојаће још укупно 15 мечева. За сваки меч можемо да одаберемо да ли побеђује леви или десни играч, јер постоји само 2^{15} = 32768 комбинација.

Временска сложеност је O(2^ {2^N}), а меморијска О(2^N).

Решење када A[i] \leq 2

Јасно је по горњој обзервацији да ће сваки меч трајати или 1 или 2 минута (мора да игра Ђоковић). Нумеришемо све мечеве од 1 до 2^{N+1}-1. Сада, можемо радити динамичко програмирање облика:

dp[i][1/2] = \text{оптимално решење ако меч }i\text{ траје 1, односно 2 минута}

Базни случајеви су очигледно мечеви првог кола, за које знамо колико су трајали (и онда на један случај тих мечева стављамо 0, а на други -\infty).

Посматрајмо неки фиксни меч i који није меч првог кола. Нека је l меч из којег је дошао победник леве стране жреба, а d меч из којег је дошао победник леве стране жреба.

Важе следеће рекурентне везе:

dp[i][1] = \max(dp[l][1]+dp[r][1]+1, dp[l][1]+dp[r][2]+1, dp[l][2]+dp[r][1])
dp[i][2] = \max(dp[l][2]+dp[r][2]+1, dp[l][1]+dp[r][2]+1, dp[l][2]+dp[r][1])

Дакле, свака комбинација, сем када је меч l трајао 2 минута, а меч r трајао 1 минут, даје један нови интересантан меч. Крајњи резултат, ако је финале нумерисано бројем f, је \max(dp[f][1], dp[f][2]).

Временска и меморијска сложеност је O(2^N).

Решење када N \leq 17 и A[i] \leq 100

Слично претходном подзадатку, радићемо динамичко програмирање над нумерисаним мечевима:

dp[i][j] = \text{оптимално решење ако меч }i\text{ траје } j \text{ минута}

Поново имамо три случаја:

  • Први случај је ако не желимо да тренутни меч буде интересантан. Онда један меч (леви или десни) мора трајати j минута, за други можемо узети било коју вредност, па ћемо узети ону која даје највише интересантних мечева.
  • Други случај је да желимо да меч i буде интересантан, а да леви меч траје j минута. Зато, десни меч мора трајати макар толико, да бисмо добили нови интересантан меч. Узећемо наравно оптималну дужину десног меча.
  • Трећи случај је такође да желимо да меч i буде интересантан, а да десни меч траје j минута. Леви меч онда мора трајати највише толико. Поново узимамо оптималну дужину левог меча.

Све ово можемо ефикасно имплементирати чувајући префиксне, односно суфиксне максимуме над динамичким програмирањем за сваки меч.

Временска и меморијска сложеност је O(2^N\cdot maxA).

Решење када N \leq 17

Задатак поново радимо динамичким програмирањем, мада овај пут нумеришемо и мечеве и играче:

dp[i][j] = \text{оптимално решење ако је победника меча }i\text{ играч } j

Овде на први поглед има O(2^N\cdot 2^N) стања, али то није тачно - број играча који могу бити победници неког меча (који су у том делу жреба) доста варира. У збиру, зато, постоји само О(2^N \cdot N) стања, јер сваки играч може бити победник у само N различитих мечева. Динамичко програмирање можемо радити коло по коло, кренувши од другог кола (прво је већ одиграно).

Сада, слично претходном подзадатку, ако нам је победник са леве стране жреба и желимо интересантан меч, десно морамо одабрати играча којем је први меч трајао макар колико први меч победника. Аналогно радимо и ако желимо да победник буде из десне стране жреба.

Како бисмо то ефикасно урадили, морамо у обе половине имати играче сортиране по дужини првог меча. Након дога, попут претходног задатка можемо користећи префиксне/суфиксне максимуме над низом динамичког програмирања, као и технику два показивача или бинарну претрагу, можемо наћи одговарајуће вредности. Све ово можемо једноставно имплементирати рекурзијом.

Временска сложеност је O(2^N \cdot N^2), а меморијска O(2^N) (ако памтимо увек само резултате претходног кола).

Главно решење

Слично претходном подзадатку, само што уместо да користимо сортирање на сваком нивоу рекурзије, ми одржавамо сортирани низ и спајамо их техником два показивача, попут алгоритма merge sort. Тиме смањујемо временску сложеност за N фактор.

Временска сложеност је O(2^N\cdot N), а меморијска O(2^N).

3

Метрополе

Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Анализа решења: Павле Мартиновић
Тестирање: Алекса Плавшић

Решење када N \leq 20

Ово је класичан задатак из динамичког програмирања са битмаскама - тражење најдужег пута у графу. Имамо динамичко програмирање dp[i][mask], где је i представља чвора до ког смо стигли, а mask је битмаска која представља које смо чворове посетили до сад.
Сложеност O(N^2\cdot2^N)

Решење када нема тура

У овом случају, дати граф је стабло, а решење у том случају је познато: можемо или радити динамичким програмирањем, или напросто кренемо од произвољног чвора и нађемо од њега најдаљи, а затим од тог најдаљег нађемо најдаљи, што ће нам дати најдужи пут.

Како даље?

Сада треба да нађемо неку озбиљну стратегију како да тражимо најдужи пут. У ту сврху ћемо пронаћи блокове нашег графа. То су максимални подскупови чворова тако да у тим скуповима нема артикулационих тачака. За ово постоји генерални алгоритам, али у нашем случају то може да се уради лакше. Наиме, пустимо претрагу по дубили (DFS) у нашем графу, и за сваку грану ван стабла узмемо пут на стаблу који спаја њене крајеве (који је дужине 3 због услова са дужинама циклуса) и утрвдимо да су те 4 гране у истом блоку (свака грана је највише у једном блоку). Када тако нађемо све могуће четворке, транзитивно затворимо релацију “у истом блоку” (у преводу, направимо граф над гранама и у њему нађемо повезане компоненте - чворови које оне обухватају нам представљају блокове графа). Спорије имплементације овог дела су обухваћена подзадатком N\le2500.

Сада, у произвољном графу можемо увести појам block-cut стабла тако што избацимо све гране које су део неког блока и онда за сваки блок направимо нови чвор који је повезан са свим чворовима у том блоку. Ово је интересантно, јер ако је почетни граф повезан, онда нам је block-cut стабло заиста стабло (ако није повезан онда је у питању шума). Сваки пут у овом графу може да се преслика у пут на block-cut стаблу, само сваки фрагмент пута који представља кретање унутар једног блока заменимо са путем од почетног до чвора који представља тај блок, и онда од тог до завршног.

Сада нам је циљ да модификујемо block-cut стабло. За сваки блок желимо да пронађемо стабло тако да су нам чворови блока листови, и да је најдужи пут од u до v унутар блока једнак дужини пута од u до v у нашем стаблу. Ако сваки блок чвор у block-cut стаблу заменимо са овом мрежом која енкодира оптимизацију тражења најдужег пута на оном фрагменту пута који се налази унутар стабла, онда нам се задатак само своди на претходни подзадатак - тражење најдужег пута на стаблу (овде конкретно на том нашем модификованом block-cut стаблу), јер сваки пут у стаблу можемо на исти начин да пресликамо на пут на модификованом block-cut стаблу, а по конструкцији ће се најдужи пут пресликати у пут исте дужине.

Сада нам треба детаљан опис блокова нашег графа. За то нам треба следећа лема:
Лема: Сваки блок у нашем графу је комплетан бипатритиван граф где је једна партиција величине 2.
Доказ: Пошто сваки циклус парне дужине, граф је бипартитиван - нека је у нашем блоку b белих и c црних. Могуће је доказати да унутар блока, за сваке две гране постоји циклус који их садржи. Претпоставимо да постоје црни чвор u и бели чвор v који нису спојени граном, и нека из њих излазе гране ua и vb. По претходно наведеном, постоји циклус који садржи, а то једино може бити циклус u-a-b-v, тако да су u и v ипак повезани граном, па је граф комплетан и бипартитиван. Најзад, онда тривијално постоји циклус дужине 2\min(b,c)=4, па је заиста у једној партицији само 2 чвора.

Сада смо већ близу краја. За конструкцију наших стабала разликујемо два случаја (и то баш они из подзатака!!)

Свака грана се налази у највише једном циклусу

У овом случају су нам блокови само K_{2,2} то јест циклуси дужине 4. Посматрајмо циклус a-b-c-d, ту супротни на циклусу треба да буду на дистанци 2, а суседни на циклусу треба да буду на дистанци 3. Додајмо чворове e и f и повежемо парове a-e, c-e, b-f, d-f и e-f. Лако се проверава да је ова конструкција баш оно што смо тражили.

Свака грана која се налази у једном циклусу се налази у барем два циклуса

У овом случају су нам блокови само K_{2,t} са t\ge3, нека су нам ова 2 чвора бела, а осталих t црни. Можемо да видимо да најдужа путања између 2 црна чвора дужине 4, између црног и белог дужине 3 и између два дела дужине 2. Зато је довољно да узмемо један нови чвор који спојимо са свим белима директно граном, а са свим црнима путем дужине 2.

Главно решење

Напросто спојимо конструкције из предхотна два случаја, и онда на добијеном стаблу нађемо најдужи пут.
Сложеност O(N).

1 Like