[Решења задатака] 2025/2026 Државно

[Sprdalo]

Намештаљка

Аутор: Марко Миленковић

Текст и тест примери: Марко Миленковић

Анализа решења: Димитрије Ердељан

Тестирање: Димитрије Ердељан

Да би направили највећу могућу суму, неопходно је да бројеви у оба
низа буду наизменично већи па мањи, односно да је или a_1 > a_2,
a_2 < a_3, a_3 > a_4, …, или а_1 < a_2, a_2 > a_3, a_3 < a_4, и тако даље. У супротном, имали бисмо три броја a_{i-1} < a_i < a_{i+1} (или у обрнутом поретку, где је доказ исти), и није тешко
доказати да би мењање места a_{i-1} и a_i повећало суму.

Претпоставимо за сада да оба низа почињу малим бројем, односно a_1 < a_2, a_2 > a_3, …, b_1 < b_2, b_2 > b_3, … 1.

Формула:

|a_1 - a_2| + |a_2 - a_3| + \cdots + |a_{n-1} - a_n|+|b_1 - b_2| + |b_2 - b_3| + \cdots + |b_{n-1} - b_n|

Сада је једнака:

-a_1 + 2a_2 - 2a_3 + \cdots \pm 2a_{n-1} \pm a_n - b_1 + 2b_2 - 2b_3 \cdots \pm 2b_{n-1} \pm b_n,

где \pm треба заменити за +, ако је n паран број, а за -, ако је n непаран број.

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

Да би довршили решење, потребно је још да поновимо исту процедуру за
преостале облике низова (где један или оба од a_i, b_i почиње
великим бројем, у ком случају на непарне индексе постављамо велике
бројеве) и од четири добијена решења испишемо оно које даје највећу
суму.

[Sprdalo]

Аралски морнар

Аутор: Алекса Милисављевић

Текст и тест примери: Алекса Милисављевић

Анализа решења: Софија Чебашек

Тестирање: Марко Трајковић

Решење када су сва поља пустињска и n \leq 10

Приметимо да, како су сва поља пустињска, укупна токсичност на путу од горњег левог до доњег десног поља ће бити сума токсичности свих поља на која је Аралски морнар стао. Морнар ће укупно направити 2n-2 корака, од којих ће n-1 бити померање на доле, а n-1 померање на десно. Укупан број различитих редоследа тих корака је \binom{2n-2}{n-1}. У овом подзадатку можемо генерисати све могуће распореде и одредити за који је укупна токсичност најмања.

Временска сложеност: O(n\binom{2n-2}{n-1})

Решење када су сва поља пустињска

Као у претходном подзадатку, укупна токсичност ће бити сума токсичности свих поља на која је морнар стао. Овај подзадатак се може решити техником динамичког програмирања. Матрица dp димензија n \times n се дефинише на следећи начин:

dp_{i,j} - \text{најмања могућа укупна токсичност на путу од поља } (i,j) \text{ до поља } (n,n)

Елементи матрице се рачунају на следећи начин:

dp_{i,j}= \begin{cases} t_{i,j} & \text{ за } i=n \text{ и } j=n \\ dp_{i,j+1}+t_{i,j} & \text{ за } i=n \text{ и } 1 \leq j \leq n-1 \\ dp_{i+1,j}+t_{i,j} & \text{ за } 1 \leq i \leq n-1 \text{ и } j=n \\ min(dp_{i,j+1},dp_{i+1,j})+t_{i,j} & \text{ за } 1 \leq i \leq n-1 \text{ и } 1 \leq j \leq n-1 \end{cases}

Матрица се конструише од последњих ка првим редовима и колонама. Решење задатка је вредност поља dp_{1,1}.

Временска сложеност: O(n^2)

Решење када важи t_{i,j} \geq 0

Тврђење: Након што морнар једном стане на пустињско поље, свако следеће поље на које стане ће сигурно бити пустињско. Свако поље након првог стајања на пустињу ће постати пустињско због проширивања пустиње поља на ком се морнар налази.

Како су токсичности свих поља ненегативне, у овом подзадатку је циљ стати на што мање пустињских поља. Због тога, ни један потез Аралског морнара неће бити трећег типа, тј. неће чекати ни на једном пољу. Користећи претрагу у ширину (енг. Breadth First Search, BFS), која се започиње из свих поља која су на почетку пустиња, за свако поље је могуће одредити тренутак у ком ће постати пустиња. Неопходно је одредити сва поља која могу бити прва пустињска поља на које ће морнар стати. Претрагом у ширину из почетног поља, можемо упоредити време за које морнар стиже на то поље и време када то поље постаје пустиња. Уколико се за време претраге стигне до поља за које је време када постаје пустиња мање од времена када морнар стаје на њега, оно је једно од могућих првих пустињских поља на која ће морнар стати и претрага у ширину се не наставља из тог поља. Укупна токсичност када се кретање настави из неког поља може се израчунати унапред динамичким програмирањем, као у претходном подзадатку. Решење је најмање од свих укупних токсичности за сва могућа почетна пустињска поља.

Временска сложеност: O(n^2)

Решење када важи n \leq 200

Приметимо да уколико морнар прескочи потез (чека на неком пољу), тренутак у ком ће први пут стати на пустињско поље не зависи од поља на ком је чекао. Уколико је почетно поље пустињско, решење ће бити dp_{1,1}. Иначе, може да прескочи произвољан број потеза док се налази на почетном пољу и затим настави своје кретање. За свако време чекања од 0 до 2n-2 (сва поља ће постати пустињска након највише 2n-2 потеза), задатак ћемо решавати као у претходном подзадатку и решење ће бити најмања токсичност за сва могућа времена чекања.

Временска сложеност: O(n^3)

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

Посматрајмо сва могућа почетна пустињска поља из трећег подзадатка. Приметимо да сва поља на која морнар стане пре него што дође до тих поља такође могу бити прва пустињска на која ће стати, уколико на почетку чека одговарајући број потеза. Имплементација решења је слична трећем подзадатку, а решење је најмања вредност dp_{i,j} за сва поља (i,j) која се посете претрагом у ширину из поља (1,1), до заустављања описаном у трећем подзадатку. Уколико је прво поље пустињско, решење је dp_{1,1} и није потребно радити претрагу у ширину из тог поља.

Временска сложеност: O(n^2)

[Sprdalo]

Суб67це

Аутор: Василије Новаковић

Текст и тест примери: Василије Новаковић

Анализа решења: Василије Новаковић

Тестирање: Милош Милутиновић

За почетак размислимо како би смо за потпуно познату ниску (без упитника), израчунали трулост на спор начин.

Назовимо подниску трулом, ако је дужине 2 и први карактер је 6 а други 7 (трулост ниске је број њених трулих подниски)

Можемо избројати колико трулих подниски постоји, које почињу неким конкретним каркатером на позицији i.

Ако важи s_i = 7, тад постоји 0 трулих подниски којима је први каркатер i, а ако је s_i = 6, тад је број трулих подниски које почињу на тој позицији, једнак броју позиција j, j \gt i, s_j = 7.

Тада је трулост ниске управо једнака суми трулих подниски које почињу на позиији i, 1 \leq i \leq N.

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

Подзадазак 1: сви карактери ниске су ‘?’

Приметимо да је оптимално да све упитнике које заменимо у 6, ставимо пре свих упитника које заменимо у 7.

Назовимо позицију последњег упитника који ћемо променити у шестицу “граница упитника”.

Доказ за ово је једноставан: ако постоје два упитника, који су замењени за 7 и 6, тако да се седмица налази пре шестице, онда посматрајући начин на који рачунамо трулост ниске, можемо приметити да ако заменимо уместо тога први упитник у 6 а други у 7, трулост ће се сигурно повећати барем за 1, и никад се неће смањити.

Дакле, за било које две позиције на којима су упитници, и заменили смо први у 7 и други у 6, увек можемо повећати трулост тако што им заменимо вредности, а кад не постоје овакви парови, то значи да се све шестице налазе пре свих седмица.

Након што је установљено да ћемо неки префикс упитника претворити у 6 а остале вредности у 7, треба узети оптималан распоред.

Формалније, рецимо да одговарамо на упит од L до R. Пошто су у овом подзадатку све упитници, то значи да одговарамо на упит са x = R - L + 1 упитника.

Ако заменимо A упитника у 6, а B упитника у 7, тада важи A + B = x, а трулост је једнака производу A \cdot B

Поприлично је интуитивно, али се може и доказати помоћу неједнакости за аритметичку и геометријску средину, да ћемо прву половину заменити у шестице, а другу половину у седмице, а ако x није дељив са 2, није битно да ли ћемо број у средини заменити у 6 или 7, јер ће резултат бити исти.

Временска сложеност О(1) по упиту.

Укупна временска сложеност је О(N+Q)

Просторна сложеност О(N)

Позадатак 2: N, Q \leq 100

У овом подзадатку можемо искористити обзервацију из претходног, а то је да ћемо неки префикс упитника заменити са 6, а остале упитнике са 7.

Можемо фиксирати границу где ће нам шестице престати, то јест седмице почети, и за тако добијену ниску израчунати трулост на начин описан у почетку задатка.

Сад се своди на израчунавање трулости фиксиране ниске (без упитника), што овај подзадатак дозвољава у О(N^2), иако је могуће урадити то значајно брже.

Сложеност: O(N^3 \cdot Q)

Просторна сложеност О(N)

Подзадатак 3: N, Q \leq 500

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

Просторна сложеност О(N)

Подзадатак 4: ни један карактер није ‘?’

У овом подзадатку је потребно брзо одговарати на упите, али нам је цела ниска већ фиксна.

Прво нађимо начин да брзо одговарамо на упите где је L = 1:

Можемо израчунати низ prefAns, где је prefAns_i једнак одговору на упит L = 1, R = i.

Овај низ можемо лако израчунати у О(N), користећи идеју из претходног подзадатка.

Сад разматрамо како да нађемо трулост од L до R, користећи овај низ:

Ако узмемо само prefAns_R, избројаћемо више него што треба, јер ће шестице које се налазе пре позиције L, да додају на трулост.

Свака шестица која се налази пре позиције L ће додати на трулост број седмица између њене позиције и позиције R. Ово се даље може разложити на број седмица између њене позиције и L-1 + број седмица између позиција L и R. Кад посматрамо све шестице заједно и групишемо први члан то је заправо prefAns_{L-1}, док је други члан заправо производ броја шестица од 1 до L-1 и броја седмица од L до R. Број шестица и седмица можемо наћи користећи одвојене префиксне суме, али коначна формула за одговор на упит од L dо R је:

• prefAns_R - prefAns_{L-1} - cnt6[1:L-1] \cdot cnt7[L:R]

Временска сложеност О(N + Q)

Просторна сложеност О(N)

Подзадатак 5: N, Q \leq 2000

Користећи идеју из претходног подзадатка, најлакше решење за овај подзадатак је да фиксирамо границу где престајемо упитнике да претварамо у 6, и почињемо да их претварамо у 7, независно од упита, и да израчунамо оне исте низове за сваку од тих граница, којих има највише N.

Након што то урадимо, одговор на упит може да се ради на исти начин, тако што фиксирамо границу и узмемо максимални одговор по свакој граници за неки упит, јер одговор можемо да нађемо у O(1).

Временска сложеност О(N \cdot (N + Q)).

Просторна сложеност О(N^2)

Подзадатак 6: L_i = 1

У овом подзадатку се сваки упит ради на префиксу ниске.

Можемо сортирати упите по R и одговарати на њих offline.

Приметимо да како десна граница упита расте, наша граница где престајемо да стављамо шестице никако не може да се смањи, може само да се повећава или да остане иста.

Доказ: замислимо да се десна граница повећава један по један карактер, а да је тренутна граница на којој престајемо да стављамо 6 и крећемо да стављамо 7 једнака x. Ако нам се сад десна граница упита повећа са један, то значи да је нови карактер који смо добили или 6 или 7 или ?. Ако је карактер 6, он не може да утиче на одговор јер је последњи, па не постоји ни једна седмица после њега. Дакле довољно је решити случај где је 7, јер ако је упитник сигурно ћемо га заменити за 7.

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

Ово нам може дати интуицију како ће се трулост понашати кад померамо границу упитника.

Може се доказати да ће померањем границе упитника десно, трулост прво strogo да расте, па да достигне максимум, и више граница може да даје максималну трулост (што се може видети на примеру ???), али ће оне бити једна до друге, и након максимума ће strogo да опада.

Доказ је следећи:

Посматрајмо како се трулост мења кад границу померимо са i-1-ог на i-ти упитник (претворимо i-ти упитник у 6 уместо у 7).

Трулост ће се смањити за број шестица пре тог упитника (упитнике пре тог сматрамо за шестице такође), али повећати за број седмица након њега (упитнике након сматрамо за седмице).

Како померамо границу на десно, број шестица лево ће да расте бар за 1, а број седмица ће се смањити бар за 1 (јер смо баш тај конкретан упитник управо претворили са 7 у 6, па кад се померимо још на десно сигурно ће се повећати број шестица за барем 1, исто тако кад се пребацимо на следећи упитник, он је пре пребацивања био 7, а сад посматрамо све десно од њега, па нам се број седмица смањио бар за 1).

Ово значи да ће фактор који се одузима да расте, док ће фактор који се додаје да се смањује, и једини случај кад трулост остаје иста, је кад су та два фактора једнака (што не мора да се деси), што је сигурно максимум јер је пре тога фактор који се одузима сигурно био мањи од фактора који повећава, а након тога је фактор који се одузима сигурно већи па ће трулост да настави строго да опада.

Знајући ово, како нам се десна граница упита помера у десно, можемо да померамо нашу границу упитника све док трулост расте.

Како би брзо израчунали трулост за одређену границу, треба имати додатно израчунато и:

• укупан број седмица након сваког упитника који се налази у првих i позиција: prefq7[i]
• укупан број шестица који се налази пре сваког упитника, у последњих i позиција: sufq6[i]

Након тога је могуће за неку границу x израчунати трулост тако што је поделимо збир следећих делова:

• Колико свака шестица има седмица након себе (рачунамо исто као у четвртом подзадатку)

• Производ броја упитника које претварамо у шестица и броја упитника које претварамо у седмице.

• Колико укупно има седмица након свих упитника које претварамо у шестице.

• Колико укупно има шестица пре свих упитника које претварамо у седмице.

Сваки од ових бројева је могуће израчунати у О(1) за неку дату границу, након што смо претходно поменуте низове израчунали пре свих упита.

Временска сложеност: O(N + Q \cdot log(Q))

Просторна сложеност: О(N + Q)

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

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

Израчунаћемо трулост за две суседне границе упитника:

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

За начин рачунања трулости у зависности од границе, погледати претходни подзадатак.

Временска сложеност: O(N + Q \cdot log(N)).

Просторна сложеност: О(N).

[Sprdalo]

Ексклузивни Камп

Аутор: Марко Миленковић

Текст: и тест примери: Марко Миленковић

Анализа решења: Марко Миленковић

Тестирање: Андреј Ивашковић

Увод

Задатак можемо да моделујемо као граф. Како тражимо минимални подграф који је повезан, структура коју тражимо стабло.

N \leq 10, M \leq 20

У овом подзадатку можемо да пробамо све подскупове грана, њих 2^M и за сваки одабир грана проверимо да ли је подграф повезан и да ли су S чворови листови. Сложеност овог приступа је (N+M)2^M

S \leq 2

Уколико је S = 1, онда је потребно да повежемо цео граф без једног изабраног чвора. Уколико је то могуће, онда само додамо грану до тог једног чвора, иначе не постоји решење.

Уколико је S = 2, фиксирамо једну грану из првог чвора, једну грану из другог чвора. Затим проверимо да ли је граф без ова два чвора повезан.

M = N - 1

Како је граф повезан и има N-1 грана, то значи да је стабло. У овом случају или је цео граф задовољавајући или не постоји решење, јер избацивање барем једне гране из стабла прекида повезаност графа.

S \geq N - 2

Уколико је S = N - 1, онда би требало да у разапињућем стаблу да имамо само један чвор који није лист. Потребно је само проверити да ли је овај чвор повезан директно са свим осталим. Успутно, овакав граф се назива звезда.

Уколико је S = N - 2, онда два чвора који не морају да буду листови морају да буду повезани граном и сви остали чворови су директно повезани на барем један од ова два чвора. Уколико нешто од овога не важи, решење не постоји.

N, M \leq 2000

Овај подзадатак се решава идентично као наредни, али је дозвољена неоптимална имплементација решења.

Без додатних ограничења

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

Временска сложеност је O(N+M).

[Sprdalo]

Кодфорсес Блог

Аутор: Немања Мајски

Текст и тест примери: Немања Мајски

Анализа решења: Ања Дожић

Тестирање: Ања Дожић

Подзадатак 1: a_1=a_2=...=a_n

Како сви људи који виде блог сматрају да његова уваженост треба да буде иста, у овом подзадатку нам редослед којим ће га они видети неће бити важан, те можемо само једном проћи кроз низ и израчунати колику уваженост ће блог имати на крају. Уваженост коју смо израчунали је једина уваженост коју блог може имати, па нам остаје једино да је упоредимо са k.

Временска сложеност: O(n)

Подзадатак 2: n\leq8

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

Временска сложеност: O(n\cdot n!)

Подзадатак 5: крајња уваженост не може бити већа од k

Приметимо да ћемо максималну уваженост добити ако низ поређамо неопадајуће. Дакле, ако можемо достићи вредност k, достићи ћемо је неопадајуће сортираним низом.

Временска сложеност: O(n\cdot logn)

Подзадатак 6: t=0

Као што смо у петом подзадатку видели, највећу уваженост нам даје неопадајуће сортиран низ, слично можемо показати да најмању даје низ који сортиран нерастуће. Како свака ротација два елемнта мења уваженост за 2, -2 или 0, можемо закључити да је могуће наћи пермутацију која даје уваженост k, за свако k које је између минималне и максималне вредности и има исту парност као и оне (нерастући низ можемо одбити од неопадаућег коначним бројем ротација, где свака ротација ствара нову пермутацију чија је вредност у датом опсегу).

Временска сложеност: O(n\cdot logn)

Подзадатак 7: n\leq500

Замена места два узастопна елемента може да промени уваженост за 2, -2 или 0. Дакле, ако кренемо од неопадајуће сортираног низа који има максималну уваженост, и сортирамо га Bubble sort-ом нерастуће, свака замена места ће мењати уваженост за највише 2 по апсолутној вредности, и на крају ће је спустити до минималне могуће уважености (када низ потпуно сортирамо нерастуће). Одатле закључујемо да ће у неком тренутку у сортирању уваженост морати да достигне k (претходно проверимо да ли је k могуће достићи као што смо радили и у шестом подзадатку), па ћемо када се то деси исписати ту пермутацију низа.

Временска сложеност: O(n^3)

Подзадатак 9: без додатних ограничења

За цело решење, користићемо се идејом из седмог подзадатка, само ћемо је оптимизовати.

Радићемо две бинарне претарге. Прва бинарна претрага служиће нам да одредимо колико највише елемената са краја можемо да ставимо на почетак у нерастућем поретку тако да уваженост буде већа или једнака од k. Она нам замењује први део Bubble sort-a, где ћемо само неке од елемената поређати на почетак низа. Затим, са фиксираним бројем елемената које смо пребацили, радимо другу бинарну претрагу. Она ће нам служити да одредимо на коју позицију стављамо елемент који је на крају низа након пребацивања, тј. замениће нам остатак соритрања (знамо да та позиција мора бити негде између његове тренутне позиције и пребачених елемената, јер би у супротном и он био пребачен).

У тренутку када добијемо редослед чија је уваженост k, исписујемо га.

Временска сложеност: O(n\cdot logn)

Други начин

У шестом подзадатку смо видели како можемо да одредимо да ли уваженост може да достигне k или не. Ако смо закључили да може, даље лако можемо видети да нам онда треба да тачно \frac{n-k}{2} људи смањи уваженост, док је њих \frac{n+k}{2} повећава. Очигледно, изабраћемо \frac{n-k}{2} најмањих a_i да буду они који спуштају уваженост, док ће је остатак повећавати (овај избор је добар јер ако већи број смањује уваженост, смањиваће је и мањи; слично, ако мањи број повећава уваженост, повећаваће је и већи). Сада нам остаје само да одредимо распоред којим ће они да виде блог.

Почећемо тако што ћемо ређати људе које смо одредили да подижу уваженост у неопадајућем поретку све док не наиђемо на неког ко због своје вредности a_i треба да је спусти или док их не поређамо све. Ако смо наишли на особу коју смо одредили да треба да подиже уваженост, а она је због своје вредности a_i спушта, уместо ње крећемо да ређамо у нерастућем поретку оне које смо одредили да треба да спуштају уваженост. Знамо да ће бар први ког поставимо спуштати уваженост јер је по одабиру сигурно мањи или једнак a_i. Њих ређамо док их не поређамо све или док не дођемо у ситуацију да неки од њих подиже уваженост због своје вредности a_i. У тој ситуацији поново крећемо да неопадајуће ређамо оне које смо одредили да подижу уваженост. Настављамо поступак док не поређамо свх n људи.

Зашто ова конструкција ради? Због начина на који их ређамо, јасно је да ће једна од две групе “испунити свој задатак” прва, и да ћемо остале из друге групе морати само да поређамо како је описано раније. Без умањења општости, нека смо поређали све људе које смо одредили да подижу уваженост и остало нам је m оних који треба да је спуштају. Како смо људе који треба да спуштају уваженост ређали у нерастућем поретку, то значи да нам је остало m најмањих вредности a_i. Такође, знамо да нам је уваженост у том тренутку k+m. Ако m најмањих не би могло да смањи уваженост на k, ни једна друга $m-$торка такође не би могла, па самим тим не бисмо могли да добијемо уваженост k за дати блог, што не може да се деси јер смо на почетку проверили да ли је могуће достићи дату уваженост. Аналогно се добија и за случај када нам на крају остане l људи које смо одредили да подижу уваженост.

Временска сложеност: O(n\cdot logn)

[Sprdalo]

Интергалактички сукоб

Аутор: Марко Савић и Урош Костадиновић

Текст и тест примери: Урош Костадиновић

Анализа решења: Владимир Миленковић

Тестирање: Немања Мајски

Решење ће бити додато ускоро. Подсетите предвиђеног члана Комисије ако имате прилику.