# \[Rešenja zadataka\] 2021/2022 Kvalifikacije - Treći krug

**URL:** <https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077>\
**Category:** Algoritam\
**Created:** [January 31, 2022, 10:15pm UTC](https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077 "2022-01-31T22:15:23Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![MladenP](https://algora.petlja.org/user_avatar/algora.petlja.org/mladenp/32/53_2.png) [@MladenP](https://algora.petlja.org/u/MladenP)\
**Post date:** [January 31, 2022, 10:15pm UTC](https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077/1 "2022-01-31T22:15:23Z")

</div>

# Биодиверзитет

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

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

Како је циљ одредити број различитих биолошких предака врста које тренутно живе, а будући да су у задатку дати индекси врста које тренутно живе, најпре је потребно приступити израчунавању индекса биолошких предака. То се чини тако што се индекс врсте i целобројно подели са K и то за све индексе i\_1, i\_2, \ldots, i\_N у задатом низу. Тиме се добија нови низ који заправо представља низ биолошких предака. Треба приметити да се у општем случају вредности унутар низа билошких предака могу понављати. Најзад да би се одредио број различитих предака потребно је пребројати јединствене чланове низа који садржи и дупликате. Постоји више начина на који је могуће израчунати број јединствених чланова низа, а један од њих је да се чланови низа биолошких предака сортирају и онда у једном пролазу кроз низ изброје различите вредности.

У решењу, поред операција пролаза кроз низ у којима се извршава целобројно дељење или пребрајање јединствених чланова, а које су линеарне сложености \mathcal{O}(N), такође имамо и операцију сортирања која је доминантне сложености. Користећи се ефикасним алгоритмима низ је могуће сортирати у логлинеарној временској сложености \mathcal{O}(N\log N), иако је за максималан број поена то било довољно учинити и у квадратној, односно \mathcal{O}(N^2) сложености.

---

<div class="post-metadata">

**Author:** ![MladenP](https://algora.petlja.org/user_avatar/algora.petlja.org/mladenp/32/53_2.png) [@MladenP](https://algora.petlja.org/u/MladenP)\
**Post date:** [January 31, 2022, 10:15pm UTC](https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077/2 "2022-01-31T22:15:50Z")

</div>

# Млађионичар

Аутор: Андреј Ивашковић Текст и тест примери: Димитрије Ердељн Тестирање: Андреј Ивашковић Анализа решења: Драган Урошевић

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

A \leq g+b+1,\quad B \leq r+b+1, \quad C \leq r+g+1.

Поред тога је укупан број куглица једнак N, па важи:

r+g+b = N.

### Решење кад је N \leq 200

У овом случају, можемо за све могуће вредности бројева r, g и b (а то су природни бројеви између 1 и N), проверити да ли задовољавају три неједнакости и последњу једнакост и прекинути проверавање оног тренутка када су задовољене. Ако поменуте неједнакости и једнакост нису задовољени ни за једну комбинацију вредности r, g и b, не постоји распоред куглица који одговара вредностима A, B и C. Очигледно је сложеност овог решења O(N^3).

### Решење кад је N \leq 2000

Приметимо да за фиксиране вредности броја црвених (r) и зелених (g) куглица можемо одредити број плавих куглица по формули b=N-r-g. Због тога је довољно за све комбинације вредности бројева r и g (а то су бројеви између 1 и N), одредити вредност броја b, а након тога проверити да ли су задовољене три неједнакости.  
Сложеност овог решења O(N^2).

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

Како у врећи треба да буде бар једна црвена, зелена и плава, бројеве куглица можемо приказати као

r = 1 + r1,\quad g = 1+g1, \quad b = 1+b1,\quad r1,g1,b1\geq 0.

Тада ваши следеће:

r1+g1+b1 = (r-1) + (g-1) + (b-1) = (r+g+b)-3 = N-3 = N1.

Поред тога, полазне неједнакости постају:

A\leq g+b+1 = (1+b1)+(1+b1)+1 = g1+b1+3,

односно

g1+b1 \geq A-3,

или прецизније

g1+b1 \geq \max(A-3,0) = A1.

Слично се добија

r1+b1 \geq \max(B-3,0)=B1

и

r1+g1 \geq \max(C-3,0) = C1.

Сабирањем последње три неједнакости добијамо

2r1+2g1+2b1=2N1\geq A1+B1+C1,

и ово је потребан услов да би постојало решење.

Показује се да је то и довољан услов. Да би одредили решење, приметимо да из услова

r1+g1+b1 = N1\quad\text{и}\quad g1+b1\geq A1,

добијамо

r1 = N1-(g1+b1) \leq N1-A1 = r1\_{max},

и слично:

g1 \leq N1-B1= g1\_{max}\quad\text{и}\quad b1 \leq N1-C1=b1\_{max}.

За бројеве r1, g1 и b1 бирамо највеће који задовољавају неједнакости и у збиру дају број N1.  
Приметимо да се могу одабрати бројеви r1, g1 и b1 тако да задовољавају горње неједнакости и збир буде N1 зато што је збир горњих ограничења

r1\_{max}+g1\_{max}+b1\_{max} = (N1-A1)+(N1-B1)+(N1-C1) = 3N1 - (A1+B1+C1) \geq 3N1 - 2N1 = N1.

Коначно, саме вредности можемо изабрати на следећи начин:

r1 = \min(N1,N1-A1),\quad g1 = \min(N1-r1, N1-B1),\quad b1=\min(N1-r1-g1,N-C1).

Сложеност овог решења је O(1).

---

<div class="post-metadata">

**Author:** ![MladenP](https://algora.petlja.org/user_avatar/algora.petlja.org/mladenp/32/53_2.png) [@MladenP](https://algora.petlja.org/u/MladenP)\
**Post date:** [January 31, 2022, 10:16pm UTC](https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077/3 "2022-01-31T22:16:31Z")

</div>

# Психо

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

### Решење за N, M \leq 1000

Овде је могуће применити разна спорија решења, нпр. можемо одржавати скуп _активних_ визит карти, односно оних које нису још одбачене или сачуване од стране директора. Сваког тренутка, све активне визит карте шаљемо надређеном и онда симулирамо поређење визит карти. Временска сложеност: O(N\cdot M), меморијска сложеност: O(N+M).

### Решење за p\_i = i-1

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

Ово нам говори да је довољно да за сваки тренутак одредимо колико визит карти стиже код директора тад. Карта која се појавила у тренутку t\_i код особе p\_i ће код директора стићи у тренутку t\_i+p\_i-1, па користећи нпр. структуру _map_ или обично сортирање, одредити све што нам је потребно да израчунамо колико карата ће бити одбачено (уколико у тренутку t стиже x карата код директора, тада он одбацује \lfloor \frac{x}{2} \rfloor \cdot 2 визит карти. Временска сложеност: O(N+MlogM), меморијска сложеност: O(N+M).

### Решење за t\_i = 1

Решење је слично главном решењу, само што је могуће избећи мапу/сортирање, и лакше је приметити погребу за дубинама запослених.

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

Попут решења када p\_i = i-1, игноришемо поређења сем код директора. Једина разлика је што овај пут морамо другачије да израчунамо у ком тренутку ће се нека карта наћи код директора. Потребно је да израчунамо _дубину_ сваког запосленог, односно колико је секунди потребно да визит карта од особе i стигне до директора (означимо то са d\_i).

За ово је могуће користити графовске алгоритме, али пошто важи p\_i \< i то није неопходно. Довољно је да то урадимо користећи следеће формуле: d\_1 = 0  
и d\_i = d\_{p\_i} + 1. Када то израчунамо, време када ће нека карта доћи до директора је t\_i + d\_{v\_i}. Временска сложеност: O(N+MlogM), меморијска сложеност: O(N+M).

---

<div class="post-metadata">

**Author:** ![MladenP](https://algora.petlja.org/user_avatar/algora.petlja.org/mladenp/32/53_2.png) [@MladenP](https://algora.petlja.org/u/MladenP)\
**Post date:** [January 31, 2022, 10:17pm UTC](https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077/4 "2022-01-31T22:17:03Z")

</div>

# Коњугација

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

Можемо за сваки пар сегмената проверити у константној сложености да ли су коњуговани - сложеност овог алгоритма је О(N^2), што је довољно за **Подзадатак 1**

Ако су координате крајева сегмената бројеви не већи од MaxVal, тада постоји O(MaxVal^2) могућих позиција за сегменате. Можемо у некој помоћној матрици m памтити m[i][j] = број сегмената са крајевима у i и j. Затим, слично као и у претходном случају, за сваке две могуће позиције сегмената проверимо да ли су они коњуговани и колико је то укупно парова на основу матрице m. Укупна сложеност је O(N + MaxVal^4) што је довољно за **Подзадатак 2**

Једна од идеја је сортирати сегменте неопадајуће на основу координате центра c\_i = \frac{a\_i+b\_i}{2} и за сваки сегмент i одредити колико има сегмената лево од њега који су коњуговани са њим; коначно решење добијамо када саберемо ове количине за сваки сегмент. Број таквих сегемената је једнак броју индекса j за које важи 1 \leq j \< i и a\_i \leq c\_j и c\_i \leq b\_j.

У **Подзадатку 3** су сегменти већ сортирани растуће по оба краја посебно (па самим тим и по центру) па је скуп сегмената лево од i-тог и који су коњуговани са i-тим неки узастопни подниз сортираног низа сегмената. У сваком кораку се са почетка овог подниза могу избацивати сегменти који нису коњуговани са тренутним (неће бити коњуговани ни са “деснијим” сегментима због услова подзадатка) па техника двa показивача и/или бинарне претраге решава овај подзадатак у сложености O(N) или O(N \log N).

Претпоставимо да су све координате центара c\_i релативно мали, различити цели бројеви (можемо се обезбедити да буду цели тако што на почетку помножимо све крајеве сегемената са 2). Дефинишимо низ A где је за свако i=\overline{1,N}, A[c\_i] = r\_i а на осталим позицијама су нуле. Ако је c\_1 \< c\_2 \< \ldots \< c\_N, тада је број сегмената који су лево од сегмента i и који су коњуговани са њим једнак броју елемемената узстопног подниза A[l\_i], A[l\_i+1],\ldots, A[c\_i - 1] који су већи или једнаки од c\_i (посматра се само подниз од l\_i-те до (c\_i-1)-те позиције јер су индекси - центри сегмената и они морају припадати i-том сегменту; вредности елемента су десни крајеви тих сегмената па морају бити \geq c\_i да би садржали центар i-тог сегмента).

Овим се задатак своди на **релативно познат проблем** : _дат је низ A дужине M и N упита облика (l, r, k) - одредити колико има елемената у поднизу A[l..r] који су већи или једнаки k_. Овај проблем се најлакше решава _offline_ користећи структуру _сегментно стабло_. На почетку напунимо помоћни низ B нулама и сортирамо све елемементе и упите (заједно) опадајуће по вредности елемента односно вредности k у упитима. Затим идемо редом по сортираном низу и када наиђемо на неки елемент A[i], на позицији i у низу B поставимо јединицу; када наиђемо на упит (l,r,k), само одредимо број (или збир) свих елемената у низу B на позицијама од l до r јер су у том тренутку додати само елементи из A који су већи или једнаки k. Ово се једноставно ради сегментним стаблом у укупној сложености O(M + N \log M).

У **Подзадатку 4** су вредности c\_i заиста довољно мале да се њима може директно индексирати низ A (тј. овде је M \leq 10^6) а случајеви се једнаким c\_i-овима се решавају малом модификацијом алгоритма. Када су вредности c\_i велике (нпр. до 10^9) треба користити _имплицитно сегментно стабло_ или, једноставније, компресовати координате на почетку, што даје алгоритам сложености O(N \log MaxVal) или O(N \log N) који решава **све подзадатке**.

Алтернативни приступ (за решавање проблема на који смо свели оригинални проблем) је коришћење такозване Sqrt-декомпозиције где делимо низ на \sqrt{N} делова величине \sqrt{N} и за сваки од њих памтимо сортирани низ елемената из тог дела. Када дође упит (l,r,k), за највише два дела у којима су крајеви упита одрадимо претрагу ручно а за осталих O(\sqrt{N}) делова одрадимо бинарну претрагу над одговарајућим низом. Ово даје алгоритам сложености O(N\sqrt{N}\log N) који би, уз пристојну имплементацију, такође требало да освоји све поене. Напоменимо да овај приступ у истој сложености решава варијанту проблема у коме се захтева да се на упите одговара у задатом редоследу (_online_) и где су дозвољени упити који модификују појединачне елементе (иначе, ова тежа варијанта проблема се може решити и у сложености O(N \log^2 N)).

---

<div class="post-metadata">

**Author:** ![MladenP](https://algora.petlja.org/user_avatar/algora.petlja.org/mladenp/32/53_2.png) [@MladenP](https://algora.petlja.org/u/MladenP)\
**Post date:** [January 31, 2022, 10:18pm UTC](https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077/5 "2022-01-31T22:18:24Z")

</div>

# Мин Макс Плус

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

Ускоро.

---

<div class="post-metadata">

**Author:** ![PetljaKoki](https://algora.petlja.org/user_avatar/algora.petlja.org/petljakoki/32/1624_2.png) [@PetljaKoki](https://algora.petlja.org/u/PetljaKoki)\
**Post date:** [January 29, 2025, 8:52pm UTC](https://algora.petlja.org/t/resenja-zadataka-2021-2022-kvalifikacije-treci-krug/7077/6 "2025-01-29T20:52:02Z")

</div>

кад ће решење да падне