Распоред
Ускоро…
Два торња
Аутор: Никола Милосављевић
Текст и тест примери: Алекса Милисављевић
Анализа решења: Немања Мајски
Тестирање: Софија Чебашек
Сви 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).
Такмичење
Аутор: Марко Миленковић
Текст и тест примери: Ања Дожић
Анализа решења: Ања Дожић
Тестирање: Алекса Милисављевић
Подзадатак 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)
Тајна Матрица
Аутор: Марко Миленковић
Текст и тест примери: Алекса Милисављевић
Анализа решења: Марко Миленковић
Тестирање: Драган Урошевић
Подзадатак 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
Напомена
Наравно, могуће је постићи боље временске сложености, али како су димензије матрице мале, то није неопходно за овај задатак.