[Решења задатака] 2023/2024 СИО

Algoritam
1

Spartacus

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

N \leq 20

У овом подзадатку је довољно да испробамо свих 2^N могућих подскупова такмичара. За сваки могући подскуп проверићмо да ли је збир њихове контраверзе мањи од K и да ли за сваког такмичара i у том подскупу важи и да је p[i] (осим кад је p[i] = 0) такође у том скупу. Међу свим подскуповима у којима то важи уочимо онај са највећим збирним спартанством и испишемо ту вредност.

p[i] = i-1, за 1 \leq i \leq N

У овом подзадатку је јасно да ћемо моћи да изаберемо само првих неколико такмичара, да бисмо испунили услов затворености (ако изаберемо i, морамо да изаберемо и p[i]). Тако да је решење да сабирамо спартанства почев од првог такмичара докле год је њихова укупна контраверза мања од K. На крају испишемо збирно спартанство.

Сваки такмичар има различитог такмичара који би се јавио на њихову дисквалификацију

У овом подзадатку је кључно да такмичаре посматрамо као чворове у усмереном графу, а усмерена грана постоји између чворова i и p[i] за 1 \leq i \leq N. Како је p[1], p[2], \ldots, p[N] пермутација бројева 1,2,\ldots,N, закључујемо заправо да ће формиран граф бити унија неколико циклуса. Главна идеја, која ће служити и за наредне подзадатке, јесте да ако изаберемо једног такмичара из циклуса, онда морамо да их изаберемо све (јер ће се циклично јављати). Стога, потребно је уочити све циклусе и сваки циклус “компресовати” у по један чвор (један циклус такмичара можемо посматрати као једног такмичара чија су контраверза и спартанство једнаки збиру свих такмиара из циклуса). Сада задатак решавамо као познат проблем ранца.

Не постоји такмичар који би се поново јавио да је спартак након што је дисквалификован

Овај подзадатак је у неку руку супротан претходном, јер можемо закључити да нећемо имати циклусе. Сада имамо усмерено стабло и задатак решавамо динамичким програмирањем над стаблом. Нека је dp[i][j] решење за подстабло чвора i, уколико је збирна контраверза у подстаблу j. Прелаз ће нам затим бити $$dp[i][j + k[i]] = max(dp[i][j+k[i]], dp[i][j + k[i] - l] + dp[y][l])$$, где су y сва деца чвора i, а l вредност коју итерирамо од 0 до j. Почетно стање нам је наравно dp[i][k[i]] = s[i].

Решење без додатних ограничења

У овом подзадатку уклапамо идеје из претходна два. Потребно је да уочимо све циклусе и компресујемо их у један чвор, што нпр. можемо урадити Тарџановим алгоритмом. Затим примењујемо динамичко програмирање из претходнох подзатка.

2

Et tu, Brute?

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

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

Означимо са P(i,j) број вредности мањих k од 2^{K+1} таквих да је (i+j)\&k=(i\&k)+(j\&k). Лако можемо видети да је P(0,0)=P(0,1)=2^{K+1}, док се такође релативно лако види да је P(1,1)=2^K (само први и други бит утичу на решење, и они морају или оба бити активна или оба неактивна). Тако да нам је довољно да само нађемо број нула c_0 и број јединица c_1 и затим брзим степеновањем нађемо 2^{\frac{c_0(c_0+1)}{2}(K+1)+c_0c_1(K+1)+\frac{c_1(c_1+1)}{2}K}. Сложеност O(N).

Решење када је K=3

Овде имамо само 36 могућности за P(i,j) које је могуће или наћи ручно на папиру или програмом. Затим на сличан начин као горе, брзим степеновањем и низом који представља број појављивања сваког броја налазимо решење. Сложеност O(N).

Решење када је K\leq 8

У овом подзадатку поступамо слично као у претходном, само P(i,j) налазимо алгоритамски тако што тестирамо свако k. Затим опет решење налазимо као производ P(i,j)^{c_ic_j} и P(i,i)^{\frac{c_i(c_i+1)}{2}}, што можемо наћи брзим степеновањем. Решење O(N+K^3+K^2\log N).

Решење када је N\leq 1.000

Сада нам је потребан бржи начин за рачунање P(x,y). Запишимо x, y и x+y у бинарном запису дужине K+1 са водећим нулама. Нека су то а_{K+1}a_K\ldots a_1, b_{K+1}b_K\ldots b_1, и c_{K+1}c_K\ldots c_1 и посматрајмо једначину 0=(x\&k)+(y\&k)-((x+y)\&k). Ако је k_{K+1}k_{K}\ldots k_1 бинарни запис броја k вредност леве стране јединачине би била сума v_i=k_i(a_i+b_i-c_i)\cdot 2^i, а вредност a_i+b_i-c_i је у скупу \{-1,0,1,2\}. Посматрајмо највеће i тако да је v_i\neq 0. Уколико је v_i>0 знамо да је v_i\ge 2^i и v_j\ge-2^j за j\leq i, те је сума v_i позитивна што није могуће. Стога је v_i=-2^i. Ово је једино могуће уколико постоји пренос на позицији i-1 и a_i=b_i=0. Даље k_{i-1}\cdot(a_{i-1}+b_{i-1}-c_{i-1}),k_{i-2}\cdot(a_{i-2}+b_{i-2}-c_{i-2}),\ldots морају бити (до неке позиције) 1,1,1,1,1\ldots,2. Можемо индуктивно доказати да ако су до сад биле јединице, следећа цифра је или 1 или 2 (ако би била 0 или -1 онда због величине, слично претходном разматрању, k не би било решење). Уколико је 1 наставимо индукцију, уколико је 2 видимо да овај цео блок има величину 0 те можемо да га избацимо и разматрамо мање скупове. Сада смо добили вредности v_i у неком блоку k где сви k_i морају бити 1, па хајде да размотримо како то мора да изгледа за те битове за x,y. Neka je p_{K+1}p_{K}\ldots p_1 низ преноса. Лако се може видети (индукцијом, на пример) да ако је горњи блок од i до j онда мора да важи да је p_i=p_{i-1}=p_{i-2}=\ldots=p_{j+1}=1 и p_j=0. Већ смо видели да пошто је v_i негативан, мора да је a_i=b_i=0 i p_i=1 тако да је и p_{i+1}=0. Тако да блок кечева узетих у бинарном запису од k мора почињати од неког места где нема пренос и ићи до следећег места где нема пренос. Из претходног се може закључити да уколико поделимо низ p на блокове облика 1111\ldots110, ако узмемо један елемент из тог блока морамо да узмемо цео блок, а лако се може видети да је сума у свако блоку 0, без обзира да ли смо узели све нуле или све јединице. Стога је P(i,j)=2^{\text{број таквих блокова}}, односно P(i,j)=2^{\text{број позиција у где нема пренос}}, тако да га можемо лако израчунати за сваки пар и помножити. Сложеност O(N^2K).

Решење када је N\leq 100.000

Уколико је A одговор који тражимо, приметимо да је \log_2(A) број тројки (i,j,k) тако да a_i+a_j нема пренос на позцији k. Ако фиксирамо k, да бисмо нашли број парова који немају пренос на тој позицији, можемо да узмемо низ по модулу 2^k (и добијемо низ b_i) и онда нам треба број парова тако да је b_i+b_j<2^k, што се може урадити сортирањем и бинарном претрагом. Затим само нађемо решење брзим степеновањем. Сложеност O(NK\log N).

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

У претходном решењу, фактор \log N у решењу долази из две ствари: сортирања и бинарне претраге. Пошто је низ сортиран, бинарну претрагу можемо лако заменити техником два показивача да би радило у O(N) у свакој од K итерација. Сортирање свакако захтева N\log N времена, али је трик да следећи сортиран низ можемо добити од претходног. Заиста, у прелазу k\rightarrow k+1 сваки b_i или остане исти или или се повећа за 2^k. Сви који су се повећали постају већи од свих који нису, а осталима паровима релативни поредак остаје исти. Стога ако у сваком тренутку памтимо и од ког елемента је неки b_i “потекао” лако можемо израчунати нови низ, и користити то што нам је тренутни већ сортиран да бисмо сортирали нови у линеарном времену (прођемо кроз низ двапут и први пут издвојимо оне које се нису повећали а у другом оне који јесу). Ово је у суштини алгоритам сортирања “radix-sort”. Сложеност O(NK).

3

E pluribus unum

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

Нека је одговор за датог миксотрофа T. Приметимо да је њему оптимално да буде аутотроф од дана 0 до дана T-1. Тек у дану T изабере да се храни хетеротрофно, и тад одједном поједе све остале бактерије. Ово важи јер ако у првом дану када одлучи да се храни хетеротрофно не поједе све остале бактерије, мора још дана да чека. Ово му касније онемогућава да добија на величини на бактеријама које је већ појео (само непоједене бактерије које се хране аутотрофно могу нарасти). Дакле, више ће нарасти ако се у том првом дану хранио аутотрофно.

Први подзадатак

За сваку бактерију, могуће је бинарно претражити одговор. Креирајмо граф и израчунајмо нове величине након претпостављених T_i тренутака. Тренутна бактерија i у сваком тренутку бира најмањег суседа и поједе га. Уколико не може да поједе ни најмањег суседа, онда провера пада. Ако може појести све остале бактерије, онда провера пролази. Најмањи сусед се може наћи преко приоритетног реда. Временска сложеност је O(NM(\log N)^2).

Други подзадатак

Потребно је брже наћи одговор за сваку бактерију. Када је у питању низ, можемо користити бинарну претрагу по вредности решења и памтити тренутну границу [l_i,r_i] коју је бактерија i појела. Уколико су бактерије l_i -1 и r_i+1 веће од тренутне величине i, провера пада. Иначе, појешће највећи број узастопних бактерија које може појести улево, и највећи такав број удесно. Те границе је могуће наћи бинарном претрагом по префиксној суми низа. Приметимо да се након две симулације ових корака величина бактерије порасте барем дупло, те је број корака O(\log S), где са S означавамо збир величина свих бактерија на почетку. Ово даје укупну временску сложеност O(N(\log N)^2 \log S).

Трећи подзадатак

Могуће је елиминисати бинарну по решењу. Провера остаје иста, с тим што у њу убацујемо “предомишљање”. За тренутну бактерију симулирамо процес и претпоставимо њено почетно оптимално време са T_i=0. Кад год наиђемо на ситуацију где она не може више нарасти, “предомислимо” се и поставимо T_i на најмању вредност која би јој дозволила да поједе бар једног суседа. Како је ипак оптимално да бактерија чека до тог првог тренутка, потребно је одговарајуће ажурирати њену тренутну величину рачунајући да ће јој тренутно поједене бактерије донети допринос. Ово је могуће решити правилно постављеним математичким формулама. Сложеност је O(N\log N \log S).

Четврти подзадатак

Приметимо да ако бактерија може појести све остале у неком тренутку, то ће урадити најкасније у тренутку 20. Ту константу бирамо јер је то највећа величина бактерије у овом подзадатку. Фиксирајмо неки универзални тренутак 0 \leq T \leq 20. Одједном проверавамо које бактерије могу појести све остале, а које не могу. Аналогно са прошлим подзадатком, уместо повезаних сегмената памтимо повезане компоненте. Њих је могуће одржати преко уније дисјунктних скупова (DSU). Компонента може појести другу ако им укупне величине то дозвољавају. За сваку је потребно памтити и скуп (vector) бактерија које могу појести све остале у тој компоненти (очито се може десити да само неке имају ту способност, и све које то могу ће имати исту величину на крају). Ако правилно радимо спајање мање компоненте у већу, имамо решење сложености O(N T \log N). Овде T представља најкаснији смислени тренутак.

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

Комбинујемо идеје из претходна два подзадатка. Одржаваћемо унију дисјунктних скупова (DSU) са “предомишљањем”. Унутар компоненте, за сваку бактерију синхронизовано памтимо њен тренутни најмањи претпостављен тренутак. Приметимо да им се величине због различитих времена разликују, али да ће најмања бактерија управо бити она са најмањим претпостављеним тренутком. Приликом спајања две компоненте, потребно је дозволити и најмањој бактерији да поједе одговарајућу суседну бактерију. Ако је потребно, ту вршимо “предомишљање” применом одговарајуће математичке формуле. Пошто нам је потребно тражење минимума и вршење промена у колекцији, мораћемо да користимо структуру података (попут приоритетног реда). Након два “предомишљања”, величина бактерије се дуплира. Овим је број таквих, за једну бактерију, ограничен са O(\log S). Иако при једном спајању можемо извршити велик број операција, претходно увиђање нам амортизује сложеност, те је укупна O(N(\log N)^2 + N\log S).

Бонус

Решити задатак у сложености O(N(\log N + \log S)).

4

Quaestio militaris formationis

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

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

Напросто за сваку од N! пермутација можемо израчунати колико инверзија дају. Сложеност O(N^2N!).

Решење када није потребно наћи низ слабости

Нека дефинишимо дистанцу d две прермутације p,q као најмањи број замена суседних елемената да би се стигло од једног до другог. Ако id означава пермутацију идентитете, знамо да је d(id,p) заправо број инверзија пермутације p. Такође једна тривијална опсервација је да је d(p,q)=d(r\circ p,r\circ q) јер у овом случају само мењамо i са r[i] у обе пермутације, што очигледно никако не мења проблем. Означимо са r^{-1} инверзну пермутацију пермутације r. За дате пермутације p и q, нама је потребна минимална вредност \max\{d(id,r\circ p),d(id,r\circ q)\} по свим r, односно \max\{d(r^{-1},p),d(r^{-1},q)\}. Пошто је очигледно d(p,r^{-1})+d(r^{-1},q)\ge d(p,q) (можемо да добијемо q од p тако што прво добијемо r^{-1} у минималном броју потеза па онда одатле q у минималном броју потеза), знамо да је тражена вредност барем \lceil\frac{d(p,q)}{2}\rceil. Међутим, ову вредност је могуће добити, просто узмемо најкраћи низ замена суседних који води од p до q и онда кад смо на пола тога станемо и прогласимо ту пермутацију за r^{-1} (и одатле пронађемо r). Сада нам је потребна само вредност d(p,q)=d(id,p^{-1}q) што је само број инверзија ове пермутације и лако се може наћи у O(N^2) провером по свим паровима, или O(N\log N) стандардним начиним преко Фенвиковог стабла.

Решење када је N\leq 3000

Тражимо пермутацију a=p^{-1}r^{-1} тако да је \max\{d(id,a),d(a,p^{-1}q)|\}=\lceil\frac{d(p,q)}{2}\rceil, из чега ћемо лако конструисати шта је r. За ово је потребно да изаберете ваш омиљени алгоритам сортирања који ради у квадратном времену и ради тако што само мења суседне елементе ако су у инверзији (на пример “bubble sort”), кренете да сортирате пермутацију p^{-1}q и станете на пола. Сложеност O(N^2).

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

Решење ћемо наћи налажење погодног квадратног алгоритма, чије бројање инверзија можемо да симулирамо брже од квадратног. Стандардно тражење броја инверзија преко Фенвиковог стабла ће нам после i-тог потеза наћи број инверзија у префиксу дужине i. Међутим, ово је управо број инверзија који је извршио “insertion sort” када је завршио са i-тим елементом, а овај сорт је један од оних који мења само суседне који су у инверзији. Тако да можемо да радимо рачунање броја инверзија пермутације p^{-1}q стандардним алгоритмом Фенвиковим стаблом, и кад се деси да број инверзија пређе половину свих инверзија, сортирамо тај префикс, и онда урадимо са i-тим тачно онолико замена колико нам треба да би дистанца била тачно пола. Сложеност O(N\log N).

5

Viae Romanae

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

Решење када је M \leq 15 , Q \leq 1.000

Симулирамо одабир свих парова путева. Сложеност овог решења је O(Q \cdot 2^N).

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

Нека је T(u) скуп чворова v таквих да сваки најкраћи пут од 1 до u пролази кроз v. Приметимо да овакав скуп можемо пронаћи избацивањем сваког чвора из графа и проверавањем да ли се повећало растојање до чвора u. Приметимо да је решење управо |T(X[i]) \cap T(Y[i])|. Овакве скупове је могуће пронаћи коришћењем Дијкстриног алгоритма. За сваки упит, можемо да пронађемо T(X[i]) и T(Y[i]) и потом њихов пресек. Сложеност овог решења је O(Q \cdot N \cdot M \log M).

Решење када је N, M \leq 2.000, Q \leq 5.000

Потребно је да оптимизујемо решење претходног задатка тако што ћемо пронаћи скупове T(u) пре одговарања на упите. Сложеност овог решења је O(N \cdot M \log M + N \cdot Q).

Решење када је N, M \leq 3.000

Овај подзадатак има два решења. Можемо оптимизовати претходни коришћењем битсета. За алтернативно решење, које наводи на решење целог задатка, можемо приметити да скупови T формирају структуру стабла. Наиме, за свако u, постоји јединствено v \in T(u) тако да T(u) = T(v) \cup \{u\}. Означимо такво v са p(u) и формирајмо стабло у којем је родитељ чвора u управо p(u). Одговор на упит је дубина најдубљег заједничког претка (LCA) чворова X[i] и Y[i]. Сложеност овог решења је O(N \cdot M \log M + Q \log N).

Решење када M = N - 1 и сваки град је повезан са највише 2 пута

Граф можемо представити као низ. Одговор на упит је величина пресека два интервала. Сложеност овог решења је O(N + Q).

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

Одговор на упит је дубина најдубљег заједничког претка (LCA) чворова X[i] и Y[i]. Сложеност овог решења је O(N \cdot M \log M + Q \log N).

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

За цело решење морамо да оптимизујемо процес конструкције стабла из четвртог подзадатка. Приметимо да стабло можемо да конструишемо паралелно са извршавањем Дијкстриног алгоритма. Нека је чвор који процесирамо у неком кораку управо u. Нека је S(u) скуп чворова v таквих да је грана v - u на неком најкраћем путу од 1 до u. Приметимо да је тада p(u) = LCA(S(u)), где је LCA(X) најдубљи заједнички предак свих чворова из скупа X. Приметимо да смо све чворове из скупа S(u) већ обрадили. Према томе, можемо да додамо чвор u у стабло, као дете чвора p(u) и да ажурирамо LCA табелу. Сложеност овог решења је O(M \log M + Q \log N).

6

Turris inclinata

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

Решење када N\le20, Q\le 50, P[i]=2

У овом подзадатку можемо да симулирамо процес пењања на торањ. Сложеност O(Q \cdot 2^N).

Решење када N\le2.500, Q\le 20

Приметимо прво да чим први пут пређемо неки спрат успешно, то значи да на свим спратовима до њега имамо 0 покушаја по модулу одговарајућег спрата. Сваки упит решавамо независно. Нека је dp[i] потребан укупан број покушаја да пређемо i-ти спрат, уколико на свим мањим имамо 0 неуспешних покушаја. Тада је dp[i] = dp[j] + dp[j+1] + ... + dp[i-1], где је j = max(X, F[i]). Коначно решење је dp[X] + dp[X+1] + ... + dp[N]. Сложеност овог решења је O(N^2 \cdot Q).

Решење када је N\le300.000, Q\le 20

Сваки упит решавамо независно. Приметимо да можемо оптимизовати решење претходног подзадатка коришћењем префиксних сума. Сложеност овог решења је O(N \cdot Q).

Решење када је F[i]\ge i-10

Нека је pref[i] = dp[1] + dp[2] + ... + dp[i]. Приметимо да je решење линеарна комбинација pref[X-1], pref[X+1], pref[X+2], ..., pref[X+10]. Можемо да процесирамо вредности X опадајуће и ажурирамо коефицијенте ове линеарне комбинације. Сложеност овог решења је O(N + Q).

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

Приметимо да можемо да симулирамо процес од последњег спрата. За сваки спрат памтимо колико смо пута морали да га пређемо. Иницијализујмо ову променљиву на 1 за сваки спрат и означимо је са T[i]. Последњи спрат морамо да пређемо тачно T[N] = 1. Међутим, пошто ћемо направити P[N]-1 неуспешних покушаја, ово значи да смо све спратове од F[N] до N-1 морали да пређемо барем још P[N] - 1 пута више, тј. T[i] се повећава за P[N] - 1 за све F[N] \leq i \leq N-1. Према томе претпоследњи спрат смо морали да пређемо T[N-1] = 1 + (P[N] - 1). Међутим, пошто смо направили P[N-1] - 1 неуспешан покушај за сваки успешан, ово повећава T[i] за T[N-1] \cdot (P[N-1] - 1) за F[N-1] \leq i \leq N-2. Ово повећавање можемо симулирати додавањем вредности за колико треба променити префикс на одговарајући елемент или коришћењем сегментног стабла. Коначно, одговор на упит је T[X] \cdot P[X] + T[X+1] \cdot P[X+1] + ... + T[N] \cdot P[N]. Ову суму можемо ефикасно пронаћи коришћењем суфиксних сума. Сложеност овог решења је O(N + Q).