[Rešenja zadataka] 2020/2021 Okružno

Algoritam
1

Такмичар

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

Анализа

Да би збир одговора на упите био што већи, потребно је да сума елемената низа буде што већа. Сума елемената је највећа онда када елементи низа имају највећу могућу вредност. Највећа могућа вредност се добија након што се примене сви упити типа 1 у којима се елементи низа увећавају за неку позитивну вредност.
Због тога је потребни прво извршити упите типа 1 код којих се вредност елемената увећавају за позитиввну вредност, а затим све упите типа 2 и на крају упите типа 1 код којих се вредности елемената увећавају за негативну вредност.

Ако је сума елемената низа износила S, онда након примене упита 1\ l\ r\ x сума елемената низа износи

S_n = S + (r - l + 1) \cdot x.

Према томе, потребно је одредити суму свих елемената након примене свих упита типа 1 код којих се неки елементи увећавају за неку позитивну вредност (нека та сума износи S_m) и број упита типа 2 (нека је то n_2).
Тада ће сума одговора на упите изноосити

n_2 \cdot S_m.

Лако се показује да је сложеност алгоритма \Theta(n+m), где је n број елемената у низу, m укупан број упита.

2 Likes
2

Лепа Матрица

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

Анализа

Врсте са редним бројевима i и i+1 ћемо назвати суседним врстама. Осим тога ћемо и врсте са редним бројевима N и 1 (претпоставимо да су врсте нумерисане бројевима од 1 до N) сматрати суседним. Слично ћемо колоне са редним бројевима j и j+1 сматрати суседним колонама, а исто тако колоне са редним бројевима M и 1 ћемо сматрати суседним. Такође ћемо рећи да су елементи А[i][j] A[i+1][j] одговарајући елементи у суседним врстама. Слично ћемо елементе А[i][j] A[i][j+1] сматрати одговарајућим елементима у суседним колонама.

Под овим претпоставкама, лепота матрице се може одредити тако што се од збирова апсолутних вредности разлика одговарајућих елмената у сусеним врстама и одговарајућих елемената у суседним колонама одузму апсолутне разлике одговарајућих елемената у последњој и првој врсти и апсолутне разлике одговарајућих елемената у последњој и првој колони. Када се матрица ротира за j колона улево, онда колоне j и j+1 постају последња и прва колона (изузетно, ако се ротира за нула колона, онда су колоне 1 и M, прва и последња колона). Слично, када се матрица ротира за i врста на горе, врсте i и i+1 постају последња и прва врста (изузетно, ако се ротира за нула врста, онда су врсте 1 и N, прва и последња врста).

Нека је S сума свих апсолутних разлика одговарајућих елемената у суседним врстама и свих апсолуних разлика одговарајућих елемената у суседним колонама. Означимо са SR[i] суму апсолутних разлика одговарајућих елемената у врстама i и i+1, а са SC[j] суму апсолутних разлика одговарајућих елемената у колонама j и j+1.

Тада се лепота матрице која се добија након ротације за j колона улево и ротације ѕа i врста на горе добија тако што се од S одузме SR[i] и SC[j]. Лепота матрице је највећа ако се одузимају суме апсолутних разлика одговарајућих елемената суседних врста и суседних колона за које су те суме најмање. Због тога је потребно одредити индексе i и j, ѕа које су SR[i] и SC[j] најмањи и те две суме одузети од S.

Лако се утврђује да је сложеност описаног алгоритма N\cdot M.

1 Like
3

Златници 2: Електрични Бугалу

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

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

Имамо само један златник који је у сваком сценарију потребно довести на одговарајућу позицију. Да бисмо са позиције a_1 дошли до позиције x потребно је |a_1 - x| потеза. Временска сложеност је O(N+Q).

Решење за N, Q \leq 1000 и a_i, x \leq 10^5:

Пошто није дозвољено да се два златника налазе на истој позицији, такође није могуће да се два златника мимоиђу. Самим тим, златник са позиције a_1 ће завршити на позицији x, златник са позиције a_2 на x+1, …, златник са позиције a_N на x+N-1. Пошто ће у сваком тренутку постојати златник који може да се приближи својој крајњој позицији, решење је |a_1-x|+|a_2-x-1|+...+|a_N-x-N+1|, односно \sum_{i=0}^{N-1} |a_{i+1}-x-i|. Пошто су N и Q мали, можемо ручно израчунати ову суму за сваки сценарио. Временска сложеност је O(N\cdot Q).

Решење за a_i = p + i\cdot d:

Приметимо да важи |a_{i+1}-i-x| = x-(a_{i+1}-i) ако a_{i+1}-i\leq x, а |a_{i+1}-i-x| = a_{i+1}-i-x у супротном. Пошто је низ a_i растући, за првих неколико (потенцијално нула) жетона важиће први случај, док
ће за остале важити други случај. Означимо са k индекс последњег жетона за који важи a_{i+1}-i\leq x (ако не постоји такав жетон онда k = 0, иначе k = i+1). Приметимо да онда важи \sum_{i=0}^{N-1} |a_{i+1}-x-i| = \sum_{i=0}^{k-1} (x-(a_{i+1}-i)) + \sum_{i=k}^{N-1} ((a_{i+1}-i)-x). Односно решење је k\cdot x - \sum_{i=0}^{k-1} (a_{i+1}-i) + \sum_{i=k}^{N-1} (a_{i+1}-i) - (N-k)\cdot x. Када знамо k, суме из формуле можемо наћи префиксним сумама. Све ово у ствари значи да ћемо неколико првих новчића померати удесно, док ћемо остале померати улево.

Остало нам је само да нађемо k. Aкo a_i = p + i\cdot d, можемо узети p = a_1 и d = a_2-a_1 (ако N \geq 2). Тражимо највеће k = i+1 тако да важи a_{i+1}-i\leq x, тј. p + (i+1)\cdot d - i \leq x. Важи i+1 \leq \frac{x+i-p}{d}. Самим тим важи k = \lfloor\frac{x+i-p}{d}\rfloor, где је \lfloor x \rfloor цео део од x. Временска сложеност је O(N+Q).

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

Једина разлика овог решења и решења за претходну групу тест примера је налажење k. За 100 поена потребно је да користимо бинарну претрагу над низом a_{i+1}-i (тражимо прво i за које је то веће од x). Временска сложеност је O(N+QlogN).

1 Like
4

Стандардан Задатак

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

Претпоставимо да ће нам на крају сви елементи низа бити једнаки неком броју x, који већ постоји у овом низу. Оно што треба да урадимо је да претворимо све бројеве који нису испрва једнаки x у x-еве.

Нека имамо l бројева строго мањих од x у почетном низу, и r бројева који су строго већи. Уколико су оба броја већа од 0, можемо извршити операцију која ће умањити бројеве l и r за један, тако што ћемо урадити операцију на једном броју мањем од x, једном једнаком и једном већем од њега. Ово можемо понављати док год су и l и r позитивни, дакле \min(l, r) пута. Када један од њих постане једнак нули, без умањења општости, нека је то r – можемо искористити још l операција у којима стављамо два броја x и један мањи број, док год сви бројеви не буду једнаки броју x.

Број операција којима смо смањили збир l + r за 2 је \min(l, r), свим осталим операцијама смо смањивали збир за 1, па је укупан број операција l + r - \min(l, r) = max(l, r).

Дакле, приметимо да нам је решење задатка једнако \min_{i = 1}^{n} \max(l(a_i), r(a_i), где функције l(\cdot) и r(\cdot) враћају број мањих, односно већих бројева од a_i у почетном низу а LIM је максимални број који се може појавити у низу.

Подзадатак 1

У овом подзадатку, након сортирања низа тривијално имамо вредности функција l(\cdot) и r(\cdot) за све вредности. Сложеност: \mathcal{O}(N\log N).

Подзадатак 2

У овом подзадатку, имамо само две могуће вредности за наш x. Сложеност: \mathcal{O}(N).

Подзадатак 3

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

Цело решење

Можемо итерирати по вредностима од најмање до највеће, памтећи колико мањих бројева смо прошли до сад. Знајући колико има мањих и колико бројева једнаких тренутном броју, можемо израчунати и колико има већих и самим тим добити решење у линеарној сложености. Сложеност: \mathcal{O}(N) или \mathcal{O}(N\log N), зависно од имплементације.

5

Велика Трка

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

N,Q\leq 1000

У овом подзадатку можемо лако симулирати сваки део трке, ако део трке креће у (x,y) и иде преко стуба (x',y'), онда се завршава у тачки (2x'-x,2y'-y) , и нађемо где се завршава у сложености O(NQ).

Сви стубови су на истом месту

Оно што треба приметити у овом подзадатку да ће после свака два дела трке да се тркачи врате на стартну позицију, па је једино заправо битна парност броја r-l, и у зависности од њега можемо да одредимо да ли се трка завршава тамо где и почиње или централно симетрично томе у односу на стубове.

Све y координате су 0

Решавамо случај на бројевној правој. Ако је почетак трке на позицији x_0, а стубови на x_1,x_2\cdots,x_n. Онда је крај првог дела трке на 2x_1-x_0, другог дела трке на 2x_2-(2x_1-x_0)=2x_2-2x_1+x_0, \cdots, n-тог дела трке на 2x_n-2x_{n-1}+2x_{n-2}-\cdots+2\cdot(-1)^{n-1}x_{1}+(-1)^{n}x_0. Ово значи да ако памтимо парцијалне суме облика x_1-x_2+x_3-x_4+\cdots, одузимањем две парцијалне суме и обраћањем пажње на парност можемо да нађемо коначну позицију трке у сложености O(N+Q)

Комплетно решење

У овом случају је довољно приметити да можемо раздвојити проблем ко координатама и обе координате независно решимо као у претходном подзадатку у сложености O(N+Q).

2 Likes
6

Алтруизам

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

Анализа

Означимо са S_i(n) збир i-тих степена цифара броја n (нпр. S_3(2021)=2^3+0^3+2^3+1^3=17). Потребно је пронаћи природан број n из сегмента [x,y] за који важи

n = a_1 \cdot S_1(n)+a_2\cdot S_2(n) + \ldots + a_k \cdot S_k(n)

Најједноставније решење је проверити претходну једнакост за сваки број из [x,y]; директна имплементација ради у сложености O(|y-x|\cdot k) и решава подзадатак 1.

Мало боље решење (које води коначном решењу) је записати претходну једначину на другачији начин. За сваку цифру i, 1 \leq i \leq 9 уведимо ознаку c_i = a_1 \cdot i^1 + a_2\cdot i^2 + \ldots + a_k \cdot i^k. Такође, означимо број појављивања цифре i (1\leq i \leq 9) у броју n са x_i(n). Није тешко уочити да је полазна једначина еквивалентна са

n = c_1 \cdot x_1(n) + c_2 \cdot x_2(n) + \ldots + c_9 \cdot x_9(n)

За конкретан број n претходну једначину можемо проверити у O(\log n) (број цифара броја n) па долазимо до решења сложености O(|y-x|\log y) које је довољно за подзадатак 2.

У подзадатку 3 је k \leq 2; како је n \leq 10^{18}, важи S_1(n) \leq 9\cdot 18 = 162 и S_2(n)\leq 9^2 \cdot 18 = 1458 па можемо испробати свих 162 \cdot 1458 могућности за ове вредности и проверити да ли добијени број n задовољава једначину.

Приметимо да ако n садржи бар једну цифру вредности c, тада важи n \geq c^1+c^2+\ldots +c^k. Сада, из n \leq 10^{18}, добијамо да ако n садржи бар једну цифру већу од 1 мора важити да је k \leq 58. Како у подзадатку 4 важи k = 2021, следи да су у овом подзадатку једини кандидати за решење бројеви који се састоје од нула и јединица. Сада на основу друге једначине имамо n = c_1 \cdot x_1(n) па једноставно испробамо свих 18 могућих вредности за x_1(n) (или, мало компликованије, генеришемо свих 2^{18} - 1 таквих бројева и проверимо их).

Кључно запажање, које директно следи из једначине са c_i-овима, је да бројеви са истим бројем појављивања сваке не-нула цифре дају исту вредност са десне стране једначине (нпр. 35502, 2355, 5532, 20305050...) па проверу не морамо вршити по свим бројевима из [x,y] већ по броју појављивања цифара. Довољно је испробати све 9-орке (x_1, x_2, ..., x_n) ненегативних целих бројева за које је 1 \leq x_1 + x_2 + \ldots +x_9 \leq 18 (број цифара је између 1 и 18), израчунати десну страну једначине и проверити да ли је добијени број n из [x,y] и да ли се у њему свака цифра i јавља тачно x_i пута.

За генерисање оваквих 9-орки користимо backtracking технику. Један од начина је заправо генерисати бројеве са нерастућим низом цифара: са F(a,b) oзначимо позив рекурзивне функције у коме треба фиксирати a-ту цифру при чему је претходна цифра b; рекурзивни позиви су F(a+1, b) (a-та цифра је b, уз повећање x_b) и F(a, b-1) (a-та цифра је мања од b) . Број поменутих деветорки се може одредити покретањем овог алгоритма или користећи мало комбинаторике; тај број је \binom{27}{9}-1=4686825 тј. довољно је мали да овај алгоритам решава цео задатак у задатом временском ограничењу.