[Rešenja zadataka] Državno 2020

Algoritam
1

Лек

Аутор: Никола Милосављевић
Текст и тест примери: Никола Пешић
Анализа решења: Димитрије Ердељан
Тестер: Александар Златески

Анализа

Пошто сваки елемент може бити део највише једног интервала који
окрећемо, знамо да важи следеће:

  • Ако A_i = i, тај елемент се не помера, тако да не сме бити део
    ниједног интервала.
  • Ако A_i \neq i, тај елемент мора бити део интервала који га доводи
    на позицију A_i.

Ако за неко i имамо A_i \neq i и A_{i-1} = i-1 (или i=1),
један интервал мора почињати на позицији i (јер не сме да обухвати
i-1) и имати дужину такву да A_i постави на исправну позицију:
A_i - i + 1.

Дакле, да би одредили позиције свих интервала, довољно је да прођемо
кроз цео низ и сваки пут када наиђемо на неко A_i \neq i, обрнемо
интервал дужине A_i - i + 1 и наставимо од прве позиције након тог
интервала (јер елементе које смо овиме померили не смемо да поново
померимо). Када дођемо до краја низа, у другом пролазу можемо
проверити да ли је сортиран: ако јесте, нашли смо (једино могуће)
решење, а ако није решење не постоји.

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

2

Вештица

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

Анализа

Почећемо од DP решења за овај проблем. Дефинисаћемо DP[row][pos] на следећи начин:

DP[row][pos] = најмањи број потеза који треба направити тако да полица у реду row почиње на позицији pos.

Нека W_i представља дужину i-тог реда, тј., W_i = R_i - L_i + 1. Тада за row > 1 и 1 \le pos \le M - W_{row} + 1, DP[row][pos] може да се израчуна на следећи начин:

DP[row][pos] = |pos - L_i| + \min_{offset = 0 \ldots W_{row} - W_{row - 1}} DP[row - 1][pos + offset]

За row = 1 имамо DP[1][pos] = |pos - L_1|.

Решење проблема је \min_{pos = 1 \ldots N - W_N + 1} DP[N][pos].

Анализа сложености

Лако је видети да горе описани начин за рачунање DP[row][pos] захтева највише O(N \cdot M \cdot M) корака – за свако од N \cdot M вредности (row, pos) треба W_{row} - W_{row - 1} + 1 \le M корака. N \cdot M \cdot M корака је преспоро за ограничења у овом задатку.

Једна опција је да израчунамо \min у дефиницији DP[row][pos] ефикасније него да посетимо свако од W_{row} - W_{row - 1} + 1 вредност у DP[row - 1]. За то постоје бар два начина.

– На пример, ако DP[row - 1] чувамо у сегментном стаблу онда можемо да нађемо \min датог интервала у O(\log M) времену.

– Или, рачунање DP[row][pos + 1] у односу на DP[row][pos] се разликује у томе што се ``прозор’’ од W_{row} - W_{row - 1} + 1 елемената који нам требају из DP[row - 1] помери за 1. То значи да ако бисмо применили Метод 3 са https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/, онда бисмо могли да израчунамо DP[row][pos + 1] у O(1) времену, под претпоставком да рачунамо у редоследу DP[row][1], DP[row][2], \ldots, DP[row][M - W_{row} + 1]. Ово би било довољно за решење које ради ефикасно на свим примерима.

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

Прецизнија анализа сложености

Да бисмо израчунали DP[row][pos] за све валидне вредности pos директно користећи формулу изнад треба нам (M - W_{row} + 1) \cdot (W_{row} - W_{row - 1} + 2) операција – (W_{row} - W_{row - 1} + 1) долази од \min, а додатна операција од |pos - L_i|. Када сумирамо за све row \ge 2, добијемо

\sum_{row = 2}^N (M - W_{row} + 1) \cdot (W_{row} - W_{row - 1} + 2) \le \sum_{row = 2}^N (M + 1) \cdot (W_{row} - W_{row - 1} + 2) =
=2 (N - 1) (M + 1) + (M + 1) \sum_{row = 2}^M (W_{row} - W_{row - 1}).

Сви елементи сем W_N и W_1 се згодно скрате у последњој суми, те добијемо

\sum_{row = 2}^N (M - W_{row} + 1) \cdot (W_{row} - W_{row - 1} + 2) \le 2 (N - 1) (M + 1) + (M + 1) (W_N - W_1) \le \le 3 (N - 1) (M + 1).

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

Оптимизација потрошње меморије

DP не можемо декларисати са 10000 \times 10000 поља јер то заузима више меморије него што је дозвољено. Уместо тога, довољно је да у меморији чувамо само DP[row] и DP[row - 1], где је row ред који се тренутно обрађује. То нам омогућава да знатно уштедимо на меморији.

3

Троокругао

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

Анализа

Најједноставније решење је за сваке три тачке проверити да ли формирају троокругао полупречника R - све што нам треба су координате центра описане кружнице. Ако су координате темена троугла (x_1, y_1), (x_2, y_2) и (x_3, y_3) а координате центра (x_c, y_c), тада изједначавањем растојања добијамо:
(x_1-x_c)^2 + (y_1 - y_c)^2 = (x_2-x_c)^2 + (y_2 - y_c)^2
(x_1-x_c)^2 + (y_1 - y_c)^2 = (x_3-x_c)^2 + (y_3 - y_c)^2
Након сређивања се губе квадрати уз x_c и y_c па добијамо само две линеарне једначине са две непознате. Уколико су решења целобројна и полупречник је R, повећамо решење за 1. Сложеност алгоритма је O(N^3) и решава подзадатак 1.

Скуп C свих могућих центара описаних кружница тражених троокруглова можемо добити тако што за сваке две тачке A и B одредимо (највише) 2 друге тачке које су и од A и од B удаљене тачно R и, уколико су целобројне, убацимо их у поменути скуп. Рачун за координте те две тачке је аналоган као у решењу подзадатка 1 (користмо и R овог пута) а могу се одредити и бинарном претрагом по симетрали дужи AB. Уколико се у скупу C нека тачка T јавља a пута, то значи да је на кружници полупречника R описаној око T тачно b тачака, где је a = \frac{b(b-1)}{2} јер смо сваки пар бројали тачно једном. Сваке 3 од тих b тачака формирају тражени троокругао па решењу треба додати \binom{b}{3} за сваку тачку T из C. Бројање појављивања сваке тачке је најлакше урадити сортирањем скупа S; како он садржи O(N^2) могућих центара, сложеност алгоритма је O(N^2 \log N) и решава подзадатке 1 и 2.

Ако је R = 1, задатак се своди на “колико једнакокрако-правоуглих троуглова са хипотенузом дужине 2 има међу датим тачкама?”. Ово се може решити провером за сваку од N тачака да ли је теме правог угла таквог троугла - нпр. ако проверавамо да ли постоји такав троугао чије је теме правог угла “надоле” и у тачки (x, y), треба испитати да ли се тачке (x-1, y+1) и (x+1, y+1) налазе међу датих N тачака. Уколико на почетку соритрамо тачке, ово испитивање можемо одрадити у O(\log N) преко бинарне претраге (може и преко неких других структура, нпр. C++ мапа). Сложеност овог приступа је O(N \log N) и решава подзадатак 3.

Означимо са minVal и maxVal најмање и највеће координате датих тачака. Центар описане кружнице траженог троокругла може бити само у делу координатне равни ограничен са [minVal - R, maxVal + R] \times [minVal - R, maxVal + R]. За сваку тачку из ове области можемо израчунати колико се датих тачака налази на растојању R од ње (ако их има a, тада има \binom{a}{3} троокруглова чији је центар описаног круга ова тачка) испитивањем свих O(R) кандидата (провера у сложености O(1) јер су координате мале и можемо маркирати тачке у матрици). Укупна сложеност овог алгоритма је O((maxVal - minVal + 2R)^2 \cdot R) и решава подзадатак 4.

Означимо са f(R) број целобројних тачака које се налазе на кружници полупречника R чији је центар у некој целобројној тачки. Нпр. f(1) = f(2) = f(3) = f(4) = 4, f(5) = 12, итд. (приметимо да није битно у којој целобројној тачки је центар). f(R) је заправо број целобројних решења једначине x^2 + y^2 =R^2 и сва та решења можемо пронаћи у сложености O(R) нпр. испробавањем свих могућности за x. Ово израчунамо на почетку и означимо скуп тих решења са \{(x_i,y_i), (x_2, y_2), \ldots, (x_{f(R)}, y_{f(R)}\}.
Уколико око сваке од N тачака опишемо кружницу полупречника R и све целобројне тачке са те кружнице (за тачку (x,y) тих f(R) целобројних тачака су (x+x_i, y+y_i), i = \overline{1, f(R)}) сместимо у један скуп (низ) C (величине N \cdot f(R)), тада је C скуп свих потенцијалних центара тражених троокруглова јер сваки такав центар мора бити на растојању R од бар једне од N тачака. Уколико се C састоји од M различитих тачака од којих се i-та појављује a_i пута, укупно решење је \binom{a_1}{3} + \binom{a_2}{3} + \ldots + \binom{a_M}{3}. Број понављања сваке тачке можемо израчунати сортирањем низа C и бројањем узастопних истих елемената. Зависно од тога да ли користимо QuickSort или CountingSort (прво по x па по y), сложеност алгоритма је O(N\cdot f(R) \cdot \log(N\cdot f(R))) или O(N \cdot f(R)).

Кључна ствар коју треба уочити је да су вредности f(R) “довољно мале” за дата ограничења - испоставља се да је за f(R) \leq 324 за свако 1\leq R\leq 10^5. Ово је интуитивно (обично нема баш пуно целобројних тачака на описаним кружницама) а могло се и лако проверити за време такмичења: уколико такмичар (на локалној машини) израчуна f(R) за свако R до 10^5 у укупној сложености O(R^2), добиће тражени резултат за 2-3 минута. Дакле, последњи описани алгоритам заиста решава цео задатак у задатом временском ограничењу.

4

Статистика

Аутор: Никола Милосављевић
Текст и тест примери: Димитрије Ердељан
Анализа решења: Димитрије Ердељан
Тестер: Иван Стошић

Анализа

Можемо поделити град на три дела: део који игноришемо (у примеру доле
обележен са ?), горњи леви (A) и доњи десни “троугао” (b):

AAAAAAAA
AA???bbb
AA???bbb
AAbbbbbb
AAbbbbbb

За оба троугла ћемо израчунати пар (m, n), где је m број случајева
у најздравијем пољу, а n број таквих поља. Ако смо добили (m_a, n_a) за горњи леви, а (m_b, n_b) за доњи десни, укупно решење
можемо одредити као:

  • (m_a, n_a), ако m_a < m_b
  • (m_b, n_b), ако m_a > m_b
  • (m_a, n_a + n_b), ако m_a = m_b

Горњи леви троугао можемо посматрати као два преклопљена правоугаоника
са једним теменом у горњем левом углу табле – на слици, A и a
(преклапање обележено са @):

@@aaaaaa
AA???...
AA???...
AA......
AA......

Као и раније, можемо одредити број случајева у најздравијем пољу и
број таквих поља у троуглу “сабирањем” ових решења за два
правоугаоника. У добијеном резултату ће поља обележена са @ бити
урачуната два пута и морамо елиминсати једно од појављивања – нека је
(m,n) “збир” правоугаоника A и a, а (m', n') обухвата само
@. Тада је укупно решење за троугао:

  • (m, n-n'), ако m = m' (нека од најздравијих поља јесу у @)
  • (m, n), ако m \neq m' (ниједно од тих поља није у @, тако да
    ништа нисмо бројали два пута).

Сада је само потребно да пре упита одредимо ове парове за сваки
правоугаоник са теменом у горњем левом углу матрице. Ово можемо
урадити у \mathcal{O}(N^2): сваки правоугаоник можемо посматрати као
унију доњег десног поља и “троугла”, вредност за троугао одредити као
што је горе описано (из претходно израчунатих вредности за мање
правоугаонике) и додати јој доње десно поље.

Исти поступак ћемо користити за доњи десни “троугао”, где унапред
одређујемо решења за правоугаонике са теменом у доњем десном углу.
Укупна сложеност је \mathcal{O}(N^2) за израчунавање ових вредности,
и \mathcal{O}(1) по упиту, односно \mathcal{O}(N^2 + Q) за цео
задатак.

5

Спец задатак

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

Анализа

Најпре, приметимо да је спец вредност подниза нула (што је и најмања могућа) ако тај подниз садржи нулу. Ово такође важи без обзира коју трансформацију применимо на низ. Тако да ћемо улазни низ поделити на максималне поднизове који не садрже 0. Сваки такав подниз ћемо звати не-нула.

Нека је A' један не-нула подниз. Прво ћемо за свако X које постоји у A' направити низ A_X = (i_1, i_2, \ldots, i_{n_X}), где је i_k индекс k-тог појављивања броја X у A', а n_X је број појављивања X у A'. Ове низове ћемо чувати у C++ map структури или сортиране по X тако да за дато X одговарајући низ можемо наћи у O(\log N) времену, нпр, бинарном претрагом ако низове чувамо сортиране по X. На исти начин ћемо обрадити све не-нула поднизове. Дакле, C++ map структура ће за дато X чувати више различитих A_X, највише једно A_X за дати не-нула подниз.

Решење за дато A_X

Најпре, ако је X = 1 или ако X не постоји у улазном низу, тада је решење тривијално – требало би исписати ``најлевљи’’ подниз дужине 1 који садржи не-нула вредност. Дакле, претпоставимо да X \ge 2 и нека је B_X неки подниз за X са највећом спец вредношћу. Нека K означава број појављивања X, а P дужину одговарајућег подниза. Лако је запазити да спец вредност подниза расте врло брзо, тј., експоненцијално, са повећањем K док расте линеарно са повећањем P. Врло корисна последица овог запажања је да B_X може да изостави највише \lfloor \log_X N \rfloor појављивања броја X – у супротном би цео одговарајући не-нула подниз А' имао строго већу спец вредност него B_X.

Ова запажања сада лако воде до решења: за дато X посматрајмо све поднизове од A_X од индекса L до индекса R (индекси крећу од 1) тако да L \le R и (L - 1) + (|A_X| - R) \le \lfloor \log_X N \rfloor; најбољи од тих поднизова је решење за A_X. За дато X, има највише (\lfloor \log_X N \rfloor + 1) \cdot (2 + \lfloor \log_X N \rfloor) / 2 таквих индекса L и R.

Решење за дато X међу свим не-нула поднизовима

За свако A_X ћемо наћи његов најбољи подниз R_X, где итерирамо по A_X из сваког не-нула подниза. Међу свим R_X ћемо исписати онај који имај највећу спец вредност; детаљи како да нађемо такав подниз су дати у наставку.

Смернице за алгоритам

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

Прво, кад једном израчунамо решење за X = Q_i, запамтићемо ово решење, на пример, у низу величине 1.000.000. Cледећи пут ако добијемо упит X = Q_j можемо да вратимо решење из тог низа.

Друго, током обраде упита за дато X, итерираћемо међу поднизовима од A_X (као што је описано изнад), и за сваки подниз исписати пар (c, P). У овом случају c представља број појављивања X у датом поднизу од A_X, а P представља дужину тог подниза. Претпоставимо да c_1 \ge c_2 (супротан случај се аналогно решава). Подниз са (c_1, P_1) има већу спец вредност од подниза са (c_2, P_2) акко X^{c_1} / P_1 > X^{c_2} / P_2, што повлачи X^{c_1 - c_2} \cdot P_2 > P_1. По конструкцији имамо c_1 - c_2 \le \lfloor \log_X N \rfloor, што повлачи да X^{c_1 - c_2} \cdot P_2 стаје у тип long long.

Користећи исту идеју за дато X можемо наћи најбољи подниз међу свим не-нула поднизовима. Када имамо више поднизова са истом спец вредношћу, онда бирамо онај који је ``левљи’’, као што је то описано у поставци задатка. Овај део решења се једноставно имплементира.

Процена сложености

За дато X обрада упита захтева време (\lfloor \log_X N \rfloor + 1) \cdot (2 + \lfloor \log_X N \rfloor) / 2 помножено са бројем не-нула поднизова који садрже X (заправо, сложеност је потенцијално мања јер није обавезно да сви поднизови садрже бар \lfloor \log_X N \rfloor појављивања броја X). Имамо (\lfloor \log_X N \rfloor + 1) \cdot (2 + \lfloor \log_X N \rfloor) / 2 \le 210, где се максимум достиже за X = 2. За X > 1000 имамо \lfloor \log_X N \rfloor \le 1, што повлачи да је (\lfloor \log_X N \rfloor + 1) \cdot (2 + \lfloor \log_X N \rfloor) / 2 \le 3 за већину вредности која се може наћи на улазу.

Број свих непразних поднизова A_X, за све вредности X, је највише N. То нам сада даје коначну сложеност од 210 \cdot N која је довољно мала за временско ограничење. Као што је наведено, разматрањем неколико случајева се може показати да се ова сложеност никад не достиже него да је бар неколико пута мања.

6

Фестивал

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

Анализа

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

Након тога, претпоставимо без губитка општости да тражимо најкраћи пут од интервала чији је почетак лево у односу на почетак другог интервала. Најбитнија ствар коју је потребно приметити овде јесте да је увек довољно да се крећемо (у десно) ка подинтервалу чији је почетак најудаљенији или ка надинтервалу чији је крај најудаљенији. Ако смо у првом кораку кренули ка подинтервалу, тада у наредном кораку идемо ка надинтервалу. Овај процес се наставља све док не стигнемо до траженог интервала или не можемо учинити наредни корак. Подстичемо такмичаре да докажу коректност овог приступа.

Решење у O(N \cdot Q)

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

Решење за све поене

У овом случају, кретање по интервалима је потребно имплементирати у логаритамској сложености, користећи такозвани “binary lifting”. Наиме, за сваки интервал чувамо интервале који се налазе на растојању 2^0, 2^1, 2^2,... 2^{\lfloor \log_2 N \rfloor}.

Решење у O(N^3)

У овом случају експлицитно конструишемо граф где су чворови интервали а ивице постоје између суседних интервала. Након тога, можемо одредити све парове најкраћих путева користећи БФС или Флојдов алгоритам. Пошто имамо N чворова и O(N^2) ивица, сложеност овог приступа је O(N^3), што је довољно за случај када је N \leq 500.

Решење за случај када су интервали или дисјунктни или је један подинтервал другог

У овом случају није тешко видети да је решење увек -1, 0, 1 или 2 (зашто?). Пошто смо разрешили случајеве када је решење 0 или 1, потребно је проверити да ли је решење -1 или 2. За сваки интервал, чувамо најшири интервал који га садржи. Уколико се најшири интервал који садржи почетни поклапа са најширим интервалом који садржи крајњи, тада је решење 2. У супротном је решење -1.