[Решења задатака] 2025/2026 ЕГОИ Изборно

Algoritam
1

Распоред

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

Текст и тест примери: Софија Чебашек, Марко Трајковић

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

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

Решење када је L_{j,i}=R_{j,i}

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

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

Решење када je N,M\leq10

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

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

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

Време посете сваког експоната ће припадати одговарајућим интервалима свих туриста, па ће припадати и њиховом пресеку. Прецизније, сваки експонат ће припадати интервалу [l_i,r_i] где је:

l_i=\max_{1\leq j \leq M}L_{j,i} \\ r_i=\min_{1\leq j \leq M}R_{j,i} \text{.}

Уколико за неки експонат важи l_i>r_i решење не постоји, у супротном, као у претходном подзадатку, за сваку пермутацију t можемо проверити да ли испуњава услове, тј. да ли важи l_i\leq t_i \leq r_i.

Вредности l_i и r_i ћемо у наставку називати лева граница и десна граница експоната i.

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

Решење када je M=1 и L_{j,i}=1

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

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

Решење када je M=1 и R_{j,i}-L_{j,i}\leq1

Посматрајмо експонат који ћемо прво посетити. За њега мора да важи l_i=1. Аналогно претходном подзадатку, изабраћемо онај са најмањим r_i. Кренућемо редом, од првог до N-тог тренутка. У i-том тренутку ћемо посматрати непосећене експонате којима је лева граница i или i-1 тј. оне чији интервали садрже тренутак i. Изабраћемо онај са најмањом десном границом. Уколико такав експонат не буде постојао у неком тренутку, нема решења. У супротном, конструисали смо једно решење.

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

Решење када je N\leq1000

Можемо уопшити решење претходног подзадатка. Разматраћемо тренутке редом, од првог до n-тог као у прошлом подзадатку. У i-том тренутку ћемо изабрати експонат са најмањом десном границом међу свим експонатима које нисмо посетили и чији интервали садрже тренутак i. Ако такав експонат не постоји, нема решења, а у супротном смо овим поступком конструисали једно решење.

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

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

Приметимо да експонате можемо сортирати по њиховој левој граници и обрађивати у том редоследу. Оваквим приступом и коришћењем структура std::set или std::priority_queue можемо ефикасно чувати све експонате у чијим интервалима је тренутак i као и ефикасно наћи онај са најмањом десном границом.

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

2

Два торња

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

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

Анализа решења: Немања Мајски

Тестирање: Софија Чебашек

Сви h_i су једнаки

Нека је висина свих блокова једнака H. Уколико је N парно, можемо ставити \frac{N}{2} блокова на један и \frac{N}{2} блокова на други торањ. Висина оба торња је H \cdot \frac{N}{2}.

Уколико је N непарно, немогуће је да сваки блок чини неки торањ, пошто би један торањ имао паран, а други непаран број блокова. Тако да је најбоље да се оба торња формирају са \frac{N-1}{2} блокова и њихова висина ће бити H \cdot \frac{N-1}{2}.

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

N\le 100, h_i = i

Нека су a и b произвољни природни бројеви за које важи 1 \le a,b \le N. Приметимо да је h_a + h_b = h_{a+1} + h_{b-1}. Претпоставимо да смо нашли неки начин да од првих m \le N-4 блокова направимо два торња исте висине. Онда можемо да додамо блокове m+1 и m+4 на први торањ, а блокове m+2 и m+3 на други. На тај начин смо направили два торња једнаке висине од првих m+4 блокова. Овај поступак називамо алгоритмом проширивања.

Разликујемо следеће случајеве:

  • Уколико је број N дељив са 4, одговор је половина збира свих висина. Односно \frac{N \cdot (N+1)}{4}. То можемо постићи тако што само примењујемо алгоритам проширивања.
  • Уколико је остатак при дељењу броја N са 4 једнак 1 , онда ће збир свих висина бити непаран. Тако да је немогуће да сваки блок буде део торња. Ако је N=1, онда је одговор 0. Иначе можемо направити два једнака торња од блокова са висинама 2, 3, 4, \ldots, N. На први торањ ћемо ставити блокове 2 и 5. На други торањ ћемо ставити блокове 3 и 4. Затим примењујемо алгоритам проширивања да би ставили остале блокове. Висина оба торња је \frac{N \cdot (N+1) - 2}{4}.
  • Уколико је остатак при дељењу броја N са 4 једнак 2 , онда ће збир свих висина бити непаран. Тако да је немогуће да сваки блок буде део торња. Ако је N=2, онда је одговор 0. Иначе можемо направити два једнака торња од блокова са висинама 2, 3, 4, \ldots, N. На први торањ ћемо ставити блокове 2, 3 и 5. На други торањ ћемо ставити блокове 4 и 6. Затим примењујемо алгоритам проширивања да би ставили остале блокове. Висина оба торња је \frac{N \cdot (N+1) - 2}{4}.
  • Уколико је остатак при дељењу броја N са 4 једнак 3, могуће је да сваки блок буде део торња. На први торањ ћемо ставити блокове 1 и 2. На други торањ ћемо ставити блок 3. Затим примењујемо алгоритам проширивања да би ставили остале блокове. Висина оба торња је \frac{N \cdot (N+1)}{4}.

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

N \leq 17

Укупно постоји 2^N начина да одаберемо које ћемо блокове искористити у неком од торњева. Можемо за сваки од њих да проверимо да ли је могуће од изабраних блокова направити два торња исте висине.

Рецимо да смо изабрали да направимо два торња од блокова чије су висине v_1, v_2, \ldots v_k. Питамо се да ли је могуће од њих направити два торња исте висине. Довољно је проверити да ли може један торањ да буде висине S = \frac{v_1 + v_2 + \ldots + v_k}{2}, пошто ће други торањ направљен од осталих блокова бити исте висине.

За ту проверу користимо динамичко прогамирање. Имамо S \times k матрицу dp, где вредност dp_{i,j} говори о томе да ли је могуће од првих j блокова направити торањ са висином i. Важи да је dp_{i,j} могуће само ако је могуће dp_{i,j-1} или dp_{i-v_j,j-1}.

Нека је H највећа вредност h_i. Временска сложеност је O(2^N \cdot N^2 \cdot H), а меморијска сложеност је O(N^2 \cdot H).

N, h_i \le 50

Нека је S сума свих вредности h_i у низу.

У овом подзадатку ћемо да користимо динамичко програмирање. Имаћемо матрицу dp димензија N \times \frac{S}{2} \times \frac{S}{2}. Вредност dp_{i, a, b} представља да ли је могуће да користећи само првих i блокова направимо два торња таква да је први висине a, а други висине b. Вредност dp_{i, a, b} је могуће само ако је нека од следећих вредности такође могућа:

  • dp_{i-1, a, b}, блок i није део ни једног торња;
  • dp_{i-1, a-h_i, b}, блок i је део првог торња;
  • dp_{i-1, a, b-h_i}, блок i је део другог торња.

Такође приметимо да док итерирамо по i, нама је важан само dp_{i-1, a, b} за свако 0 \le a,b \le S, тако да можемо памтити само тренутни dp_{i, a, b} и претходни dp_{i-1, a, b}, чиме је меморијска сложеност O(S^2).

Временска сложеност је O(N \cdot S^2).

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

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

То је мотивација да променимо dp. dp_{i, d} ће бити матрица димензије N \times S, где је dp_{i, d} највећа могућа висина вишег торња ако се од првих i блокова направе торњеви чија је апсолутна разкика висина тачно d.

Вредност dp_{i, d} је максимум од следећег:

  • dp_{i-1, d}, блок i неће чинити ни један торањ;
  • dp_{i-1, d+h_i}, блок i ће се ставити на нижи торањ;
  • dp_{i-1, d-h_i} + h_i, блок i ће се ставити на виши торањ.

Као и у претходном подзадатку, када рачунамо dp_{i, d}, за 0 \le d \le S, нама требају само вредности dp_{i-1, d}. Тако да је меморијска сложеност O(S), док је временска сложеност O(S \cdot N).

3

Такмичење

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

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

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

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

Подзадатак 2: Q=1, k_1=N

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

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

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

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

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

За почетак ћемо направити низ разлика између суседних елемената и затим над њим направити сегментно стабло. Помоћу тог стабла ћемо наћи максималне разлике у свим поднизима дужине k и од њих изабрати најмању.

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

Подзадатак 4: Q\leq300

Као и у прошлом подзадатку, и овде треба да нађемо подниз дужине k_i, за свако 1\leq i\leq Q који има најмању максималну апсолутну разлику. Овде ћемо за то користити deque и низ разлика који је коришћен и у претходном задатку.

У deque-у ћемо чувати позиције елемената и додаваћемо их на следећи начин: ако је елемент на позицији i већи од елемента на позицији са краја реда, позицију са краја реда склањамо јер знамо да нам разлика на тој позицији неће бити релевантна када убацимо позицију i. Склањамо све позиције елемента из реда, док не дођемо до прве за коју је њен елемент већи од елемента на позицији i, када се то деси, индекс i стављамо на крај реда. Приметимо да ће разлике поређане по реду у ком су индекси унесени у deque бити сортиране опадајуће.

За првих k-1 елемната, само ћемо додавати индексе на раније објашњен начин, док ћемо од k-тог, након додавања у ред, кренути да тражимо максималан у одговарајућем интервалу. То радимо тао што крећемо од почетка реда, где ће се налазити позиција највеће сачуване разлике на коју смо до тог тренутка наишли и гледамо да ли она припада поднизу који се завршава на позцији коју у том тренутку посматрамо. Ако не припада, бришемо ту позицију са почетка реда и настављамо даље док не наиђемо до оне која припада. Вредност на њој је максимална вредност за посматрани подниз.

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

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

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

Када активирамо разлику на позицији i, провераваћемо да ли су разлике на позицијама i-1 и i+1 активиране, и ако нека од њих јесте, њену групу спајамо са разликом на позицији i. То спајање можемо извршити примењујући DSU, или једноставно памтећи најлевљи и најдешњи елемент сваке групе, и апдејтујући их након спајања.

Када спојимо две групе дужина m и n преко разлике i, добићемо групу дужине m+n+1 и знаћемо да је највећа разлика у њој управо разлика на позицији i јер је она последња активирана а знамо да их активирамо у растућем редоследу. Тада ћемо у посебан низ ans, где је ans[i] најмања максимална разлика која може да се добије за k=i, унети вредност разлике i ако је она мања од тренутне вредности за ans[m+n+1]. На крају морамо још једном проћи кроз низ ans како бисмо попунили разлике за оне дужине које нисмо добили при спајању. Пошто важи да је решење монотоно (за веће k одговор не може бити мањи), можемо пропагирати вредности уназад: ans[k] = min(ans[k], ans[k+1]).

На крају сваки упит можемо одговорити у O(1).

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

4

Тајна Матрица

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

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

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

Тестирање: Драган Урошевић

Подзадатак 1: 1 \leqа_{ij} \leq 2

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

Временска сложеност: O(1), број упита: 0.

Подзадатак 2: q=nm

У овом подзадатку питаћемо за свако поље у матрици и исписати тачну суму.

Временска сложеност: O(nm), број упита: nm.

Подзадатак 3: m=1

У овом подзадатку решавамо случај када је матрица заправо низ. Зарад лакше анализе претпоставимо да је n=2^k степен двојке. Посматрајмо следећу суму:

a_1 + a_2 + a_4 + a_4 + a_8 + a_8 + a_8 + a_8 + a_{16} + \ldots + a_{2^k}

Очигледно је да је наша сума мања или једнака правој јер знамо да је низ растућ. С друге стране, уколико помножимо цео израз са два, добијамо: 2a_1 > a_1, 2a_2 \geq a_2 + a_3, 8a_4 \geq a_4 + a_5 + a_6+ a_7. Ово показује да наша апроксимативна сума није дупло мања од праве суме. Овим завршавамо доказ тачности.

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

Временска сложеност: O(n), број упита: \lceil \log_2(n) \rceil

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

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

Ипак, довољно је да само помножимо целу нашу апроксимативну суму са два. Онда је наша нова апроксимативна сума највише дупла права сума, а барем половина праве суме.

Временска сложеност: O(nm), број упита: \lceil \log_2(n)\rceil \cdot \lceil \log_2(m) \rceil

Напомена

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