[Решења задатака] 2025/2026 СИО

Algoritam
1

Продаја

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

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

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

Тестирање: Урош Костадиновић и Марко Миленковић

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

Ако Лука има само један покушај, онда је довољно да проба сваку могућу цену.

Ако понуди цену Y, муштерија ће прихватити понуду ако је X \geq Y. Број папирића који доводе до прихватања понуде је:

A_Y + A_{Y+1} + \ldots + A_N

Зато је очекивана зарада, помножена са D, једнака:

Y \cdot (A_Y + A_{Y+1} + \ldots + A_N)

Дакле, довољно је проћи кроз све вредности Y и узети максимум.

У случају када су све вредности A_i једнаке, ово се своди на тражење максимума израза:

Y \cdot (N - Y + 1)

што решава први подзадатак.

Решење за мале вредности N и K

Приметимо шта се дешава након што Лука понуди цену Y.

Ако муштерија прихвати понуду, продаја се завршава и Лука зарађује Y динара. Ако је одбије, Лука сада сигурно зна да важи X < Y. То значи да се после одбијене понуде проблем своди на исти проблем, али само над вредностима 1,2,\ldots,Y-1 и са једним покушајем мање.

Ово нас природно доводи до динамичког програмирања.

Нека је:

P_i = A_1 + A_2 + \ldots + A_i

и нека је dp[t][r] највећа могућа зарада помножена са D, ако знамо да је X \leq r и ако Лука има још t покушаја.

Ако као прву цену понудимо Y, где је 1 \leq Y \leq r, онда добијамо:

  • за све вредности X \in [Y,r] муштерија прихвата понуду, па је допринос

    Y \cdot (P_r - P_{Y-1})

  • за све вредности X < Y понуда је одбијена и остаје нам проблем са t-1 покушаја над префиксом 1,\ldots,Y-1, па је допринос

    dp[t-1][Y-1]

Зато важи рекуренција:

dp[t][r] = \max_{1 \leq Y \leq r} \left( Y \cdot (P_r - P_{Y-1}) + dp[t-1][Y-1] \right)

Почетно је:

dp[0][r] = 0

јер без преосталих покушаја Лука не може ништа да заради.

Ово решење ради у сложености:

O(KN^2)

и довољно је за подзадатак N \leq 200, K \leq N. Такође, подзадатак K=2 и једнака расподела може се решити истом идејом, само са мањим бројем стања.

Кључно запажање за оптимизацију

Погледајмо рекуренцију:

dp[t][r] = \max_{1 \leq Y \leq r} \left( Y \cdot (P_r - P_{Y-1}) + dp[t-1][Y-1] \right)

Средимо израз:

dp[t][r] = \max_{1 \leq Y \leq r} \left( Y \cdot P_r + dp[t-1][Y-1] - Y \cdot P_{Y-1} \right)

За фиксирано t и фиксирано Y, израз је линеарна функција по P_r:

f_Y(x) = Y \cdot x + dp[t-1][Y-1] - Y \cdot P_{Y-1}

Дакле, за свако Y имамо једну праву, а за свако r треба да нађемо максимум вредности тих правих у тачки:

x = P_r

Ово је класична примена Convex Hull Trick-а.

Зашто је Convex Hull Trick једноставан у овом задатку?

Праве додајемо редом по Y.

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

Са друге стране, упити се раде за вредности:

P_1, P_2, \ldots, P_N

а овај низ је неопадајући, јер су сви A_i \geq 0.

Зато можемо користити deque верзију Convex Hull Trick-а:

  • праве додајемо у редоследу растућих нагиба,
  • упите постављамо у неопадајућем редоследу x,
  • бескорисне праве избацујемо са краја,
  • током упита померамо показивач са почетка док следећа права даје бољу вредност.

На овај начин свака права се дода и избаци највише једном, па један слој динамике рачунамо у O(N).

Пуно решење

Још треба објаснити шта радимо ако је K > N.

Након сваке одбијене понуде, Лука мора понудити мању цену да би та понуда уопште могла бити прихваћена. Зато у једној партији има смисла направити највише N различитих понуда. Све преко тога не може побољшати резултат.

Зато можемо одмах поставити:

K = \min(K, N)

Сада користимо динамику из претходног дела и Convex Hull Trick оптимизацију.

За сваки број покушаја t рачунамо нови ред динамике из претходног реда. За сваку могућу цену Y додајемо праву:

f_Y(x) = Y \cdot x + dp[t-1][Y-1] - Y \cdot P_{Y-1}

а за сваки r питамо максимум у тачки:

x = P_r

Тако добијамо:

dp[t][r] = \max_Y f_Y(P_r)

Одговор је:

dp[K][N]

односно оптимална очекивана зарада помножена са D.

Сложеност

Пошто је K \leq N, а сваки слој динамике рачунамо у O(N), укупна временска сложеност је:

O(NK)

односно у најгорем случају:

O(N^2)

Меморијска сложеност је:

O(N)

јер је за рачунање тренутног реда динамике довољно чувати само претходни ред.

2

Градови

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

Подзадатак 1: M=N,Q=1, пут i повезује места i и i+1, за i<N, а пут N повезује место N и место 1

Посматрајмо пут N. Он је дужине 2^N, док је сума дужина осталих путева 2^1 + 2^2 + \dots + 2^{N-1} = 2^N - 2. Дакле, било која рута која користи пут N дужа је од било које руте која га не користи.

Размотримо случај K = 0. Нека смо неко село k прогласили за град. Приметимо да увек можемо бирати руту из села ка граду која избегава грану N. Другим речима, из села i < k би се ишло рутом i \to i +1 \to \dots \to k - 2 \to k - 1, а из села j > k рутом j \to j - 1 \to \dots \to k + 1 \to k.

Пут N-1 ће сигурно бити део неке руте, па је наш циљ да прогласимо град тако да минимизујемо дужину руте која садржи пут N-1. Ово радимо тако што прогласимо место N - 1 за град – тада је највећа изолованост управо 2^{N-1}.

Шта се дешава у случају K \geq 1? Тада постојећи градови деле цео граф на узастопне интервале села. Илустрације ради, посматрајмо интервал i, i + 1, \dots, j, где су i и j градови, i+1, \dots j-1 села, а важи i<j-1 (како би у интервалу постојало бар једно село). Слично као пре, пут j-1 неће бити коришћен ни у једној рути, јер све руте у овом интервалу могу ићи ка граду i.

Уколико прогласимо село j-1 за град, нећемо користити ни пут j-2, па ће највећа изолованост у овом интервалу бити 2^i + 2^{i+1} + \dots + 2^{j-3}, добијена рутом од j-2 до i Укокико ипак не прогласимо ниједно село у интервалу градом, највећа изолованост биће 2^i + 2^{i+1} + \dots + 2^{j-2}, добијена рутом од j-1 до i.

Случај када компонента пролази кроз грану N, тј. где не важи i < j, мало је компликованији, али се долази до истог закључка: изолованост целог графа зависиће од треће најдуже гране једног интервала по избору, као и од друге најтеже гране свих осталих интервала. Према томе, град је потребно прогласити у оном интервалу са највећом вредности дужине друге најдуже гране.

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

Подзадатак 2: M=N,Q=1, путеви повезују места циклично

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

Посматрајмо поново случај K = 0. Слично као пре, пут дужине 2^N неће бити коришћен, па га можемо игнорисати, али пут дужине 2^{N-1} хоће, па желимо да минимизујемо дужину руте која га користи. Нека је, без умањења општости, пут N тежине 2^N, а пут k дужине 2^{N-1}, где је 1 < k < N - 1. Нови град t који прогласимо делиће граф на две компоненте села, 1, \dots, t -1 и t+1, \dots, N. Највећа изолованост добија се дужом од две руте: оне од 1 до t и оне од N до t. Ако је t > k, онда је прва рута дужа (јер садржи пут дужине 2^{N-1}, у супротном је друга рута дужа.

Уколико бирамо t > k, циљ је да минимизујемо дужину прве руте, па желимо што мање t. Уколико бирамо t \leq k, желимо да минимизујемо дужину друге руте, па бирамо што веће t. Другим речима, t ће увек бити или k или k + 1. Избор између ова два села зависи од дужина рута 1 \to 2 \to ... \to k и N \to N - 1 \to ... \to k + 1, јер грану k желимо да спојимо са краћом од ове две руте. Њихове дужине могу се лако упоредити према томе где се налази грана дужине 2^{N-3}.

Посматрајмо сада случај K \geq 1. Решење лако следи из раније наведених закључака. Поново ћемо имати узастопне интервале села. У сваком интервалу можемо игнорисати пут највеће дужине. Како не бисмо користили ни други најдужи пут, морамо прогласити градом било које село између првог и другог најдужег пута у том интервалу. Дакле, изолованост целог графа поново зависи од треће најдуже гране неког интервала, као и од друге најдуже гране свих осталих интервала. Бирамо онај интервал са највећом вредности дужине друге најдуже гране.

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

Подзадатак 3: K=1,Q=1

Посматрајмо минимално разапињуће стабло датог графа. Нека је грана u - v у графу, а није у стаблу. Она има тежину већу од свих грана на рути од u до v у стаблу, а пошто су све тежине различити степени двојке, она има и тежину већу од суме тежина свих тих грана. Према томе, не може учествовати ни у једној најкраћој рути између два чвора, па је за изолованост потребно разматрати само гране на минималном разапињућем стаблу.

Можемо посматрати град као корен стабла. Поново нам је жеља да елиминишемо најтежу грану у стаблу. Ово омогућавамо проглашавањем било ког села у подстаблу испод те гране. Сада нам проблем представља друга најтежа грана. Уколико је она ван тог подстабла, небитно је који чвор у подстаблу бирамо за град, јер не утиче на максималну изолованост. Уколико ипак јесте у подстаблу, важи, као и раније, да је оптимално прогласити један од чворова на крајевима те гране. Између та два чвора избор зависи од најтеже гране у њиховим одговарајућим подстаблима.

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

Подзадатак 4: Q=1

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

У случају K \geq 2, потребно је из сваког села наћи најкраћу руту до његовог најближег града. Све те руте заједно чине шуму, тј. скуп стабала у ком свако стабло има тачно један град, који представља његов корен.

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

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

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

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

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

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

Приметимо да за сваки град који прогласимо, можемо елиминисати најтежу грану тачно једном. Дакле, помоћу Q проглашавања можемо елиминисати Q најтежих грана дате разапињуће шуме. Избришимо те гране и посматрајмо новодобијене компоненте. Постојаће тачно Q нових компоненти без града, у којима треба прогласити неко село.

Посматрајмо нову најтежу грану. Уколико је она у компоненти која већ има град, небитно је где ћемо прогласити Q нових градова (док год су у одговарајућим компонентама). Уколико је у компоненти која нема град, поново је потребно бирати између два чвора на крајевима те гране, на исти начин као у ранијим решењима. Што се тиче осталих компоненти, градове можемо прогласити било где у њима.

Што се тиче имплементације решења, није неопходно конструисати целу шуму Крускаловим алгоритмом и након тога брисати гране. Нама је познато да ће шума садржати N - max(K, 1) грана, те да ће након брисања Q грана имати N - K - Q. Дакле, довољно је вршити само N - K - Q додавања грана. Даље, током рада алгоритма можемо за сваку компоненту памтити тренутног кандидата за град, као и најтежу грану у њој. Код компоненти које имају предодређен град, то је и кандидат, а за компоненте без њега рачунамо оптималног кандидата током рада алгоритма. Када спајамо две компоненте и једна од њих већ има предодређен град, додељујемо га и њиховој унији. Уколико ниједна нема предодређен град, оптималан кандидат у њиховој унији је онај од два чвора на повезујућој грани који припада компоненти са већом најтежом граном.

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

3

Мајнкрафт Коофа

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

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

Анализа решења: Тони Шкријељ

Тестирање: Тони Шкријељ и Урош Констадиновић


Увод

Ово је output-only задатак: не постоје класични подзадаци које решавамо једним програмом, већ за 10 познатих улаза треба направити 10 излаза.

Циљ је минимизовати параметар K (максималан број поља које бришемо у једном кораку).


Кључна опсервација

Ако у једном кораку обришемо неки скуп поплављених поља S, нека поља из S могу поново да се поплаве (имају бар два суседна поплављена поља), а нека остају празна.

Ако након симулације задржимо само поља која су заиста остала празна, добијамо „ефективан“ скуп операције. Зато у пракси сваку кандидат-операцију вреднујемо симулацијом.


Приступ 1: Обриши сву воду

Најједноставније:

  • K = број свих поплављених поља,
  • један корак који садржи сва поплављена поља.

Ово је коректно и даје почетне поене, али је K велики.


Приступ 2: Обриши компоненту по компоненту

Уместо свега одједном:

  • нађемо повезане компоненте поплављених поља,
  • обришемо једну по једну.

Овим се K спушта на величину највеће компоненте, што је обично боље од приступа 1.


Приступ 3: Први ред

Бирамо први ред који има воду.
У њему узимамо све максималне узастопне сегменте поплављених поља и бришемо их редом.

Интуиција: на ивици матрице повратак воде је често слабији, па овај приступ даје бољи K.


Приступ 4: Први/последњи ред/колона

Ово је прва општа greedy шема:

  1. генериши више кандидата за следећи корак,
  2. изабери најмањи важећи скуп,
  3. примени и понови док не нестане воде.

Кандидати су сегменти са:

  • првог реда са водом,
  • последњег реда са водом,
  • прве колоне са водом,
  • последње колоне са водом.

Овај приступ је брз и у пракси даје солидан baseline.


Приступ 5: Компонента у траци ширине 2

За сваки пар суседних редова (и симетрично колона):

  • посматрамо само та два реда,
  • нађемо компоненте воде у тој траци,
  • узмемо најмању компоненту као кандидата.

Приступ 6: Било која линија (ширина 1)

Не ограничавамо се на ивице:

  • за сваки ред/колону тражимо сегмент узастопних поља који можемо уклонити тако да после симулације остане добар ефекат.

Ово је јаче, али захтева пажљиву проверу услова.


Приступ 7: Правоугаоник ширине 2

Уместо произвољне компоненте у траци, директно испитујемо правоугаонике код којих је једна димензија 2.
За сваки кандидат симулирамо операцију и узимамо најмањи ефективни скуп.

Ово је спорије, али уме да нађе боље операције него приступ 5.


Приступ 8: Шупљи правоугаоник

За правоугаоник (x_1,y_1)-(x_2,y_2) узима се само гранични појас ширине 2.
Тражи се најмањи важећи такав скуп.

Овај приступ је тежак за ефикасну имплементацију и обично се позива тек ако бржи приступи не дају довољно мали K.


Приступ 9: Пун правоугаоник

За фиксне димензије h \times w:

  1. узме се сва вода у том правоугаонику (S),
  2. симулира се повратак воде и избаце поља која су се вратила (S' = S \\setminus T),
  3. ако је скуп не-празан, кандидат је за следећи корак.

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


Практичне оптимизације

Да би решење радило на великим примерима:

  • Bound на добар одговор: тражимо кандидате само док не нађемо скуп величине до тренутног циља (нпр. до jury bound-а).
  • Селективно рачунање: после једне операције поново рачунамо само редове/колоне које су могле да се промене.
  • Каскадно укључивање претрага: спорије претраге (шупљи/пуни правоугаоник) позивају се само ако брже претраге не дају добар скуп.
  • Рад по компонентама: на највећим улазима исплати се разбити проблем на edge-connected компоненте воде и решавати их одвојено.
  • Вишеструко покретање: параметар „добро довољно“ може се дотерати бинарном претрагом кроз више покретања.

Закључак

За овај output-only задатак најбољи практичан приступ је комбинација више претрага:

  • брзе претраге за већину корака,
  • јаче (и спорије) претраге као fallback,
  • јаке оптимизације око ре-рачунaња и границе за „довољно добар“ скуп.
4

Василије мрзи геометрију


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

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

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

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

Решење кад p = [1, 2, 3, \dots, N] или p = [N, N-1, \dots, 1], N \leq 200, Q = 20000


Овај подзадатак може бити решен користећи један позив функције Pitaj.

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

Ово значи да би било која уређена тројка тачака које би у пермутацији p = [1, 2, 3, \dots, N] давала позитиван смер обиласка, давала негативан смер обиласка у пермутацији p = [N, N-1, \dots, 1], и обратно.

Дакле за овај подзадатак довољно је да међу тачкама имамо бар једну тројку која није колинеарна, и да знамо који би био њихов обилазак неким редоследом. Затим питамо за смер обиласка ове три тачке у том истом редоследу, и ако се поклапа са нашим, одговор је p = [1, 2, 3, \dots, N], а ако се не поклапа онда је p = [N, N-1, \dots, 1].

Анализа малих случајева


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

Упит за оријентацију 3 тачке је поприлично апстрактан, па можемо изградити осећај за добру конструкцију размишљањем о малим случајевима:

Зашто је у задатку N \geq 4?

Узмимо N = 3:

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

  • Ако узмемо три тачке које нису колинеарне, за сваку тројку (i, j, k), све ротације било које пермутације дају нам идентичне одговоре на упит, па их не можемо никако разликовати, што значи да је задатак нерешив за N = 3.

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

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

Сад узмимо N = 4

Размишљајући о колинеарним тачкама, можемо закључити да постоје 3 различите конструкције:

  1. Све 4 тачке леже на једној правој.
  2. Не постоје колинеарне тројке.
  3. Постоји тачно једна колинеарна тројка, а четврта тачка не лежи на истој правој као и оне.

Разматрањем N = 3 одмах можемо одбацити случајеве 1 и 2, што нам оставља случај где једна тачка одступа од праве.

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

Решење кад p_1 = 1, N \leq 200, Q = 25000


Размотримо генерализацију конструкције коју смо смислили у анализи малих случајева: ставићемо N - 1 тачку на исту праву, док ћемо прву тачку ставити ван те праве. Ради једноставности, можемо ставити све тачке на x-осу, где ће i-та тачка T_i = (i, 0), док ћемо нашу специјалну тачку ставити било где на y=1 (изнад осталих тачака)

Пошто важи p_1 = 1, ми одмах знамо која тачка нам је специјална, јер је само можемо ставити као прву тачку.

Можемо сад приметити да, пошто се специјална тачка налази изнад свих осталих, Pitaj(specijalna, x, y) ће вратити одговор 1 ако се T_{p_x} налази лево у односу на праву коју чине прве две тачке, што значи ако се T_{p_y} налази десно на x-оси у односу на T_{p_x}. Важи и супротно за одговор -1.

На овај начин можемо видети да ли је p_x < p_y, јер смо исписали тачке тако да лева тачка има мањи индекс од десне.

Ово нам дозвољава да нађемо засебно свако x, где се он налази у пермутацији, што нам самим тим једнозначно одређује и саму пермутацију.

Пошто овај начин тражења поретка тачака захтева n^2 / 2 упита, ово се комотно уклапа у ограничења подзадатка.

Решење кад N \leq 50, Q = 150000


У овом подзадатку важи Q > N^3 што нам дозвољава да урадимо сваки могући упит.

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

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

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

Можемо на исти начин као и у претходном подзадатку наћи скривену пермутацију.

Решење кад N \leq 200, Q = 25000


Овај подзадатак захтева од нас да брже нађемо специјалну тачку.

Како би смо то урадили, можемо упитивати редом тачке i, i+1, i+2: ако је одговор на упит 1 или -1, то значи да је једна од ове 3 тачке специјална, након што смо свели број могућих специјалних тачака на 3 у O(N) упита, лако можемо закључити која од те 3 је заправо специјална, тако што питамо сваки пар две од те 3 тачке са неком споредном тачком (која је сигурно на правој), и ако је одговор 0, онда је тачка коју смо изоставили из упита специјална.

Користећи овај начин тражења успешно налазимо специјалну тачку након највише N + 1 упита.

Налазак тражене пермутације решава се на исти начин као и у претходна два подзадатка.

Решење кад Q = 24000


За овај подзадатак морамо у мањем броју упита да нађемо пермутацију. У суштини, ми не морамо директно за свако x засебно да налазимо колико тачака има лево од Т_{p_x}, већ тачке можемо сортирати све у исто време користећи било који сортинг алгоритам са поређењем, где свако поређење унутар сортирања кошта један упит. За овај подзадатак можемо искористити скоро било који алгоритам сортирања који користи O(N \cdot log_2 N) поређења.

Након што смо сортирали тачке можемо проћи кроз свако x како би нашли колико има тачака лево од p_x. Иако ово може да се уради и у линеарној сложености није потребно за овај задатак.

За једноставну имплементацију можемо направити нашу функцију поређења која користи Pitaj како би знала како да упореди две тачке, и ову функцију можемо проследити std::sort функцији чиме постижемо да не морамо да имплементирамо ниједан специфичан сортинг алгоритам за овај подзадатак.


Решење кад Q = 9400


За N = 1000, log_2 N је мало испод 10, што значи да би N \cdot log_2 N било око 10000 упита. Тренутни алгоритам преко овога има и тражење специјалне тачке које захтева O(N) упита, доводећи нас до око 11000 упита.

Како би смо овај број упита смањили на испод 9400, потребно је, прво, да нађемо алгоритам сортирања у O(N \cdot log_2 N) са довољно малим, гарантованим бројем поређења.

Посматрајмо како функционише алгоритам merge sort. Кад спајамо два дела, величина x и y, овај алгоритам ће направити x+y-1 поређење у најгорем случају, где је најгори случај се оба дела празне док не дођу до стања где оба имају по један елемент, где ће након поређења оба та елемента моћи да се убаце у спојени, сортирани низ.

Ово је најгори случај зато што смо за сваки елемент осим последњег направили по једно поређење. Али опет, постоји тачно \lceil log_2 N \rceil нивоа merge sort-а, и сваки елемент ће бити упоређен на сваком нивоу највише једном, што merge sort алгоритму даје релативно мали број поређења, који смо управо ограничили на N \cdot \lceil log_2 N \rceil поређења.

Међутим, број поређења је још нижи, због тога што претходна граница рачуна да је број поређења x + y за спајање, а не x + y - 1.

На најнижем нивоу, алгоритам спаја N делова величине 1, у N/2 делова величине 2. Ово значи да на том нивоу ми не правимо N поређења, него N - N / 2 поређења. Сличном логиком можемо за претпоследњи ниво добити N - N / 4, и тако даље.

Кад просумирамо ово за све нивое, добијамо укупно: N \cdot \lceil log_2 N \rceil - N + 1, и овим смо ефективно смањили број упита за N, што нас доводи до око 10000 упита.

Како бисмо даље спустили број упита испод 9400, можемо приметити да специјалну тачку можемо пронаћи у највише N/3 + 4 упита, уместо N + 1, тако што ако за i, i+1, i+2 добијемо да су колинеарне, не морамо да проверавамо ни за i+1, i+2, i+3 нити за i+2, i+3, i+4, већ можемо одмах прећи на i+3, i+4, i+5. Једини изузетак овде јесте да морамо ручно проверити N-2, N-1, N јер се може десити да нам је специјална тачка на месту N а да смо добили одговор 0 на N-4, N-3, N-2. Овом оптимизацијом смо смањили број упита за још 2 \cdot N / 3, што је довољно да уз merge sort успешно одреди било коју пермутацију у мање од 9300 упита.

5

Интергалактички конфликт два

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

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

Анализа решења: Тони Шкријељ

Тестирање: Тони Шкријељ


Подзадатак 1: N \le 10, M \le 20


Пошто су и N и M мали, можемо да испробамо све могућности.

За свако X \in \{0,1,\dots,M-1\} рачунамо нове позиције Марсоваца
A'[i] = (A[i] + X) \bmod M.
Затим за фиксирано X решавамо оптимално парирање Марсоваца и Нишоваца ДП-ом по битмасци:
dp[\text{mask}] је минимална цена када су већ упарени Нишовци из mask,
а следећи Марсовац је одређен бројем постављених битова.

Цена једног пара је циклусна дистанца
\min(|p-q|, M-|p-q|).

Укупна сложеност:
O(M \cdot 2^N \cdot N).


Подзадатак 2: N \le 500, M \le 500


Кључна опсервација: када сортирамо позиције Марсоваца и Нишоваца, оптимално парирање је циклусни помак једног сортираног низа у односу на други.
Дакле, довољно је пробати све помаке t \in [0, N).

У овом подзадатку можемо и даље пробати свако X \in [0, M).
За фиксиране X и t цену рачунамо у O(N).

Укупно:
O(M \cdot N^2), што пролази за дате границе.


Подзадатак 3: A[i] < M/4, B[i] < M/4


Пошто су све тачке у првој четвртини круга, можемо посматрати да нема „преласка преко нуле“.
Тада је проблем исти као на правој.

За сваки помак t дефинишемо:
D_i = A_i - B_{(i+t)\bmod N}.

За фиксиран t треба минимизовати:
\sum_i |D_i - X|.
Ово је класичан облик, минимум се постиже за медијану низа D.

Зато:

  1. формирамо D,
  2. сортирамо га,
  3. узмемо медијану,
  4. израчунамо суму апсолутних одступања.

Узимамо минимум по свим t.

Сложеност:
O(N^2 \log N).


Подзадатак 4: N \le 500


Сада морамо потпуно коректно обрадити круг.
Решење је проширење претходне идеје.

За фиксни помак t:

  1. рачунамо
    D_i = (A_{(i+t)\bmod N} - B_i) \bmod M,\quad D_i \in [0,M),
  2. сортирамо D,
  3. правимо удвостручени низ
    E = D \cup (D+M),
  4. гледамо све прозоре дужине N у E.

Сваки прозор представља избор „са које стране круга“ иде сваки елемент.
За прозор је оптимални X његова медијана.
Цену прозора рачунамо преко префиксних сума у O(1).

Укупно:
O(N^2 \log N) (сортирање по сваком t).


Подзадатак 5: укупна дистанца \le 10^4 и N \le 2000


Овај подзадатак такође решава алгоритам из подзадатка 4.

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


Подзадатак 6: без додатних ограничења (главно решење)


Главно решење је исти приступ као у подзадатку 4:

  • сортирање A и B,
  • пролаз по свим помацима t,
  • конструкција D, затим E = D \cup (D+M),
  • минимум по прозорима дужине N уз медијану и префиксне суме.

Сложеност је:

O(N^2 \log N)

што је довољно за N \le 5000 уз пажљиву имплементацију.


6

Гајбиша

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

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

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

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

Решење када је n, q \leq 200

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

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

Ово можемо урадити потпуно наивно, покретањем DFS-а из сваког чвора. Сложеност је довољно добра за овај подзадатак.

Решење када је стабло звезда

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

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

Сложеност по промени је O(\log n).

Решење када је q = 1, или када је n, q \leq 5000

За ове подзадатке довољно је после сваке промене поново израчунати најбољи бумеранг у тренутном стаблу.

Постоји више начина да се ово уради. Један начин је да за сваки чвор нађемо три најбоља пута ка листовима, при чему та три пута морају кренути у три различита смера из тог чвора. То се може урадити DFS-ом и рерутирањем динамике на стаблу.

Једноставније за имплементацију је користити идеју из пуног решења, али без икакве динамичке структуре. После сваке промене поново направимо Euler tour и израчунамо одговор. Ово даје сложеност O(n) или O(n \log n) по промени, у зависности од имплементације, што је довољно за ове подзадатке.

Кључно запажање

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

Нека су та три листа a, b, c. Тежина бумеранга је једнака тежини минималног подстабла које повезује ова три листа. Другим речима, то је збир тежина грана у стаблу које добијамо када спојимо a, b и c.

Ако стабло укоренимо у неком чвору који није лист, и ако листове a, b, c посматрамо у DFS поретку, нека важи:

fst[a] < fst[b] < fst[c]

Нека је:

x = lca(a, b)

и

y = lca(b, c)

Тада је центар бумеранга заправо онај од чворова x и y који је ближи корену, односно који има мању дубину.

Зато тежину бумеранга можемо записати као:

dep[a] + dep[b] + dep[c] - dep[x] - dep[y] - \min(dep[x], dep[y])

Ово можемо преписати као максимум две вредности:

dep[a] - 2dep[x] + dep[b] - dep[y] + dep[c]

и

dep[a] - dep[x] + dep[b] - 2dep[y] + dep[c]

Зато се у решењу појављују баш два низа коефицијената:

(1, -2, 1, -1, 1)

и

(1, -1, 1, -2, 1)

Прва, трећа и пета позиција представљају листове a, b, c, док друга и четврта позиција представљају чворове lca(a,b) и lca(b,c).

Euler tour

Направићемо стандардни Euler tour стабла. Сваки чвор упишемо када први пут уђемо у њега, а затим га поново упишемо сваки пут када се вратимо у њега из неког детета.

За овако добијен низ важи важна особина: ако су u и v два чвора и ако је fst[u] < fst[v], онда се lca(u,v) налази као чвор најмање дубине на делу Euler tour-а између fst[u] и fst[v].

Ово нам савршено одговара, јер у формулама изнад чворови x и y имају негативне коефицијенте. Дакле, када максимизујемо израз, за позицију са коефицијентом -1 или -2 аутоматски ће бити изабран чвор најмање дубине на одговарајућем интервалу, односно LCA.

Пуно решење

Потребно је динамички одржавати максимум израза облика:

c_0 dep[v_0] + c_1 dep[v_1] + c_2 dep[v_2] + c_3 dep[v_3] + c_4 dep[v_4]

где је:

v_0, v_1, v_2, v_3, v_4

растући подниз Euler tour-а, а коефицијенти су један од два низа:

(1, -2, 1, -1, 1)

или

(1, -1, 1, -2, 1)

Додатно, позиције са позитивним коефицијентом морају бити листови, и то њихова прва појава у Euler tour-у. Позиције са негативним коефицијентом могу бити било који чворови.

Ово можемо одржавати segment tree-јем.

У сваком чвору segment tree-ја чувамо динамику:

dp[t][i][j]

где је t један од два низа коефицијената, а i, j означавају да смо у том сегменту изабрали подниз који одговара коефицијентима од i до j-1.

Пошто имамо само 5 коефицијената, број стања је мали. За сваки од два типа имамо само:

\binom{6}{2} = 15

стања.

Када спајамо два сина segment tree-ја, радимо стандардно спајање динамике над поднизовима:

dp[i][j] = \max_{k=i}^{j} left[i][k] + right[k][j]

Ово значи да неки префикс траженог подниза узимамо из левог детета, а остатак из десног детета.

Почетне вредности у листу segment tree-ја

Нека једна позиција Euler tour-а представља чвор v.

Ако је тренутни коефицијент позитиван, онда ту позицију смемо искористити само ако је v лист и ако је ово прво појављивање тог листа у Euler tour-у.

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

На тај начин segment tree тачно бира три листа и два LCA чвора између њих.

Обрада промене тежине гране

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

Ако се промени грана која води ка чвору v, онда се дубине свих чворова у подстаблу чвора v промене за \Delta.

У Euler tour-у сва појављивања чворова из тог подстабла чине један интервал, па је довољно урадити range add на segment tree-ју.

Ако се свим дубинама у неком segment tree чвору дода вредност \Delta, онда се вредност стања које користи коефицијенте од i до j-1 повећава за:

\Delta \cdot (c_i + c_{i+1} + \ldots + c_{j-1})

Зато је довољно да унапред израчунамо префиксне суме коефицијената и lazy propagation ради директно над свим стањима.

Одговор

Одговор после сваке промене је максимум две вредности у корену segment tree-ја:

dp[0][0][5]

и

dp[1][0][5]

Прва вредност одговара случају када је lca(a,b) ближи корену, а друга случају када је lca(b,c) ближи корену.

Сложеност

Euler tour има дужину O(n), тачније највише 2n-1.

У сваком чвору segment tree-ја чувамо константан број стања, јер је број коефицијената увек 5. Зато је меморијска сложеност:

O(n)

Свака промена тежине гране је један range add над segment tree-јем, па је временска сложеност по промени:

O(\log n)

Укупна сложеност је:

O((n+q)\log n)

са веома малом константом, јер сваки чвор segment tree-ја има само 2 \cdot 15 стања.