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

Минимални Труд

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

Ако Мика у другом и трећем кругу заједно има барем 256 бодова, односно
B+C \geq 256, сигурно ће се квалификовати, тако да може да освоји 0
бодова у првом кругу.

У супротном, у крајњем збиру ће учествовати први круг и бољи од
преостала два, и минималан број бодова је онај који даје укупно 256.
Дакле, знамо да A + \text{max}(B, C) = 256, односно A = 256 - \text{max}(B, C).

5 Likes

Пријатељи

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

Решење за N, M \leq 10:

За свако познанство помоћу рекурзије или битмаски фиксирамо да ли је пријатељство или непријатељство. Пробамо све могућности за сва познанства и узмемо најбољу комбинацију. Временска сложеност је O(2^M\cdot(N+M))

Решење за A_i = 1:

Пошто су дружељубивости свих људи позитивне, никада нам се неће исплатити да имамо непријатељства, тј. сва познанства ће бити пријатељства. Дакле, ако са P_i означимо број познаника (односно и пријатеља) особе i, наше решење ће бити \sum^{N}_{1} A_i\cdot P_i. Пошто важи A_i = 1 за свако i, та сума је еквивалентна \sum^{N}_{1} P_i. Детаљнијом анализом ове суме можемо закључити да она износи 2\cdot M, јер свако познанство повећава нашу суму за 2. Временска сложеност је O(N+M) или O(1) у зависности од имплементације.

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

Означимо поново број пријатеља особе i са P_i, а број непријатеља са Q_i. Онда је наш крајњи резултат \sum^{N}_{1} A_i \cdot (P_i - Q_i), по тексту задатка. Можемо уочити да је ово еквивалентно томе да за свако пријатељство између особа x и y доприноси резултату A_x + A_y, док свако непријатељство доприноси резултату -(A_x + A_y). Пошто желимо да максимизирамо наш резултат, свако познанство за које важи A_x + A_y \geq 0 ћемо поставити као пријатељство, а свако познанство за које важи A_x + A_y < 0 ћемо поставити као непријатељство. Може се приметити да је у том случају наше решење \sum^{M}_{1} |A_{X_i} + A_{Y_i}|. Временска сложеност је O(N+M).

4 Likes

Жалбе

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

Прво сортирамо низ A растуће. Од сада са A_i означавамо i-ти најмањи елемент низа A.

Решење за A_i, B_i, N, M \leq 3000:

Довољно нам је да проверимо свако могуће X (све бројеве од 1 до 3000). Неко X је могуће само ако дели A_{i+1}-A_i за свако 1 \leq i \leq N-1, а не дели |B_i-A_1| ни за једно 1 \leq i \leq M. Временска сложеност је O(T \cdot maxA \cdot (N+M)).

Решење за N = 2:

Знамо да X, ако постоји, мора да дели A_2 - A_1, али пошто та разлика може да буде велика, не можемо да проверимо све делиоце. Можемо да приметимо да ако број p дели број q, сваки делилац од p такође дели q. То нам говори да нам је довољно проверити да ли је A_2 - A_1 добар кандидат за X, јер ако не дели ниједно од |B_i-A_1| онда је у реду, у супротном и сви његови делиоци деле неки од |B_i-A_1|, па решење не постоји. Временска сложеност је O(T \cdot (N+M)).

Решење за A_i \leq 10^6:

Пошто X мора да дели све разлике A_{i+1}-A_i, једини кандидати су делиоци најмањег заједничког делиоца тих разлика, односно, ако X постоји, важи X \mid НЗД(A_2-A_1, A_3-A_2, ..., A_N-A_{N-1}). НЗД можемо нађи Еуклидовим алгоритмом, а пошто делиоца има O(\sqrt{maxA}), укупна временска сложеност је O(T \cdot (NlogN + M\sqrt{maxA})).

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

Ако спојимо решења за претходна два подзадатка можемо видети да је довољно проверити да ли X може бити НЗД(A_2-A_1, A_3-A_2, ..., A_N-A_{N-1}). Уколико не, не може ниједан његов делилац. Временска сложеност је O(T \cdot (NlogN + M)).

4 Likes

Чврсти бројеви

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

У овом задатку је потребно наћи чврст број који се на најмање места разликује од задатог броја. Број је чврст ако су сва појављивања неке цифре узастопна.

Нека је у свим подзадацима M број цифара броја N, а d број различитих цифара.

Подзадатак 1: N\le10^6

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

Подзадатак 2: Све цифре су 0 или 1

За сваки префикс и суфикс је могуће једним проласком кроз низ да одредимо број потеза да би све цифре постале 0 или 1, па онда за сваку позицију преламања можемо да видимо колико нам треба потеза (постоји само 2M чврстих бројева са само јединицима и нулама, проверимо који од њих је оптималан).

Подзадатак 3: N\le 10^{100}

Овај подзатак служи да се на њему освоје поени које користе идеје у наредна два, али нису довољно брза за већа ограниченја (нпр. O(M^2\cdot d\cdot2^d) или O(M\cdot d^2\cdot2^d))

Подзадатак 4: N\le10^{10.000}

Овај задатак ћемо урадити путем динамичким програмирањем по битмаскама. Нека је dp[i][c][mask] најбоље решење за првих i цифара, тако да је последња цифра c и у mask су на 1 постављене цифре које одговарају цифрама које смо већ искористили (укључујући c). Имаћемо и помоћни низ aux[i][mask] који нам каже највећу вредност dp[i][c][mask] за неко 0\le c\le 9. Сада лако можемо рачунати вредност dp[i][c][mask] као максимум од dp[i-1][c][mask] и aux[i-1][mask \text{ xor } 2^c] и на то додамо 1 ако тренутна цифра није c. Тако свако стање dp[i][c][mask] рачунамо у O(1) и сваку од вредности aux[i][mask] у O(d), што нам даје решење у O(M\cdot d\cdot 2^d).

Подзадатак 5: 100 поена

У овом подзадатку за све поене ћемо променити перспективу. Уместо што тражимо најмањи број промена, тражићемо највећи број цифара да не мењамо. Да бисмо то постигли, чуваћемо два низа a[c][mask], који је пандан низу dp из претходног решења (кад обрадимо i-ту цифру ту ће се налазити најбоље решење за првих i цифара) и низ max[mask] који је пандан претходном низу aux. Главна разлика је што се већина ових низова сада неће мењати и онда можемо само да их пустимо да наследе вредности из претходне итерације. На пример: a[c][mask] има смисла поново рачунати за тренутну цифру (a[c][mask] постане максимум од a[c][mask]+1 и max[mask\text{ xor } 2^c]+1), и при томе променити max[mask]. Ово нам доста смањи број операција, тако да нам је сложеност сада O(M\cdot2^d) што лако пролази за 100 поена.

4 Likes

СИО стабло

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

Решење када је n \leq 1000

Временска сложеност: O(N^2)

Покренимо алгоритам претраге у дубину (DFS) од сваког чвора. Чувајмо колико се пута које слово појављује на тренутном путу и са тим информацијама лако можемо да повећамо решење за сваки СИО пар.

Решење када је слово \text{"S"} урезано на тачно једној грани

Временска сложеност: O(N)

Решење је број путева дужине 3 на којима се свако од три слова појављује по једном. Пронађимо грану на којој је урезано слово \text{"S"} и запамтимо њене крајеве. Нека су то чворови U и V. Пребројимо колико има путева дужине 2, чији је јадан крај неки од чворова U и V, такве да је на њима урезано по једно слово \text{"I"} и \text{"O"}. На решење још додајмо број парова грана тако да једна креће из U, а друга из V и на једној је урезано слово \text{"I"}, а на другој слово \text{"O"}.

Решење када је СИО стабло ланац

Временска сложеност: O(N log N)

Направимо стринг од свих слова која се појављују на гранама од једног до другог краја ланца, у том поретку. Решење се своди на број подстрингова у којима се свако од 3 слова појављује једнак број пута. Нека је \text{X(i)} број појављивања слова X у првих i слова. За сваки префикс од дужине 0 до N-1 (имамо N-1 грана па самим тим исто толико слова), запамтимо пар P(i) = (\text{S(i)}-\text{I(i)}, \text{S(i)}-\text{O(i)}). Посматрајмо подстринг од L-тог до R-тог слова. Ако се слова \text{S} и \text{I} појављују исти број пута онда мора да важи (\text{S(R)}-\text{S(L-1)}) - (\text{I(R)}-\text{I(L-1)}) = (\text{S(R)}-\text{I(R)}) - (\text{S(L-1)}-\text{I(L-1)}) = 0 односно прве вредности из парова P(R) и P(L-1) морају бити једнаке. Слично се добија и да друге вредности из ових парова морају бити једнаке, односно парови P(R) и P(L-1) морају бити једнаки. Сада остаје још да пребројимо колико имамо парова префикса са једнаким P. Ово можемо урадити сортирањем низа парова или помоћу \text{std::map}.

Решење када је СИО стабло комплетно бинарно стабло

Временска сложеност: O(N log^2 N)

Нађимо прво за колико СИО парова се корен стабла налази на путу између њих. То морају бити чворови из различитих подстабала. Слично као у решењу за ланац нађимо вредности X(i) колико се пута појављује слово X на путу од корена до чвора i. Такође за сваки чвор запамтимо пар P(i) = (\text{S(i)}-\text{I(i)}, \text{S(i)}-\text{O(i)}). У \text{std::map} запамтимо колико се пута који пар појављује у левом подстаблу. За чвор i у десном подстаблу ако га упаримо са чвором j у левом подстаблу тако да важи P(j) = (\text{I(i)}-\text{S(i)}, \text{O(i)}-\text{S(i)}), свако од три слова ће се појављивати исти број пута на путу између i и j. За сваки чвор i у десном подстаблу помоћу \text{std::map} нађимо колико има таквих чворова j у левом подстаблу и то додајмо на решење. Сада када смо у обзир узели све путеве који прелазе преко корена стабла, знамо да су сви остали путеви између чворова из истог подстабла па можемо рекурзивно да решимо проблем за лево и десно подстабло. Подстабло величине M решавамо у временској сложености O(M log M). Како је висина стабла O(log N) збир величина подстабала је O(N log N) па је временска сложеност целог алгоритма O(N log^2 N).

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

Временска сложеност: O(N log^2 N)

Решење је слично као за комплетно бинарно стабло. У сваком стаблу постоји чвор такав да када избришемо њега и све његове гране, свака повезана компонента која остане мора имати барем два пута мањи број чворова него стабло пре брисања. Овај чвор се назива центроид и могуће га је наћи помоћу алгоритма претраге у дубину (DFS). Нађимо за колико СИО парова се центроид налази на путу између њих, на сличан начин као у претходном решењу, затим обришимо центроид и све његове гране. Рекурзивно решимо проблем за повезане компоненте које су нам остале. Због особина центроида дубина ове рекурзије је O(log N) па је временска сложеност целог алгоритма O(N log^2 N).

Алтернативно решење за 100 поена

Временска сложеност: O(N log^2 N)

Као у решењу за комплетно бинарно стабло, нађимо вредности P(i) за сваки чвор. Овај пут прво рекурзивно решавамо подстабла, а затим тражимо број СИО парова тако да се корен налази на путу између њих. Сваки рекурзивни позив ће направити \text{std::map}-у у којој су пребројане вредности P(i) за све чворове i у тренутном подстаблу. Како бисмо направили \text{std::map} за тренутно подстабло потребно је да спојимо \text{std::map}-е за подстабла која остану када се избаци корен овог подстабла, а затим да убацимо P(koren). Како бисмо добили добру временску сложеност, када спајамо \text{std::map}-е увек пролазимо кроз мању и пребацујемо све из ње у већу. Приликом спајања пребројавамо СИО парове. Посматрајмо пут од чвора U до V. Нека је W чвор на најмањем растојању од корена који се налази на путу између U и V. Пар (U, V) је СИО пар ако и само ако важи P(U) + P(V) - 2 P(W) = (0, 0). Ако се U налази у мањој \text{std::map}-и, на решење додајемо број чворова у већој, таквих да је P(V) = 2 P(W) - P(U). Остаје још да анализирамо временску сложеност овог алгоритма. Посматрајмо за неки чвор колико пута је био пребачен из једне у другу \text{std::map}-у. Сваки пут када је пребачен, величина \text{std::map}-е у којој је повећала се бар два пута јер је величина нове \text{std::map}-е збир величина \text{std::map}-е у којој је био и веће \text{std::map}-е. Због тога један чвор није могао бити пребачен више од log N пута. Следи да је укупан број пребацивања O(N log N), па како је за сваку операцију над \text{std::map}-ом потребно O(log N) времена, укупна временска сложеност овог алгоритма је O(N log^2 N).

4 Likes

Umesto parova P(i) može da se čuva samo R_{i}=a*S+b*I+c*O, gde su S, I i O brojevi pojavljivanja odgovarajućih slova od korena stabla (centroida) do i, a a,b i c celi brojevi tako da za N \leq 3 \times 10^{5} važi R_{i}=0 \iff S=I=O. Radi malo brže u svakom primeru. Super je zadatak. :slightly_smiling_face:

1 Like