Takmičarsko okruženje i tekstovi zadataka nalaze se ovde.
Задатак Б1: Пола-пола
Аутор: Иван Стошић
Текст и тест примери: Иван Стошић
Анализа решења: Владимир Миловановић
Тестер: Слободан Митровић
Анализа
Кључно је увидети да је најефикаснији начин за решавање овог проблема коришћење листи (или пак двостраних редова) као структуре података за чување слова. Прецизније говорећи, неопходне су две овакве структуре у којима би се у сваком тренутку чувале и одржавале прва, односно друга половина тренутног низа слова.
Свако (непарно) убацивање новог слова заправо представља додавање новог члана на крај једне листе (реда), при чему треба водити рачуна да се приликом сваког другог (тј. парног) додавања, први члан те листе (реда) избаци и дода на крај прве листе (реда). Тиме би обе листе (реда) у сваком тренутку биле или подједнаке дужине или би се разликовале највише за један члан.
Операција замене редоследа прве и друге половине се своди на тривијалну замену два показивача и одвија се само када су листе (редови) једнаких дужина. Како се додавање и пребацивање чланова, као и промена места над овим структурама података могу урадити у константној сложености, \mathcal{O}(1), и како укупно имамо N оваквих операција, тако је, рачунајући ту и крајње исписивање резултата, задатак на овај начин решен у линеарној \mathcal{O}(N) временској сложености.
3 Likes
Задатак Б2: Трик
Аутор: Владимир Миловановић
Текст и тест примери: Душан Здравковић
Анализа решења: Владимир Миловановић
Тестер: Иван Стошић
Анализа
Најпре, лако се доказује да у општем случају за произвољно N, није могуће склопити одговарајући низ без џокера. Наиме, како картице означене непарним бројевима, 1, 3, 5,\ldots, морају садржати непаран број картица између њих, ове картице се увек појављују на местима у низу, односно индексима, са истом парношћу. Са друге стране, картице означене парним бројевима, 2, 4, 6,\ldots, садрже паран број картица између њих, па се стога појављују на позицијама супротне парности. У низу који садржи само 2N картица, постоји тачно N парних и тачно N непарних индекса, од којих би, без смањења општости уз претпоставку да је N парно, по N/2 парних и непарних позиција било заузето картицама са парним бројевима на себи, то јест, 2, 4, 6,\ldots, па би након њиховог распоређивања у низу преостало N/2 парних и N/2 непарних индекса без могућности да се картице означене непарним бројевима, 1, 3, 5,\ldots, распореде на одговарајући начин.
Иако је описани низ немогуће саставити без џокера, за произвољно N потребан је и довољан само један џокер да се испуне услови описани поставком задатка. Није тешко уочити да се све картице означене непарним и парним бројевима могу угнездити једна у другу на следећи начин за непарно N:
- N, N-2, N-4,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-4, N-2, N
- N-1, N-3, N-5,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-5, N-3, N-1
односно на идентичан начин и за парно N:
- N-1, N-3, N-5,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-5, N-3, N-1
- N, N-2, N-4,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-4, N-2, N
те се њиховим спајањем добија решење које садржи укупно три џокера (једног у поднизу картица означених непарним и два у поднизу картица означених парним бројевима).
У сваком случају, сада између несуседних џокера тако спојених поднизова има тачно N, то јест N+1 картица, међу којима су и по једна картица означена бројевима N-1 и N, без обзира на то да ли је N парно или непарно и који је од угнежђених поднизова први, а који други, односно:
- N-1, N-3, N-5,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-5, N-3, N-1, N, \\ N-2, N-4,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-4, N-2, N
- N, N-2, N-4,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-4, N-2, N,\\ N-1, N-3, N-5,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-5, N-3, N-1
Уколико сада, (у првом случају) извадимо картице означене бројем N-1 добићемо тачно N-1 картицу између два ближа несуседна џокера:
- N-3, N-5,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-5, N-3, N,\\ N-2, N-4,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-4, N-2, N
- N, N-2, N-4,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-4, N-2, N,\\ N-3, N-5,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-5, N-3
па заменом одговарајућих џокера картицама означеним са N-1 добијамо тражени низ, то јест:
- N-3, N-5,\ldots, 7, 5, 3, 1, N-1, 1, 3, 5, 7,\ldots, N-5, N-3, N, \\ N-2, N-4,\ldots, 6, 4, 2, N-1, J, 2, 4, 6,\ldots, N-4, N-2, N
- N, N-2, N-4,\ldots, 7, 5, 3, 1, N-1, 1, 3, 5, 7,\ldots, N-4, N-2, N, \\ N-3, N-5,\ldots, 6, 4, 2, N-1, J, 2, 4, 6,\ldots, N-5, N-3
за парно и непарно N, респективно.
Слично томе, било је (у другом случају) могуће извадити и картице означене бројем N, па би између друга два несуседна џокера било N картица:
- N-1, N-3, N-5,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-5, N-3, N-1,\\ N-2, N-4,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-4, N-2
- N-2, N-4,\ldots, 7, 5, 3, 1, J, 1, 3, 5, 7,\ldots, N-4, N-2, N-1, \\ N-3, N-5,\ldots, 6, 4, 2, J, J, 2, 4, 6,\ldots, N-5, N-3, N-1
чијом бисмо заменом картицама означеним бројем N на још један могући начин добили тражени низ, заправо:
- N-1, N-3, N-5,\ldots, 7, 5, 3, 1, N, 1, 3, 5, 7,\ldots, N-5, N-3, N-1, \\ N-2, N-4,\ldots, 6, 4, 2, J, N, 2, 4, 6,\ldots, N-4, N-2
- N-2, N-4,\ldots, 7, 5, 3, 1, N, 1, 3, 5, 7,\ldots, N-4, N-2, N-1, \\ N-3, N-5,\ldots, 6, 4, 2, J, N, 2, 4, 6,\ldots, N-5, N-3, N-1
такође за парно и непарно N, респективно.
Претходним се доказује да је у општем случају користећи само једну џокер картицу могуће конструисати тражени низ за произвољно N, па је и сложеност овог алгоритма линеарна по N, односно \mathcal{O}(N). Тривијалним додавањем преосталих K-1 џокера било на почетак или на крај овако формираног низа, задатак је решен у укупној сложености \mathcal{O}(N+K).
3 Likes
Задатак Б3: Есикез
Аутор: Иван Стошић
Текст и тест примери: Иван Стошић
Анализа решења: Драган Урошевић
Тестер: Алекса Плавшић
Анализа
Лако се закључује да је потребно одредити најдужи заједнички подниз за низове који представљају боје фонтана на два булевара из задатка. Такође је добро познат алгоритам базиран на динамичком програмирању за одређивање најдужег заједничког подниза два дата низа. Међутим, сложеност тог алгоритма Је једнака \Theta(NM), где су и дужине та два низа.
Оно што карактерише ове низове је чињеница да су у сваком од њих све вредности међусобно различите. Означимо са a и b та два низа. Онда ћемо формираи трећи низ који ће имати исти број елемената као низ b, тако да је c_i индекс елемента низа a који се поклапа са елементом b_i (ако такав елемент не постоји онда ће одговарајући елемент низа c имати вредност -1). Након тога ћемо из низа c избацити све елемент који имају вредност -1 и оно што је остало у низу c су индекси елемената низа a који се појављују у низу b, али баш у редоследу у коме се појављују (од почетка према крају низа b).
Није тешко закључити да ће дужина најдужег заједничког подниза за низове a и b бити једнака дужини најдужег растућег подниза (не обавезно узастопних елемената) низа c.
Најдужи растући низ низа c можемо одредити коришћењем динамичког програмирања. Обрађује се један по један елемент низа c и након обраде i-тог елемента позната је дужина најдужег растућег подинза за низ кога чини првих i елемената низа c (нека је то h) и такође за свако g \leq h је позната најмања могућа вредност последњег елемента у растућем поднизу дужине g )те вредности образују низ који ћемо назвати d). При обради i+1-ог елемента низа c одређује се најмањи индекс g са особином да је c_{i+1} < d_g, То значи да је $$d_{g-1} < c_{i+1} < d_g$. Ако такав елемент не постоји онда се c_i може додати на крај низа дужине h и формирати растући подниз дужине h+1 (тј. вредност за h се повећава за 1 и вредност одговарајућег d_h се изједначава са c_{i+1}). У супротном се може смањити вредност d-G (тј. најмања могућа вредност последњег елемента у растућем поднизу дужине g).
Ако на описани начин обрадимо све елементе низа c, крајња вредност за h ће бити дужина најдужег растућег подниза (тј. решење нашег задатка).
3 Likes
Задатак А1: Супер Велика Матрица
Аутор: Алекса Плавшић
Текст и тест примери: Алекса Плавшић
Анализа решења: Драган Урошевић
Тестер: Иван Стошић
Анализа
Овај проблем се може решити коришћењем похлепног алгоритма. Рушимо редом зграде почевши од прве. Ако тренутно рушимо i-ту зграду онда можемо одредити скуп деце \{j_1, j_2, ..., j_p\} који могу да учествују у рушењу те зграде (тј. број i припада интервалима зграда које могу рушити та деца-духови). Ако не постоји ниједно дете које може рушити ту зграду, онда град не може бити уништен. Ако постоји бар једно дете које може рушити ту зграду, онда бирамо оно дете из скупа \{j_1, j_2, ..., j_p\} које има најмању вредност за R, односно чији интервал зграда које може рушити се најраније завршава.
Ако је број преосталих спратова мањи од броја струјних удара које има на располагању то дете, онда уништимо зграду, нотирамо да се број струјних удара тог детета смањио за број порушених спратова и прелазимо на следећу зграду.
Ако је број струјних удара мањи или једнак од висине те зграде, онда применимо све струјне ударе тог детета и смањимо висину зграде за број примењених струјних удара. Како је то дете већ потрошило своју моћ, избацујемо га из скупа деце коју можемо користити за рушење. Ако је висина зграде постала нула, онда је она порушена и прелазимо на следећи зграду.
При преласку на следећу зграду, морамо ажурирати скуп деце која могу бити коришћена за рушење: избацују се она деца код којих је десни крај интервала мањи од тренутне зграде и додају деца чији је леви крај једнак индексу те зграде.
Да би убрзали тај поступак додавања деце коју можемо користити за рушење, деца се на почетку сортирају по левим крајевима интервала.
Како би ефикасно бирали дете које ће рушити зграду (тј. дете које има најмањи десни крај), децу која могу рушити тренутну зграду држимо у приоритетном реду.
Сложеност дела за сортирање деце је O(n\log n), а сложеност рушења ће бити O((n+m)\log n).
1 Like
Задатак А2: Сорт на стаблу
Аутор: Душан Живановић
Текст и тест примери: Алекса Плавшић
Анализа решења: Никола Јовановић
Тестер: Никола Јовановић
Анализа
Ако размислимо о начинима на које се стабло може користити при сортирању природно се намећу замене, па уместо оригиналног проблема сортирања посматрајмо прво проблем замене два суседна елемента из низа, конкретно златника на индексима k-1 и k. Назовимо чвор стабла најближи корену који има више од једног сина ,,рачва’’. Замену златника вршимо тако што преместимо део низа закључно са индексом k-2 негде у дубину стабла, затим поставимо златнике са индексима k-1 и k у различита подстабла рачве, вратимо их у низ у обрнутом редоследу, и затим вратимо део низа закључно са индексом k-2 (истим редом). Потребан и довољан услов за ово је да подстабло рачве (не укључујући саму рачву) има барем k елемената. Лако се види да у супротном златници на индексима k-1 и k никада не могу заменити места.
Сада када знамо процедуру за замену два суседна златника алгоритмом налик на bubble sort изводимо сортирање целог низа. Сортирање је могуће уколико је могућа замена пара суседних златника са највећим индексима (приметимо да ово нису увек златници n-1 и n, јер неки суфикс низа може бити већ сортиран). Простим поређењем величине подстабла рачве и индекса последњег златника који није на свом месту добијамо одговор на упит.
Смернице за алгоритам
Оба броја потребна за решавање упита можемо једноставно наћи. Једним пролазом кроз низ златника налазимо последњи индекс k такав да је p_k \neq k. Проласком кроз стабло налазимо рачву и величину одговарајућег подстабла, R. За R >= k исписујемо DA, а у супротном NE. У задацима са више упита тј. више тест примера по једном покретању програма важно је посебну пажњу обратити на глобално стање програма које је неопходно reset-овати између тест примера. У овом задатку би пример био број деце за сваки чвор у стаблу - уколико заборавимо да анулирамо ово поље можемо добити неочекиване резултате.
2 Likes
Задатак А3: Обарање
Аутор: Никола Милосављевић
Текст и тест примери: Никола Милосављевић
Анализа решења: Никола Милосављевић
Тестер: Душан Здравковић
Анализа
Означимо (произвољну) тачку пробадања са $T$ и нека је њено растојање до најудаљенијег темена правоугаоника једанко $r_T$. Није тешко закључити да, окретањем око тачке пробадања, правоугаоник покрива површ која је заправо круг $K(T, r_T)$ са центром у $T$ и полупречником $r_T$. Дакле, треба изабрати тачку $T$ унутар правоугаоника такву да круг (укључујући и границу) $K(T, r_T)$ садржи што мање од датих $N$ тачака; oзначимо број тачка унутар поменутог круга са $c(T)$ а са $opt$ - оптимално решење (које треба израчунати).
Нека су темена правоугаоника $ABCD$, његов центар $O$ а $P_1$, $P_2$, $P_3$ и $P_4$, редом, средишта страница $BC$, $CD$, $DA$ и $AB$. Означимо са $a$ дуж $P_1P_3$ (хоризонтална средња линија) а са $b$ дуж $P_2P_4$ (вертикална средња линија). Нека су тачке у којима су такмичари $Q_1, Q_2, \ldots, Q_N$. Иако се најмања вредност $r_T$ достиже када је $T = O$, нама није битан само полупречник већ и позиција круга. Следећа лема представља кључно запажање:
Лема: Постоји тачка $T$ која припада $a \cup b$ и за коју је $c(T) = opt$.
Заиста, посматрајмо било коју оптималну тачку пробадања $T$ – нека је, без умањења општости, у доњем-десном “квадранту” тј. правоугаонику $P_4BP_1O$. Тада је одговарајући круг $K(T, |TD|)$. Нека је $T’$ пресечна тачка дужи $TD$ и $a \cup b$ (ако их има више, нека је то пресечна тачка ближа $T$). Није тешко уочити да се пробадањем у тачки $T’$ добија круг $K’(T’, |T’D|)$ који је цео садржан у кругу $K(T, |TD|)$ па важи $c(T’) \leq c(T)$. Дакле, заиста је довољно разматрати само тачке на “средњим линијама правоугаоника” за оптималну тачку пробадања.
Најлакши начин је разликовање 4 случаја тј. тражење оптималне тачке на дужима $OP_1$, $OP_2$, $OP_3$ и $OP_4$. Размотримо случај када је тачка $T$ на $OP_1$ – тада ће полупречник круга бити $|TD|$. Нека су $x$-координате тачака $O$ и $P_1$, редом, $L$ и $R$. Нека је $Q_i$ произвољна тачка и нека је $X_i$ пресек дужи $OP_1$ и симетрале дужи $Q_iD$ (уколико пресек постоји). Да би тачка $Q_i$ била ван круга $K(T, |TD|)$, тачка $T$ мора бити са “праве стране” тачке $X_i$; прецизније, ако је $Q_i$ “лево” од странице $CD$, мора важити $T \in (X_i, R)$ а ако је $Q_i$ “десно” од $CD$, мора важити $T \in (L, X_i)$.
На овај начин добијамо највише $N$ подинтервала интервала $(L, R)$ и задатак се своди на одабир тачке из $(L, R)$ коју садржи највише поменутих интервала (одговарајући круг са центром у тој тачки неће садржати тачно оне тачке које одговарају интервалима које садрже тај центар). Ово се може решити на неколико начина а најлакши је сортирати крајеве интервала, свим левим крајевима доделити $+1$, свим десним $-1$ и одабрати тачку тако да је сума крајева интервала лево од ње највећа могућа. Сложеност овог алгоритма је $O(N \log N)$ због сортирања.
За лакшу имплементацију поменутог алгоритма, корисно је на почетку транслирати слику тако да је центар правоугаоника у $(0,0)$. Додатно, исти алгоритам се може искористити 4 пута (увек тражење центра на дужи $OP_1$) при чему се пре сваког позива цела слика ротира $90^\circ$ улево. Тражење одговарајућих тачака $X_i$ на дужи $OP_1$ се може урадити једноставном аналитичком геометријом (уколико je слика центрирана и за тачку $Q_i=(x_i,y_i)$ важи $x_i \neq x_D$, тада је пресек одговарајуће симетрале са $x$-осом управо у тачки $X_i = \frac{1}{2}(\frac{(y_i - y_D)(y_i+y_D) + (x_i + x_D)(x_i -x_D)}{x_i - x_D})$ ); вредност $X_i$ је могуће одредити и тернарном претрагом - тражење тачке (на датој дужи) која је подједнако удаљена од $D$ и $Q_i$.
Подзадаци: за први подзадатак је увек оптимално да центар буде у средишту дужи $AB$ (доња страница правоугаоника). За други подзадатак је довољна анализа неколико случајева (што се своди на проверу да ли два интервала имају пресек). У трећем подзадатку је довољно испитати да ли постоји тачка која је садржана у свим интервалима што се може урадити једноставније у $O(N)$; такође, могућ је и следећи приступ: за сваку тачку $Q_i$ одредимо геометријско место тачака оптималног центра тако да одговарајући круг не садржи дату тачку - може се показати да је тај скуп тачака у општем случају четвороугао; затим проверимо да ли је пресек свих таквих скупова непразан. У четвртом подзадатку је је довољно одредити тражену тачку на интервалу $(L,R)$ у сложености $O(N^2)$.
4 Likes