[Rešenja zadataka] 2021/2022 Izborno za EJOI

Послован човек

Ускоро!

Архитекта

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

Решење када M = N-1

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

Решење када скуп путева прави циклус

У овом подзадатку, морамо одабрати све путеве сем једног, где можемо било који изоставити. Можемо пребацити овај граф у низ дужине N, где чувамо цене путева редом. Да бисмо ефикасно нашли битовску дисјункцију свих путева сем једног, чуваћемо префиксну и суфиксну битовску дисјункцију тог низа. Решење је онда битовска дисјункција одговарајућег префикса и суфикса. Од свих могућих опција, бирамо ону која даје најјефтинији план. Временска и меморијска сложеност је O(N).

Решење када 0 \leq w_i \leq 1

Битовска дисјункција бројева из скупа \{0, 1\} може бити 0 само ако су сви бројеви 0. У супротном она је 1. Зато, проверимо да ли када узмемо све путеве цене 0 добијемо државу у којој је сваки град повезан са сваким другим. Уколико да, решење је 0, у супротном, решење је 1. Ово можемо проверити на пример DFS алгоритмом. Временска и меморијска сложеност је O(N+M).

Решење када 1 \leq M, w_i \leq 10^3

Пошто су цене путева до 1000, онда је највећи могући резултат 1023. Проверићемо све могуће укупне цене једну по једну од најмање ка највећој. Рецимо да проверавамо резултат x. Прођимо редом кроз све гране и додајмо само оне које можемо, тако да x остане могућ резултат. У овом случају, то значи да ни на једној позицији у бинарном запису нема цифру 1, а да је у броју x та цифра 0. Када додамо све те гране, као у претходном подзадатку проверимо да ли је могуће стићи од сваког града до сваког другог користећи те гране. Ако да, и то је најмање такво x, то је решење. Временска сложеност је O(M\cdot \max(w_i)), а меморијска O(N+M).

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

Уместо да фиксирамо могући резултат као у претходном задатку, градићемо резултат бит по бит, кренувши од највреднијег бита. Пошто важи да је 2^{0} + 2^{1} + \ldots + 2^{i} \leq 2^{i+1}, у интересу нам је да највреднији бит буде што мањи. Покушајмо прво да избегнемо највреднији бит. Додајмо све гране у чијим тежинама је та цифра 0. Уколико можемо да направимо план само са тим гранама, стављамо 0 на ту цифру резултата, а избацујемо из скупа грана све гране чијој цени је та цифра 1, јер су непотребне. Уколико не можемо, онда стављамо 1 на ту цифру, али одржавамо исти скуп грана (неопходне су нам обе врсте). У оба случаја, прелазимо на следећи бит на исти начин. На крају, имаћемо конструисани резултат. Временска сложеност је O(M\log(w_i)), а меморијска O(N+M).

1 Like

Заграде

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

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

Након сваке промене, пребацујмо једну по једну заграду са почетка на крај, док не наиђемо на први пут када имамо валидан низ заграда. Решење је број пребачених заграда. Проверавамо да ли је низ заграда валидан тако што идемо слева надесно и одржавамо број неупарених отворених заграда. Уколико наиђемо на отворену заграду, повећавамо тај број. Уколико наиђемо на затворену заграду, а број неупарених отворених заграда је већи од 0, онда упарујемо једну отворену заграду са том затвореном заградом, па смањујемо тај број. Уколико немамо неупарених отворених заграда, а наиђемо на затворену заграду, низ заграда није валидан. Он такође није валидан ако завршимо процес са неупареним отвореним заградама. Временска сложеност је O(QN^2), а меморијска O(N).

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

У овом подзадатку ћемо применити сваку промену и покушати да нађемо решење у O(N). Посматрајмо следећи низ:

p_0 = 0
p_i = \begin{cases} p_{i-1} + 1, & i\text{-та заграда је отворена} \\ p_{i-1} - 1, & i\text{-та заграда је затворена} \end{cases}

Приметимо да је услов да низ заграда буде валидан да важи p_i \leq 0 за свако 1 \leq i \leq N и p_N = 0 (ово је еквивалентно томе да ниједан префикс нема више затворених него отворених заграда и да укупно имамо једнако отворених и затворених заграда).

Посматрајмо сад шта се деси када првих i заграда пребацимо на крај. Можемо приметити да ће се првих i елемената низа p_i пребацити на крај и онда ће се цео низ повећати за -p_i. Пошто желимо да сви елементи буду већи или једнаки 0, онда морамо да га повећамо за што више, што значи да ћемо узети што мање p_i. Дакле, решење је i за које је p_i најмање. Уколико има изједначења, онда узимамо најмање такво i. Након сваке промене само поново израчунамо низ p_i. Временска сложеност је O(QN), а меморијска O(N).

Решење када све промене мењају затворене заграде у отворене

Приметимо да, како би низ заграда био валидан, морамо имати једнак број отворених и затворених заграда. Рецимо да на почетку имамо l отворених, а r затворених заграда. Уколико r < l онда очигледно никад не можемо добити валидан низ заграда. У супротном, моћи ћемо да имамо валидан низ заграда само након што \frac{r-l}{2} затворених заграда претворимо у отворене. Уколико \frac{r-l}{2} > Q, онда опет никад нећемо имати решење. У супротном, довољно је да применимо решење из претходног подзадатка након \frac{r-l}{2} промена (сви остали резултати су -1). Временска сложеност је O(N+Q), а меморијска O(N).

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

Овај подзадатак се ради слично као други подзадатак, само због ефикасне промене низа p_i потребно је да одржавамо сегментно стабло са лењом пропагацијом над њим. Промена која је потребна је додавање +1 или -1 на неки суфикс, и налажење минимума целог низа. Да бисмо узели најлевљи минимум целог низа, сегментно стабло градимо над низом парова \{p_i, i\}, па ћемо упитом минимума добити онај пар са најмањим p_i, а најмањим индексом у случају изједначења. Временска сложеност је O(Q\log N), а меморијска O(N).

1 Like