[Решења задатака] 2022/2023 СИО - дан 1

Algoritam
1

Операција над глистом

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

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

Приметимо да су операције раздвајања и спајања узајамно инверзне
(тј. иверзне једна другој), тако да ако нека два дела спојимо, никад их више нећемо раздвајати.
У последњем потезу знамо да морамо да спојимо два дела који имају једнаке дужине, или два дела од којих је леви за један краћи од десног (тј. дужине делова су \left\lfloor\frac{S}{2}\right\rfloor и \left\lceil\frac{S}{2}\right\rceil, где је S укупна дужина глисте). Због тога треба да постоји индекс k, тако да је сума дужина првих k делова једнака \left\lfloor\frac{S}{2}\right\rfloor, а сума дужина преосталих делова износи \left\lceil\frac{S}{2}\right\rceil. Ако не постоји такав индекс k, онда се одређује индекс k тако да је

\sum_{i=1}^{k-1} a_i< \left\lfloor\frac{S}{2}\right\rfloor \quad \text{и} \quad \sum_{i=1}^{k} a_i > \left\lceil\frac{S}{2}\right\rceil.

Након тога се део са индексом k дели све док се не добије низ у коме постоји индекс l, такав да је

\sum_{i=1}^{l} a_i = \left\lfloor\frac{S}{2}\right\rfloor.

То постижемо тако што сваки пут делимо део са индексом k'
за који важи

\sum_{i=1}^{k'-1} a_i < \left\lfloor\frac{S}{2}\right\rfloor \quad \text{и} \quad \sum_{i=1}^{k'} a_i > \left\lceil\frac{S}{2}\right\rceil.

Када добијемо низ делова (који има n' делова) за који постоји индекс l такав да је

\sum_{i=1}^{l} a_i = \left\lfloor\frac{S}{2}\right\rfloor.

онда рекурзивно позивамо функцију која одређује минимални број операција потребан да се споје првих l делова у један део и фунцију која одређује минималан број операција потребан да се споји последњих n'-l делова у један део. На крају два тако добијена дела ћемо спојити у један део. Укупан број операција је једнак збиру броја операција дељења на почетку функције, броју операција за спајање леве половине, броја операција за спајање десне половине и броја 1 за спајање два добијена дела (половине).

Значи, за решавање задатка смо искористили технику подели па владај (divide\ and\ conquer). Приметимо да је сложеност једног рекурзивног позива (односно припреме за рекрзивне позиве током извршавања тог рекурзивног позива) {\mathcal O}(S), а да се рекурзивно позива функција за низове у којима је сума дужина делова \frac{S}{2}, па је по мастер теореми сложеност комплетног функције {\mathcal O}(S\log S).

2

Компресовани низ

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

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

У овом подзадатку можемо тестирати сваки могући низ примене операција. За дато K имамо N-K+1 = (N - (K-1)) опција за примену прве операције. После првог корака, број елемената се смањи за K-1, па у другом кораку имамо N-2\cdot(K-1) опција. Укупно, постоји (N-(K-1)) \cdot (N-2\cdot(K-1)) \cdot ... \cdot ( (K-1) + (N\mod(K-1))) различитих секвенци операција које резултују низом дужине мање од K. Претходни производ је ограничен са (N-1)!, па је сложеност овог решења O(N!).

Решење када K \leq 3 и N \leq 100.000

За наредне подзадатке морамо мало детаљније анализирати како примене операција утичу на низ. За овај подзадатак, довољно је приметити да су елементи крајњег низа заправо компресовани блокови узастопних елемената у почетном низу. Ти блокови узастопних елемената имају дужину 1 \mod (K-1), што је лако показати. Наиме, у почетном низу блокови имају дужину 1. Сваком даљом компресијом се K таквих блокова спаја у један блок, који по модулу K-1 има дужину K \cdot 1 = K = 1 \mod (K-1). Коначно, за овај подзадатак можемо да анализирамо два слулчаја:

  • K=2 - тада крајњи низ има дужину 1, а вредност тог елемента је \textbf{or} вредности свих елемената у почетном низу
  • K=3 - тада крајњи низ има дужину 1 уколико је N непарно и 2, уколико је N парно. Уколико је N непарно, тада је вредност јединог елемента \textbf{or} вредности свих елемената у почетном низу. Коначно, уколико је N парно, можемо да итерирамо по завршетку првог блока, који се завршава на неком непарном индексу у почетном низу и да посматрамо префиксни и суфиксни \textbf{or} елемената почетног низа. Решење задатка је минимум њихове суме.

Решење када N \le 3.000

Овај и наредне подзадатке решавамо динамичким програмирањем. Вредност dp[i] ће представљати минималну вредност суме уколико се ограничимо искључиво на првих i елемената низа. Прво морамо приметити да је услов да се операције примењују све док низ има довољно елемената суштински неважан. Наиме, применом операције се сума елемената низа не може повећати, те је свакако увек боље применити што више операција. За сваку позицију i, итерирамо по завршној позицији претходног блока. Рекурентна формула за наше динамичко програмирање је \min_j (dp[j] + A[j+1] \textbf{ or } A[j+2] \textbf{ or } ... \textbf{ or } A[i]), где је i - j = 1 \mod (K-1) (јер према опсервацији из претходног подзадатак важи да је дужина сваког блока 1 \mod (K-1)). Уколико одржавамо вредност A[j+1] \textbf{ or } A[j+2] \textbf{ or } ... \textbf{ or } A[i], док итерирамо по j, добијамо решење сложености O(N^2).

Решење када су све вредности у низу A су 1 или 2 и N \le 100.000

И у овом подзадатку поново посматрамо блокове. Сваки блок има вредност 1, 2 или 3. Међутим, блок који се завршава на некој позицији i може да има само две вредности, а то су A[i] и 3 (нпр. уколико i-ти елемент има вредност 1, блок који се завршава на позицији i никако не може да има вредност 2 и обрнуто). За сваку крајњу позицију, фиксирамо једну од те две могуће вредности последњег блока и посматрамо све могуће стартне позиције тренутног блока. За њих можемо да одржавамо минимум користећи неку структуру података, на пример set.

Решење када N \le 100.000

Решење овог подзадатка представља надоградњу на решење подзадатка у којем су све вредности у низу A једнаке 1 или 2. Можемо да приметимо да постоји највише \log_2 \max_i A[i] \leq 30 могућих различитих вредности блока који се завршава на позицији i за свако i. Сада можемо да фиксирамо једну од тих вредности и пронађемо најранију позицију (означимо ту позицију са j) на којој је тренутни блок могао да почне да би имао ту вредност. Затим, користећи неку структуру, нпр. set пронађемо минимум вредности dp-ова претходног блока од позиције j па до i. Ово можемо да реализујемо користећи set на следећи начин. Можемо да чувамо K-1 set-ова, један за сваку крајњу позиција модуо K-1. У сваком од њих можемо да чувамо вредности dp-ова сортирано по индексу. Коначно када убацујемо dp[i] у set који одговара модулу i \mod (K-1), треба да избацимо све оне које који се појављују пре њега, а имају већу вредност од dp[i]. Када тражимо минимум од позиције j до позиције i, можемо да позовемо уграђену функцију lower_bound, да би пронашли први индекс већи од j који постоји у одговарајућем set-у. Сложеност овог решења је O(N \log N \log \max_i A[i]).

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

За главно решење и последњи подзадатак, довољно је оптимизовати сложеност на O(N \log \max_i A[i]). Ово се може постићи на пример тако што заменимо set са спарс табелом.

3

Најслабија карика

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

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

Приметимо да сваки низ који добијемо на крају је подсеквенца почетног, па за дати низ постоји највише 2^N могућих подсеквенци и за сваку можемо грамзивим алгоритмом да проверимо да ли се заиста може добити описаним операцијама. O(Q2^NN)

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

За сваки подзадатак надаље ћемо морати да се удубимо у концепт Декартовог стабла низа. Наиме, то је бинарно стабло које се конструише рекурзивно (у квадратном времену) на следећи начин: нека је i индекс максимума у нашем низу, онда је чвор i корен нашег стабла. Затим, поделимо низ на два низа 1,2,\cdots,i-1 i i+1,i+2,\cdots,N и нађемо Декартово стабло од ова два подниза, чијим качањем на корен i као лево и десно дете, редом, ћемо добити Декартово стабло целог низа. Сада може се приметити да је могуће уклонити неки члан низа акко смо већ уклонили цело његово подстабло у Декартовом стаблу. Стога је задатак заправо еквивалентан са тражењем броја начина како можемо да изаберемо неколико дисјунктних подстабала Декартовог стабла датог низа. Ово се решава простим динамичким програмирањем на стаблу. Ако су l и r деца чвора u, онда можемо да срачунамо dp[u]=dp[l]\cdot dp[r]+1. O(QN^2)

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

Овај подзадатак се ради слично као и претходни, само је потребно да се брже изгради Декартово стабло. Ово може да се уради, на пример, тако што се за сваки елемент низа нађе први елемент лево и десно већи од њега (преко такозване “стек форе”), и онда је његов родитељ у Декартовом стаблу управо мањи од та два броја. O(NQ)

Решење када сваки упит садржи максимум

Надаље је јасно да је кључни проблем како брзо налазити Декартово стабло за подниз или бар довољно информација о том Декартовом подстаблу. Ако интервал садржи M чији је индекс i онда је јасно да је довољно решити задатак само за [L,i] и [i,R] одвојено, након чега лако налазимо решење укупно. Сада ћемо рачунати одговор за сваки интервал облика [i,R] неком врстом динамичког програмирања, где ћемо се позивати на вредности које смо срачунали динамичког програмирања за цео низ (ако бисмо прво решили задатак за цео низ као у претходном подзадатку). Наиме нека је last[R] највећи индекс броја већег од оног на позицији R. Ако је last[R]=i, потребно нам је само решење за интервал [i+1,R-1]. Уколико није, онда је решење једнако решењу за last[R], али треба да му додамо још производ решења за [last[R]+1,R-1],\cdots, [last^k[R]+1, last^{k-1}[R]-1] (у каснијим подзадацима ћемо видети тачан разлог овоме). Међутим, сва ова решења потпроблема која нам требају су заправо већ израчунати у Декартовом стаблу, тако да већ за те интервале знамо да решимо проблем и комбиновањем свега тога можемо решити овај подзадатак.

Решење када је пермутација насумична

Инспирисани претходним подзадатком, јасно је да се некако све врти око максимума на интервалу L,R, тако да би било лепо када бисмо нашли везу максимума на интервалу и Декартовог стабла. Није тешко уверити се да је најмањи заједнички предак од L i R заиста максимум на интервалу [L,R]. Међутим, сада долази питање, како тачно изгледа то Декартово стабло подниза, и да ли можемо да га изразимо преко Декартовог стабла почетног низа. Испоставља се да можемо, и то на следећи начин: кренимо од чвора L и његовог десног подстабла. Сада идемо путем од L до LCA(L,R): ако дођемо у неки чвор из левог детета, онда тај чвор избацујемо, а чвор из ког смо дошли преспојимо са његовим дедом. Ово исто радимо са R, само заменимо речи “лево” и “десно”. Уверите се сами да оваква конструкција ради!! Како је пермутација рандом генерисана, заправо можемо да тврдимо да је Декартово стабло дубине реда величине O(\log N), па овакву симулацију можемо да вршимо у О(Q\log N), као и онда прерачунавање вредности динамичког програмирања за тих O(\log N) нових вредности по упиту.

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

Сада треба некако избећи ручну симулацију прављења новог Декартовог стабла, када не знамо да је оно плитко. Ово ћемо радити, наравно, путем *sparse tabela. Наиме за сваки чвор ћемо приметити да нам је операција која се примени на тренутну вредност dp бити облика линеарна облика dp ->dp\cdot x+c. Шта мислимо под овиме? Па ако имамо вредност dp[l], онда налазимо вредност за dp[u]=dp[l]\cdot dp[r]+1, значи трансформацију од dp[l] у dp[u] имамо по горњој формули за k=dp[r], c=1. Међутим, оно што је важно приметити је да је композиција две операције овог типа опет операција тог типа (композивција две линеарне функције је опет линеарна). Тако да ми у спарсе табели можемо наћи како изгледа формула за dp[2^k\text{-ти предак од }u] преко dp[u]. Оно што још важи је да је x\cdot1+0, неутрал за операцију композиције функције. Онда налазимо решење на следећи начин: имамо две табеле, једна која кад идемо на горе од неког чвора кад уђемо слева множи резултат са вредности dp од десног детета и додаје 1, а ако улази сдесна онда не ради ништа и друга која ради обрнуто. Није тешко видети да се на овај начин ако кренемо од L до LCA(L,R) управо рачуна решење проблема за тај подинтервал, а такве операције су све линеарне, па сваку од њих можемо претворити у спарс табелу, која нам дозвољава брзо рачунање решења за тај подинтервал. Затим радимо то за десну страну и спајамо решења као у подзадатку 4. Сложеност O(Q\log N).