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

[MladenP]

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

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

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

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

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

[MladenP]

Млађионичар

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

Означимо са 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).

[MladenP]

Психо

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

Решење за 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).

[MladenP]

Коњугација

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

Можемо за сваки пар сегмената проверити у константној сложености да ли су коњуговани - сложеност овог алгоритма је О(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)).

[MladenP]

Мин Макс Плус

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

Ускоро.