[Решења задатака] 2023/2024 Квалификације - други круг

[milovanovic]

Надквадрат

Аутор: Владимир Миловановић
Текст и тест примери: Владимир Миловановић
Анализа решења: Владимир Миловановић
Тестирање: Александар Вишњић

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

За решење задатка довољно је пронаћи масимум и минимум по свакој координати од три задате тачке, а затим квадрирати већу од разлика двеју координата. Другим речима, ако су три тачке у Декартовом координатном систему задате координатама $(x_1, y_1)$, $(x_2, y_2)$ и $(x_3, y_3)$, тада је најпре неопходно пронаћи $x_\max = \max(x_1, x_2, x_3)$ и $x_\min = \min(x_1, x_2, x_3)$, те $y_\max = \max(y_1, y_2, y_3)$ и $y_\min = \min(y_1, y_2, y_3)$. Да се у задатку тражила површина минималног обухватајућег правоугаоника, онда би дужине страница тог правоугаоника биле $\Delta x = x_\max - x_\min$ и $\Delta y = y_\max - y_\min$. Међутим, с обзиром да се тражи површина минималног обухватајућег квадрата, то је страница квадрата заправо $\max(\Delta x, \Delta y)$, а површина тог квадрата $(\max(\Delta x, \Delta y))^2$ до чега се долази у константној временској и просторној сложености $\mathcal{O}(1)$. За све поене (последњи подзадатак) било је неопходно приметити имплементацијски детаљ да квадрирањем неке велике вредности може доћи до прекорачења, па је у програмском језику C резултат неопходно сместити у неки довољно велики цео број (конкретно long long у овом случају).

Да је уместо три, у општијем случају било задато $N$ тачака у простору, могао би се применити идентичан алгоритам, а његова сложеност била би $\mathcal{O}(N)$, то јест линеарна по броју задатих тачака чије се обухватање квадратом тражи.

[milovanovic]

Мања је матрица од матрице

Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Анализа решења: Младен Пузић
Тестирање: Александар Вишњић

У анализи решење сматраће се да први ред од горе има индекс $1$, последњи ред индекс $N$, прва колона слева има индекс $1$, а последња $M$.

Решење када $K = L = 1$

Лепота матрице је сума свих подматрица димензија $1 \times 1$, што је у ствари збир свих елемената матрице. Дакле, како год распоредили елементе, лепота матрице биће иста и то збир свих елемената низа $A$.

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

Решење када $N = M = 3, K = L = 2$

Пошто матрица има само $9$ поља, постоји $9! = 362.880$ могућности за распоређивање низа $A$ у матрицу. Назовимо матрицу $m$ - лепота матрице након фиксираног низа јесте (може се видети ако се испишу заједно суме свих подматрица димензије $2\times 2$):

$$
m_{1, 1} + 2\cdot m_{1, 2} + m_{1, 3} + 2\cdot m_{2, 1} + 4\cdot m_{2, 2} + 2\cdot m_{2, 3} + m_{3, 1} + 2\cdot m_{3, 2} + m_{3, 3}
$$

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

Временска сложеност је $O((NM)!)$, а меморијска $O(NM)$.

Решење када $K, L \leq 5$

Пошто су димензије посматраних подматрица мале, ми можемо грубом силом израчунати за свако поље у колико подматрица димензије $K \times L$ се налази, следећим алгоритмом:

• Иницијализујемо матрицу $cnt_{i, j} = 0$, за свако $1 \leq i \leq N$ и $1 \leq j \leq M$;
• За свако могуће горње лево поље $(x, y)$ (ово су сва поља за која важи $1 \leq x \leq N-K+1$ и $1 \leq y \leq M-L+1$):
  • За свако поље $(i, j)$ за које важи $x \leq i < x+K$ и $y \leq j < y+L$ увећати $cnt_{i, j}$ за један.

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

Временска сложеност је $O(NMKL + NM\log(NM))$, а меморијска $O(NM)$.

Решење када $0 \leq A_i \leq 1$

Пошто имамо само две могуће вредности, желимо јединице ставити у поља која се налазе у највећем броју подматрица димензије $K\times L$, док нуле стављамо у поља која се ређе појављују. Дакле, желимо да за свако поље ефикасно пронађемо у колико посматраних подматрица се налази (ово не зависи од расподеле елемената у матрици).

Када бисмо имали бесконачну таблу, поље $(i, j)$ би садржао сваки правоугаоник димензије $K\times L$ чији је горње лево поље $(x, y)$, где важи $i-K+1 \leq x \leq i$ и $j-L+1 \leq y \leq j$. Уколико урачунамо да ивице матрице могу да смање наш број опција, добијамо да мора да важи:

$$
\max(i-K+1, 1) \leq x \leq \min(N-K+1, i)
$$

$$
\max(j-L+1, 1) \leq y \leq \min(M-L+1, j)
$$

Из овога се може закључити да се број подматрица које садрже поље $(i, j)$, дакле, $cnt_{i, j}$, може израчунати формулом:

$$
cnt_{i, j} = (\min(N-K+1, i) - \max(i-K+1, 1) + 1) \cdot (\min(M-L+1, j) - \max(j-L+1, 1) + 1)
$$

Даље, избројимо број јединица у низу $A$ и решење је збир толико највећих елемената из матрице $cnt$.

Временска сложеност је $O(NM\log(NM))$, а меморијска $O(NM)$.

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

Попут решења када $0 \leq A_i \leq 1$ за свако поље проналазимо у колико посматраних подматрица се налази, а попут решења када $K, L \leq 5$ упарујемо највећи елемент низа $A$ са оном позицијом која се појављује у највише посматраних подматрица.

Временска сложеност је $O(NM\log(NM))$, а меморијска $O(NM)$.

[milovanovic]

Школице

Аутор: Александар Вишњић
Текст и тест примери: Александар Вишњић
Анализа решења: Игор Павловић
Тестирање: Александар Вишњић

Решење када $A_i = 1$

Стајање на било који степеник има исту “цену”. Потребно је стати на укупно што је мање могуће степеника. Решење зависи само од дужине низа за игру. За сваки упит је засебно рачунамо и нека она износи $M_i$ код $i$-тог друга. Решење код истог је $\lfloor \frac{M_i}{2} \rfloor$.

Решење када $N\leq 10, Q\leq 100$

Сваки низ за игру нема величину већу од $10$. Укупан број начина скакања није велик, те их можемо симулирати рекурзијом. Бирамо онај начин који даје најмањи резултат.

Решење када $N,Q \leq 4, 000$

Сазнајмо прво како решавамо задатак за један одређен низ за игру. Нека је тај низ $B_1,B_2,\ldots B_M$. Ово представља класичан задатак из динамичког програмирања. Нека је ${dp}_i$ минимална цена стајања на поље $i$ (почев од $0$, заједно уз све скокове до тог поља). Почетне вредности су ${dp}0 = 0$ и ${dp}1 = B_1$. За $i>1$ рекурентна веза је $${dp}i = \min({dp}{i-1},{dp}{i-2}) + B_i$$
Одговор на тражено питање је ${dp}{M+1}$. Неопходно је засебно разматрати случаје $M=0$ (низ за игру је празан) и $M=1$. У њима је одговор увек $0$.

Сложеност алгоритма по смицалици је $O(N)$. Дакле, укупно $O(Q\cdot N)$.

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

Неопходно је брже налазити одговоре за сваку смицалицу. Дозвољено нам је да пре њихових тражења израчунамо неке вредности у низу $A_1,A_2,\ldots , A_N$. Од користи ће бити слично динамичко програмирање као у претходном подзадатку. У овом чувамо и префикс и суфикс. Тачније, нека ${pref}_i$ представља најмању цену потребну за стајање на поље $i$ почев од поља $0$. А нека ${suf}_i$ представља најмању цену потребну за стајање на поље $i$ почев од поља $N+1$. Ова два низа се рачунају на аналоган начин са динамичким програмирањем из претходног подзадатка.

Прећимо сад на смицалице. Дајемо поступак за решавање случаја $1 < L \leq R < N$. Ивичне случаје остављамо читаоцу за вежбу. Приметимо да, користећи индексе из низа $A$, Перица мора стати на барем једно од поља $L-1$ и $R+1$ (јер је у низу за игру њихово растојање заправо $1$) . Формално, постоје $3$ случаја:

1. Перица је прошао само кроз поље $L-1$;
2. Перица је прошао само кроз поље $R+1$;
3. Перица је прошао кроз оба поља.

Кад спојимо све случаје, одговор на смицалицу постаје $$\min({pref}{L-1}+{suf}{R+2}, \ \ {pref}{L-2}+{suf}{R+1},\ \ {pref}{L-1}+{suf}{R+1})$$

Префиксне и суфиксне низове рачунамо у сложености $O(N)$. За сваку смицалицу налазимо решење у $O(1)$. Укупна сложеност је $O(N+Q)$.

[milovanovic]

Обарање руку

Аутор: Павле Мартиновић
Текст и тест примери: Александар Вишњић
Анализа решења: Павле Мартиновић
Тестирање: Павле Мартиновић

Решење када $N=4$

Овај задатак је могуће урадити грубом силом, али и ручно с обзиром да постоје само четири међусобно не-еквивалентна жреба, а то су $(1,2,3,4)$, $(1,3,2,4)$ и $(1,4,2,3)$, где сваком треба највише једна размена да би стигао до финала, осим најслабијем који свакако испада у првој рудни.

Решење када $P_i=i$

У овом задатку, као и у сваком надаље, је кључно описати услов за једну особу да ли може да стигне до неке рунде. Подтурнир дефинишемо као скуп свих људи који играју да би један од њих прошао у $k$-то коло. Да ли особа $x$ може стићи до $k$-рунде зависи да ли има $2^{k-1}-1$ играча које може да победи, (јер да би стигао до $k$-те рунде, мора бити најјачи у његовом подтурниру), и да ли има довољно размена на располагању да избацимо све јаче људе из тог подтурнира. Уколико имамо довољно размена на располагању, онда само све те јаче људе унутар подтурнира заменимо са слабијим људима ван подтурнира, којих има довољно због првог услова. Тако да сада знамо да одговоримо на питање да ли учесник може да стигне до рунде $k$ ако знамо број размена и број јачих од њега у том подтурниру. Знамо да постоји укупно $N-1$ подтурнира, и сваки учествује у $\log_2N$ подтурнира. Када добијемо ново питање, можемо за сваки подтурнир у коме тај човек учестује да одредимо да ли може да буде победник ту (број размена нам је дат, а број јачих у подтурниру можемо лако одредити због специфичности пермутације) и одговоримо на сва питања у $O(Q\log N)$.

Решење када је увек исти миљеник

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

Решење када $N\leq 17$, $Q\leq 100.000$

У сваком подтурниру можемо држати сортиран низ свих учесника тог турнира, а затим када хоћемо да видимо да ли миљеник може стићи до неког кола, бинарном претрагом по том низу сачуваном за тај подтурнир, можемо брзо наћи тачно колико њих је јачих у том подтурниру, и онда видети јел могуће стићи до тог кола исто као у другом подзадатку. Сложеност $O(N\log^2N+Q\log^2N)$.

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

Радимо упите у тзв. offline начину. Сортирамо упите по томе колика је јачина човека који је миљеник, а затим по томе колико размена имамо на располагању. Када решимо све упите за неког миљеника, прођемо кроз све подтурнире у којима он учествује и додамо $1$ на неки бројач. Када сад решавамо упите за неког следећег миљеника, у бројачу за сваки подтурнир ће стајати број учесника тог подтурнира који су слабији од тренутно посматраног (из чега, наравно, одмах можемо да нађемо и број јачих од посматраног). Даље, пошто је број размена потребан да стигне до $k$-тог кола растућа фунцкија, тако да сада, преко информација у бројачима можемо наћи у $O(1)$ колико најмање размена треба да би стигао до тог кола. Пошто је низ упита сортиран, методом 2 pointers, можемо одговорити на сваки упит за тренутног миљеника. Сложеност $O(N\log N+Q\log Q)$.

[milovanovic]

Пећински зечеви

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

Први подзадатак

У овим тестовима пећина се може представити као низ, и скок нагоре као прелазак на леви елемент низа.

Најједноставније решење је да се симулирају скокови сваког зеца: кренемо из његове почетне позиције, и сваки пут идемо у најлевљу достижну позицију. Другим речима, ако је $i$-ти зец тернутно на $v$-том месту слева, он ће у следећем кораку отићи на најлевљу позицију са платформом у интервалу $[v-i, v)$ (наравно, ако таква позиција не постоји, онда $i$-ти зец не може да изађе). Ово се лако налази ако имамо низ позиција са платформом, јер онда у том низу можемо бинарном претрагом наћи најмању позицију већу или једнаку $v-i$.

Приметимо да у овако траженом решењу сума висина било која два узастопна скока $i$-тог зеца мора бити већа од $i$ (иначе би се они могли заменити једним скоком), па је и број његових скокова ограничен одозго са $2\lceil \frac{N}{i} \rceil$. Укупан број скокова свих зечева биће ограничен одозго са $2 \sum \limits_{i=1}^n \lceil \frac{N}{i} \rceil$, што је $O(NlogN)$ (сума хармонијског реда), а пошто сваки скок тражимо у временској сложености $O(logN)$, укупна временска сложеност алгоритма биће $O(Nlog^2N)$.

Прва два подзадатка

Уместо низа, користићемо структуру std::set да чувамо позиције соба са платформом. Уместо бинарне претраге можемо онда користити функцију lower_bound, која такође ради у $O(logN)$.

Решење када је $X_i = 0$ за свако $i$

У овом задатку дато је стабло, али без промена стања чворова (соба). Слично као раније, потребно је пронаћи највишу слободну собу од првих неколико соба изнад дате (и то урадити пуно пута). Пошто нема промена, то је могуће урадити бинарним подизањем (binary lifting). Чувамо две sparse табеле, једну са информацијом о $2^k$-том претку, а другу са информацијом колико међу $2^k$ предака (рачунајући сам тај чвор у њих) постоји соба са платформом. Ове информације чувамо за сваки чвор и свако $k = 0,1,2,\ldots,\lfloor \log N \rfloor$.

Решење када је $N \leq 100.000$

Ове тестове пролазе спорије имплементације главног решења.

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

Присетимо се ранијих закључака. Потребно је $O(N\log N)$ пута наћи прву слободну собу међу $x$ предатака датог чвора. Такође, сада је потребно и подржати $O(N)$ промена соба. Стандардна идеја је употреба тешко-лаке декомпозиције стабла, која је од ове године у програму такмичења. Стабло партиционишемо у ланце на посебан начин. Први ланац креће из корена и наставља у чвор који има највише деце (рачунајући децу на свим дубинама). Понављамо поступак са новим крајем док не дође до листа стабла, чиме смо тада направили цео ланац. Избацивањем овог ланца настају нова подстабла, сваки са својим кореном. Алгоритам се врши за сваки од њих.

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

За дат почетни чвор, тврдимо да пролазимо кроз $O(\log N)$ ланаца декомпозиције приликом целе шетње (до изласка из пећине, тј. стабла). Нека је $s_p$ величина подстабла чвора $p$. Размотримо алгоритам који, почев од датог чвора, у сваком тренутку подиже тренутни за један изнад њега. Ако променимо ланац декомпозиције, бројач (иницијално $0$) се повећа за $1$. Посматрајмо ситуацију промене. Нека је претходни чвор $u$, наредни $v$, а $w$ чвор у коме се ланац од $v$ наставља. Због начина избора декомпозиције, важи $s_w \geq s_u$. Одавде је јасно $s_v > 2\cdot s_u$. Дакле, $s$-вредност тренутног чвора се повећа барем дупло. То се највише деси $O(\log N)$ пута, одакле следи тврдња.

Правилна имплементација доводи до решења сложености $O(N\log ^2 N)$. Комисија тврди да постоји и решење боље сложености. Такмичару остављамо за вежбу да га пронађе.

Алтернативно главно решење

Прво, размотримо алтернативно решење за низ. Постоји другачији начин да нађемо најлевљу слободну позицију у $[v-i, v)$: то је уједно и најлевља позиција $x$ за коју је број слободних позиција од $1$ до $x$ строго већи од броја слободних позиција од $1$ до $v - i - 1$. Упити “број слободних позиција од $1$ до $x$”, као и промене вредности неке позиције, могу се решити сегментним или Фенвиковим стаблом. Најлевља слободна позиција може се поново наћи бинарном претрагом, само што сада на овај начин у $O(logN)$ одговарамо на упит “постоји ли слободна позиција у $[v-i, x]$”. Дакле, укупна временска сложеност овог решења би била $O(Nlog^3N)$.

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

Размислимо како бисмо могли да то урадимо када не постоје промене. Можемо да прођемо кроз стабло претрагом у дубину из корена, и чувамо променљиву $x$ која представља суму од корена до тренутног чвора. Када уђемо у чвор, додајeмо његову вредност (у овом случају, $1$ ако има платформу, $0$ ако нема) у $x$. Када излазимо из чвора, одузимамо његову вредност од $x$. Оваквим поступком за сваки чвор имамо суму елемената од корена до њега.

Како се овде могу применити промене? Конструишемо низ $b$ величине $2N$ који одговара горенаведеном поступку: када улазимо у чвор, на крај низа додајемо његову вредност, а када излазимо, додајемо минус од те вредности. Нека су $in_v$ и $out_v$ позиције у низу $b$ које одговарају уласку у чвор $v$ и изласку из њега, редом. Тада је сума елемената у стаблу од корена до $v$ заправо сума елемената у низу $b$ од 1 до $in_v$.

Сада се решење за стабло своди на решење за низ, једино што при промени вредности чвора $v$ морамо у низу променити вредности у $in_v$ и $out_v$, што поново можемо урадити сегментним или Фенвиковим стаблом (мада је у овом случају, ради брзине и једноставности, боље користити Фенвиково). Такође, потребно нам је да брзо налазимо $k$-тог родитеља произвољног чвора, што се лако може урадити методом binary lifting.

Временска сложеност овог решења је $O(Nlog^3N)$, мада је у пракси доста брже: делом јер је бинарна претрага углавном ради на мањим скоковима (јер са већим скоковима завршавамо брже), делом јер су операције над Фенвиковим стаблом врло брзе. У сваком случају, константа решења је јако мала, и комисијина имплементација пролази за 2.5s.