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

Извлачење сламки

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

Подзадатак 1

За овај подзадатак, потребно је наћи позицију са које се највише пута извлачи сламка, а да је могуће ставити најкраћу сламку на ту позицију. Потребно је, дакле, само наћи интервал на којем може завршити најкраћа сламка. На почетку је тај интервал једнак само њеној почетној позицији, док сваким новим мешањем тај интервал се може проширити, уколико се макар и мало преклапа са интервалом мешања. Временска и меморијска сложеност: O(N+M).

Подзадатак 2

За свако мешање, можемо фиксирати да ли се мења место двема сламкама на интервалу мешања. Сваку комбинацију симулирамо и узмемо најбоље решење. Меморијска сложеност: O(N+M), временска сложеност: O(2^M\cdot M + N).

Подзадатак 3

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

Подзадатак 4

Означимо са dp_{i, j} максимално решење ако се после j догађаја најкраћа сламка налази на позицији i. На почетку важи dp_{i, 0} = -\infty (довољно мали негативан број), за свако i на којем се не налази најкраћа сламка, док важи dp_{i, 0} = 0, за i које је почетна позиција најкраће сламке. Сада је потребно да нађемо рекурзивну везу. Постојаће два случаја, за два различита типа догађаја:

1 l r: dp_{i, j} = max\{dp_{l, j-1}, dp_{l+1, j-1}, \ldots, dp_{r, j-1}\}, уколико i \in [l, r]. У супротном dp_{i, j} = dp_{i, j-1}. Дакле, било која позиција на интервалу може доћи са било које друге позиције на интервалу, а оптимално је да узмемо са максималне.

2 x: dp_{x, j} = dp_{x, j-1} + 1, а dp_{i, j} = dp_{i, j-1} уколико i \neq x. Једино се повећава случај кад се баш ту налази најкраћа сламка, остале се не мењају.

Меморијска сложеност: O(NM) (може и O(N)), временска сложеност: O(NM).

Подзадатак 5

Чувајмо dp_i за сваки догађај i који је другог типа. Ту чувамо најбоље решење ако је Павле у том тренутку извукао најкраћу сламку. Како бисмо израчунали ову вредност потребно је да видимо одакле смо све могли да дођемо. Крећемо се уназад кроз догађаје и одржавамо интервал одакле смо могли да дођемо на позицију сламке коју је Павле извукао у догађају i, слично решењу првог подзадатка. Сваки пут када наиђемо на догађај j облика 2, ако је у интервалу од којег смо могли да дођемо, урадимо операцију dp_i = max(dp_i, dp_j+1). Крајње решење нам је максимум целог низа dp. Меморијска сложеност: O(M), временска сложеност: O(M^2+N).

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

Веома слично решењу подзадатка 4, идемо кроз дешавања једно по једно и одржавамо низ dp_i, за до сада пређене догађаје, које је најбоље решење, ако се тренутно најкраћа сламка налази на позицији i. Овај низ можемо одржавати по рекурентним везама из 4 подзадатка, користећи сегментно стабло са лењом пропагацијом, које има операције: нађи максимум на интервалу и постави цео интервал на неку вредност. Догађај један се покрива операцијом постави интервал на максимум на интервалу, док се догађај два покрива операцијом постави интервал [x, x] на вредност од dp_x+1. Меморијска сложеност: O(N), временска сложеност: O(MlogN+N).

Ксорко

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

N\leq10,A_i\leq1

Приметимо да има највише 2^{10} могућих комбинација (сваки број може бити 1 или 0). Сада напросто ручно бектреком претражимо сва могућа стања до којих можемо стићи обраћајући пажњу да ниједно стање не посећујемо више пута. Укупна сложеност O(2^N\cdot N).

N\leq10,A_i\leq63

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

N\leq3000

Приметимо следеће:
Нека су P[i] префиксни битовски ксорови низа A (значи P[i]=A[1]\text{ xor }A[2]\text{ xor }\cdots\text{ xor }A[i]). Сада ако извршимо операцију из текста задатка на елемент i, приметимо да то замени вредности P[i-1] и P[i]. Заиста, ако кренемо да рачунамо нове вредности

P'[i-1]=A[1]\text{ xor }A[2]\text{ xor }\cdots\text{ xor }A[i-1]\text{ xor }A[i]=P[i]
P'[i]=A[1]\text{ xor }A[2]\text{ xor }\cdots\text{ xor }A[i-1]\text{ xor }A[i]\text{ xor }A[i]=P[i-1]

док све остале вредности низа P[i] остају непромењене јер се дејство на елементе A[i-1] и A[i+1] скрати (или уопште не утиче).
Приметимо сада да можемо на произвољан начин да испермтујемо првих N-1 префиксних ксорова овог низа, и како за дати низ префиксних ксорова можемо на јединствен начин реконструисати низ (A[i]=P[i]\text{ xor }P[i-1]), такви низови који се добију тим пермутовањем префиксних ксорова су управо и једини низови које је могуће добити (одакле и следи да је највећи број различитих низова које могуће добити (N-1)!).
Сада кад смо ово уочили смо скоро па готови са овим подзадатком. Наиме, треба похлепно бирати пермутацију префиксних ксорова тако да се добије лексикографски највећи низ. У сваком тренутку прођемо кроз остале префиксне ксорове који су нам остали и напросто изаберемо онај који нам даје највећи ксор са претходно изабраним. Обратити посебну пажњу на последњи префиксни ксор, који се не може мењати. Сложеност O(N^2).

A_i\leq1

Са опсервацијама из претходног подзадатка, овде се може смислити релативно лако решење облика: похлепно узимамо алтернирајуће префиксне ксорове који су 1 и 0 алтернирајуће док нам неких не понестане.

A_i\leq15

Овај подзадатак (а и последњи), се ослања на то да се убрза похлепно тражење наредног члана у N\leq3000 решењу. Овде пошто нам је само битна вредност префиксног ксора, која је до 15, па онда је довољно да само имамо count низ који броји колико имамо које вредности међу префиксним сумама и онда прођемо кроз све могуће вредности следећег члана и изаберемо ону оптималну. Сложеност O(N\cdot\max A_i)

Пуно решење

Убацимо све префиксне ксорове у бинарни trie. Наиме, запишимо сваки тај број као његов бинарни запис тако да има тачно 60 цифара (са потенцијалним водећим нулама). Сада све те вредности убацимо у наш trie. Сада за тако припремљену структуру, могуће је врло брзо наћи елемент који са датим бројем x даје највећи ксор, тако што се спуштамо низ трие и похлепно бирамо да одемо у дете са супротном цифром, уколико постоји. Такође могуће је брзо избацити број из наше структуре.
Сада напросто изградимо ту структуру и идемо редом, и увек бирамо из ње онај елемент који са претходном вредношћу даје највећи могући ксор, а затим је избацујемо из исте.
Сложеност O(N\cdot\log \max A_i).

Два стабла

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

За P=0 сви упити су унапред познати па их можемо решавати у произвољном редоследу. Када је P=1 морамо да одговоримо на i-ти упит да бисмо сазнали i+1-ви упит, па задатак морамо да решавамо online, односно да на упите одговарамо редом којим су задати.

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

Искористимо DFS алгоритам да нађемо све чворове на једном и на другом путу и затим пребројмо колико чворова се налази на оба пута. Временска сложеност је O(QN).

Решење када су оба стабла ланци

Уз помоћ DFS алгоритма можемо да поређамо чворове оба стабла у два низа. Нека су то низови S и T. У овом случају се упити своде на питања за поднизове. Посматрајмо упит за подниз L1 \dots R1 низа S и подниз L2 \dots R2 низа T. Ако бисмо у низу T означили са 1 позицију i ако се T_i налази на поднизу L1 \dots R1 низа S, и са 0 у супротном, решење за упит би било збир ознака на поднизу L2 \dots R2 низа T.

За подзадатак када је N, Q \leq 3 \times 10^4, можемо да одржавамо ознаке у Фенвиковом стаблу и упите решавамо offline помоћу Мо-овог алгоритма. Упите сортирамо по пару (\lfloor frac{L1}{\sqrt{N}} \rfloor, R1) и решавамо их у том редоследу. Када решимо упит са поднизом L1_{i-1} \dots R1_{i-1} леву границу померамо до L1_i, а десну до R1_i, мењајући |L1_i-L1_{i-1}|+|R1_i-R1_{i-1}| ознака у низу T. На овај начин имаћемо O(N \sqrt{N}) промена и за сваку промену нам треба O(logN) времена за измену у Фенвиковом стаблу, па је временска сложеност овог решења O(N \sqrt{N} logN).

Када је N, Q \leq 2 \times 10^5 и P=0, решење је слично као претходно, али потребна нам је једна кључна опсервација: Решење за упит L1, R1, L2, R2 једнако је решење за 1, R1, L2, R2 минус решење за 1, L1-1, L2, R2. На овај начин можемо да раставимо упите на по два упита за које је подниз низа S заправо префикс истог. Ако упите сортирамо по десној граници подниза низа S, укупан број измена у Фенвиковом стаблу ће бити највише N. Временска сложеност овог решења је O(NlogN).

Када је P=1, можемо да применимо исто решење, али уместо Фенвиковог стабла треба да искористимо презистентно сегментно стабло како бисмо могли да сачувамо по верзију сегментног стабла за сваки од N префикса низа S, и касније их користили да одговарамо на упите у задатом редоследу.

Решење када је једно стабло ланац

У овом случају ланац можемо да претворимо у низ S и на њему радимо Мо-ов алгоритам или да раставимо упите као у прошлом решењу. Део решења који се мења је то да нам више нису потребни упити за збир на поднизу већ за збир на путу у стаблу. Пут од A до B у стаблу можемо да раставимо на пут од корена до A, плус пут од корена до B, минус пут од корена до \text{LCA}(A,B), минус пут од корена до \text{parent}(\text{LCA}(A,B)). Треба још да нађемо начин да добијемо збир ознака свих чворова на путу од корена до неког чвора. Урадимо Ојлеров обилазак стабла и сместимо чворове у низ тим редом како смо их посетили у DFS-у. На овај начин ће свако подстабло да чини један подниз. Током DFS-а можемо да запамтимо и границе поднизова за свако подстабло. Над низом који смо овако добили можемо да направимо Фенвиково стабло које подржава упите повећавања и смањивања вредности свих чланова неког подниза, и упите који враћају вредност неког чвора. Ако користимо Мо-ов алгоритам са овом структуром добијамо сложеност O(N \sqrt{N} logN), што пролази подзадатак када је N, Q \leq 3 \times 10^4, а ако раставимо поднизове низа S као у претходном подзадатку, добијамо решење у временској сложености O(NlogN) што пролази и подзадатак када је N, Q \leq 2 \times 10^5.

Reшење када је N, Q \leq 3 \times 10^4

Решење за овај подзадатак је да на једно стабло применимо Мо-ов алгоритам, а на друго стабло исту структуру података као у претходном решењу. Мо-ов алгоритам на стаблу заправо примењујемо на Ојлеровом обиласку. Направимо од стабла низ дужине 2N тако што ставимо чвор у низ када улазимо и када излазимо из чвора. Пут од A до B, где је прво појављивање чвора A пре првог појављивања чвора B, мапирамо на подниз од другог појављивања чвора A до првог појављивања чвора B, осим ако је A предак чвора B, када овај пут мапирамо на подниз од првог појављивања A до првог појављивања B. У првом случају се сви чворови на путу осим \text{LCA}(A, B) пјављују тачно једном, а остали чворови 0 или 2 пута. У другом случају сви чворови на путу од A до B се пајављују тачно једном, а остали чворови 0 или 2 пута. Када сортирамо упите, у структури за друго стабло одржавамо све чворове који се појављују тачно једном и пре решавања упита убацимо и чвор \text{LCA}(A, B) ако већ није убачен. Временска сложеност овог алгоритма је O(N \sqrt{N} logN).

Reшење када је P=0

Као што смо раставили пут у другом стаблу, тако можемо да раставимо и пут у првом стаблу. И у овом решењу на исти начин радимо са другим стаблом, а за прво стабло упите растављамо на по 4 упита за путеве од корена до неког чвора. Упите ћемо решити offline, DFS алгоритмом. Када уђемо у неки чвор додамо га у структури за друго стабло, затим решимо све упите за путеве од корена до тренутног чвора и на крају када изађемо из чвора избацујемо тренутни чвор из структуре за друго стабло. Временска сложеност овог решења је O(NlogN).

Решење за 100 поена

Online решење је слично као и offline решење, само што користимо перзистентно сегментно стабло уместо Фенвиковог стабла као структуру за друго стабло. На тај начин можемо да запамтимо верзије структуре каква је била након уласка у сваки чвор, и уз помоћ тога можемо редом да одговарамо на упите. Временска и меморијска сложеност овог решења је O(NlogN).