[Rešenja zadataka] 2020/2021 Kvalifikacije - Drugi krug

[MladenP]

Квадрати

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

Приметимо најпре да ако су задата два темена на истој страници квадрата, тада мора важити да је x_1 = x_2 или y_1 = y_2. Тада постоје два квадрата који испуњавају услове, а они су централно симетрични у односу на задату страницу. Ако су задата два антиподална (дијаметрално супротна) темена, неопходно је проверити да важи да је |x_1 - x_2| = |y_1 - y_2|. У овом случају постоји тачно један квадрат. У свим осталим случајевима решење је 0.

[MladenP]

Узгајивачи јабука

Главна идеја у овом задатку је да ће СПАУЈ увек одабрати као стопу пореза један од елемената низа P. Да бисмо то доказали, претпоставимо супротно, да нам је оптимално узети за порез x посто, где је x различито од свих елемената низа P. Узмимо први већи елемент низа P и означимо га са y. Може се лако приметити да ће за оба та избора (и x и y) исти узгајивачи наставити да раде, али пошто важи x < y, СПАУЈ ће узети већи проценат новца од тих узгајивача ако изабере y. Самим тим, x није оптимално што је у контрадикцији са нашом претпоставком. Дакле, једине опције за порез су елементи низа P.

Решење кад су елементи низа P цели бројеви:

На основу претходног закључка можемо видети да је потребно проверити само све целобројне проценте, односно да порез буде цео број од 0 до 100. То значи да ћемо највише 101 пут проћи кроз низ, што је свакако довољно брзо. Временска сложеност је O(N).

Решење за N \leq 1000:

Проверимо проласком кроз низ сваки од N елемената низа P. Временска сложеност је O(N^2).

Решење кад су сви елементи низа A једнаки:

За решење овог подзадатка морате питати врачару Миљану.

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

Сортирамо све узгајиваче по вредности низа P опадајуће (дакле, сортирамо низове A и P заједно). Сада за дати елемент низа P можемо у O(1) проверити колико би СПАУЈ зарадио за такав порез користећи префиксну суму над низом A (низ у којем за свако i чувамо суму првих i елемената). Временска сложеност је O(NlogN), због сортирања.

[MladenP]

Слова

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

Решења за мале примере

Ако је дужина стринга 26, потребно је једноставно проверити да је задати стринг заиста сачињен од свих слова ‘A’ до ‘Z’ у растућем поретку. Када је дужина 27, исти услов треба да је испуњен када се избаци једно слово.

Квадратно решење

Проблем можемо посматрати као пребројавање (не нужно узастопних) поднизова задатог натписа који чине растући низ слова од А до Z. Могући приступ јесте посматрати једноставнији потпроблем који се састоји од пребројавања краћих растућих поднизова који се завршавају неким словом. Нека dp_{i, j} представља број растућих поднизова који се завршавају на позицији i и који су дужине j.

Број поднизова који се завршавају на позицији i и имају дужину 1 је 1 ако је слово на тој позицији у натпису A и 0 у супротном. Ако претпоставимо да знамо решење за све позиције пре тренутне, лако можемо израчунати dp вредности за тренутну позицију. Наиме, dp_{i, j} је 0 за свако j сем за редни број слова који је на i-том месту у натпису. За ово j потребно је пребројати све натписе дужине j-1 који се завршавају пре позиције i. Другим речима dp_{i, j} = \sum_{1\le k <i}dp_{k, j-1}. Коначно решење је сума свих секвенци које су дужине 26, односно \sum_{1\le i \le n}dp_{i, 26}.

Решење у линеарном времену

Претходно решење можемо оптимизовати чувањем сумe свих претходних вредности. Вредности у табели биле би одређене на следећи начин.

dp_{i, j} = \begin{cases} dp_{i-1, j} + dp_{i-1, j-1}, & \text{ако је на $i$-тој позицији $j$-то слово алфабета}\\ dp_{i-1, j}, & \text{у супротном само преписујемо претходну вредност} \end{cases}

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

[MladenP]

BUG

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

Први потпроблем

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

Други потпроблем

Чистом симулацијом израчунавања функције f, на начин описан у тексту задатка, можемо у експоненцијалном времену урадити овај потпроблем.

Остали потпроблеми

Можемо лако уочити да ће вредност функције f(A, k) бити једнако изразу \sum_{i=1}^{n} c_i \cdot A_i за неки низ коефицијената c – хајде да видимо колики су ти коефицијенти. Коефицијент уз A_i ће бити једнак броју финалних поднизова у којима се појављује тај елемент.

Скуп свих подниза чији ће се збирови сабирати у фазама када је k = 0 у којима се садржи елемент A_i је у бијекцији са скупом парова низова l и r од k елемената, за које важи 1 \leq l_1 \leq l_2 \leq \dots \leq l_k \leq i \leq r_k \leq r_{k-1} \leq \dots \leq r_1 \leq n. Ово лако можемо проверити тако што посматрамо да је тај подниз у првој фази био подниз низа A[1..n] = A, у другој подниз низа A[l_1 .. r_1], итд. Такође, приметимо да су низови l и r на неки начин независни, број оваквих парова низова (l, r) је једнак производу броја адекватних l и r низова.

Треба да израчунамо колико оваквих поднизова постоји (симетрично рачунамо за l и r низове). Рачунајући за l низове прво, увођењем d_i = l_i - l_{i-1} (уз l_0 = 1), можемо видети да низова l има колико и решења једначине d_1 + d_2 + \cdots + d_k = i - 1 (где d_i \geq 0), чији је број решења {k + i - 1 \choose k}.

Користећи сличну анализу за број низова r, добијамо да је c_i = {k + i - 1 \choose k} \cdot {k + n - i \choose k}. Све што нам остаје је да израчунамо ове биномне коефицијенте.

Подзадаци 3 и 4

Све биномне коефицијенте можемо израчунати користећи Паскалов троугао, и укупна временска сложеност је O(N^2).

Подзадатак 5

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

[MladenP]

01-низ

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

Решење када је C=N

Не исплати се окретати поднизове новчића за цену C јер можемо појединачно да их окренемо за мању или једнаку цену. Решење се своди на најмањи број окретања по једног оновчића тако да се добију све нуле. Нема разлога да икада окренемо новчић на ком је 0, а сваки новчић на ком је 1 окрећемо по једном, односно решење је број јединица у низу. За 2 поена можемо после сваке промене да прођемо кроз низ и пребројимо јединице. Временска сложеност је O(QN). За 4 поена треба да приметимо да се после сваке промене за коју је L_i=R_i мења тачно један новчић у низу па можемо лако да израчунамо за колико се променио број јединица посматрајући само тај новчић. Временска сложеност је O(N+Q). За 16 поена треба да израчунавамо број јединица помоћу сегментног стабла са лењом пропагацијом. Временска сложеност је O(QlogN).

Решење када је C=1

Можемо да окрећемо поднизове за исту цену као и појединачне новчиће, тако да је решење најмањи број окретања поднизова тако да добијемо све нуле. Замислимо да смо на почетак и крај низа додали по један новчић са нулом на видљивој страни. Пребројмо све парове суседних новчића тако да су им различити бројеви на видљивим странама. Ако је овај број 0 у низу су све нуле. Окретање подниза мења стање тачно 2 од поменутих парова и за свака два пара постоји подниз који мења њихова стања. Зато је решење број парова суседних новчића чији су видљиви бројеви различити подељен са 2. Ако се ово пребројавање ради проласком кроз цео низ после сваке промене добија се 4 поена. Временска сложеност је O(QN). Већ знамо да свака промена мења стање тачно два пара па ако то искористимо можемо лако да нађемо за колико се променио број парова које бројимо. Ово решење је временске сложености O(N+Q) и носи 10 поена.

Решење када је Q=1

Овај случај можемо да решимо динамичким програмирањем. Потребна нам је следећа опсервација. У неком од оптималних решења, обрнућемо неке дисјунктне поднизове и затим све јединице појединачно. Нека је dp_i минимална цена за првих i новчића. Последњи новчић може бити обрнут за цену C са неким поднизом или не, па је dp_i = max(dp_{i-1} + S_i, max_{j=1}^i(dp_{j-1} + C + broj\_nula(j,i))). Ово решење је временске сложености O(N^2) и носи 8 поена. За 26 поена потребно је решење у бољој временској сложености. Нека је dp_{i, 0} решење за првих i новчића ако i-ти новчић није био обрнут као члан подниза, а dp_{i, 1} решење ако јесте. Онда је dp_{i, 0}=max(dp_{i-1, 0}, dp_{i-1, 1})+S_i и dp_{i, 1}=max(dp_{i-1, 0}+C, dp_{i-1, 1})+(1-S_i). Ово решење је временске сложености O(N).

Решење када је L_i=R_i

Ако бисмо Q пута искористили решење за Q=1 добили бисмо решење у временској сложености O(NQ) што је превише споро за овај подзадатак. Ипак треба да приметимо да велики део низа остаје исти и да то треба некако да искористимо. Можемо да направимо сегментно стаблно над низом новчића и да у сваком чвору чувамо неке dp вредности. За сваки сегмент чувамо 4 решења dp_{l,r}, где је l=1 ако је први новчић био обрнут као члан подниза и r=1 ако је последњи новчић био обрнут као члан подниза. Са овим информацијама можемо да спојимо dp вредности за два подниза и решење задатка ће бити у корену сегментног стабла. Временска сложеност овог решења је O(QlogN).

Решење за 100 поена

За свих 100 поена потребно је да на сегментном стаблу применомо lazy propagation технику. За сваки чвор чуваћемо dp вредности за сегмент и dp вредности за сегмент ако бисмо обрнули све новчиће на њему. Када треба да обрнемо подниз, заменићемо ове dp вредности за неке сегменте и обрнути њихове lazy тагове. Временска сложеност остаје O(QlogN).

[prvi1]

Koliko poena nosi rešenje N<1000?

[prvi1]

Za uzgajivača jabuka.

[MladenP]

Taj podzadatak je vredeo 20 poena.

[MihajoESTS]

Kada će izaći preliminarni rezultati?