[Rešenja zadataka] 2021/2022 Državno

[MladenP]

Једначине

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

Решење подзадатка 1

Приметимо да је у овом случају једина могућа вредност за n број

n = A\cdot S(n) + B = 0 \cdot S(n) + B = B.

Због тога је довољно само проверити да ли је број n=B између X и Y и ако јесте исписати тај број, у супротном исписати вредност -1. Сложеност овог решења је O(1).

Решење подзадатка 2

Како је n\leq Y \leq 10^6, довољно је за свако n из интервала [X,Y] одредити збир цифара (узастопним дељењем тог броја са 10 и сабирањем остатака), а након тога проверити да ли задовољава једначину . Наравно, након проналаска прве такве вредности за број n исписује се та вредност и прекида извршавање програма. Ако ниједан број из интервала [X,Y] не задовољава једначину, исписује се вредност -1. Сложеност овог решења је O(Y\log Y).

Решење подзадатака 3 и 4

Приметимо да ако је 1\leq X \leq n \leq Y \leq 10^{18}, онда је 1 \leq S(n) \leq 18 \cdot 9 = 162. Самим тим je скуп могућих вредност за израз A\cdot S(n) +B заправо скуп

U = \{A\cdot T + B|T = 1, 2, \dots, 162\}

и то је скуп могућих вредности за број n.

Према томе, довољно је за елементе n\in U, проверити да ли задовољавају једначину

S(n) = S(A\cdot T + B) = T

и ако неки од њих задовољава исписати његову вредност, у супротном исписати број -1. Број елемената скупа U је O(\log Y), а провера да ли неки елемент n скупа U задовољава горњу једнакост има сложеност O(\log n)=O(\log Y), па је сложеност целог алгоритма O(\log^2 Y).

При решавању подзадатка 4 треба водити рачуна да при рачунању вредности A\cdot T + B може доћи до прекорачења.

[MladenP]

Турнир

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

Решење првог подзадатка

Уколико се игра састоји од само једне рунде, то значи да свих својих K жетона користимо у тој рунди. Укупан број поена који можемо да остваримо једнак је броју осталих играча који имају мање од K жетона. Ово решење ради у временској сложености O(M).

Решење другог подзадатка

Довољно је испробати све могуће начине да се K представи као збир N ненегативних целих сабирака, генерисане бектрекингом, и да се за сваку од тих подела одреди број поена који можемо да остваримо. Број начина да се K разбије на N сабирака једнак је N+K-1 \choose N-1, а одређивање броја поена за дату поделу се ради у сложености O(MN). Бектрекинг решење не мора да буде посебно ефикасно да би се у овом подзадатку добили сви поени.

Решење трећег подзадатка

За M=1 постоји само један играч против ког играмо, те је питање како распоредити жетоне да остваримо највећи број победа у рундама. Уколико је у i-тој рунди овај играч поставио a_{i,1} жетона, онда победу у овој рунди остварујемо постављањем a_{i,1}+1 жетона. За остваривање победе у највећем броју рунди, довољно је победити у оним рундама у којима је наш противник ставио најмање жетона. Ово води ка једноставном грамзивом алгоритму: најпре се сортирају рунде по броју жетона саиграча (у растућем поретку), након чега се “буџет” од K жетона троши редом у овим рундама све док нам не остане ниједан жетон. Временска сложеност овог решења је O(N \log N).

Решење четвртог подзадатка

Овај подзадатак се решава применом динамичког програмирања. Дефинишимо тродимензиони низ S_{n,k}, уз 0 \leq n \leq N, 0 \leq k \leq K:

• S_{n,k}: највећи број поена који се може остварити уколико је искоришћено k жетона у првих n рунди

Тривијално познате вредности у овом низу су:

• S_{0,k}=0 за свако k

Нека је [B] индикатор неког логичког израза: 1 уколико B важи и 0 уколико не важи. У случајевима n>0 користимо рекурентну везу:

• S_{n,k} = \max_{1 \leq z \leq k} (S_{n-1,k-z} + \sum_{j=1}^{m} [a_{n,j} < z]) (*)

Ова рекурентна веза може да се објасни на следећи начин: најбољи начин да се k жетона распореди у n рунди може да се одреди уколико се размотре сви могући бројеви жетона z у n-тој рунди, одреди колико играча има мање од z жетона у n-тој рунди и тако одреди број поена, на то дода оптимална расподела k-z жетона у претходним рундама, и одреди најбоље такво z. Тада је коначан одговор на питање из задатка вредност S_{N,K}, која може да се одреди у временској сложености O(NMK^2).

Решење петог подзадатка

Решење које доноси све поене је оптимизација решења четвртог подзадатка.

Приметимо да су једини значајни бројеви жетона у n-тој рунди 0, a_{n,1}+1, a_{n,2}+1, \ldots, a_{n,M}+1, односно бројеви жетона при којима се остварују различити бројеви поена. У оквиру једне рунде је небитно који играч је ставио колико жетона, битни су само бројеви. Стога не губимо никакве информације сортирањем бројева жетона различитих играча у оквиру једне рунде.

Приметимо и да је S_{n,k} за фиксирано k растуће у n, односно S_{n,k} \leq S_{n',k} за n < n’.

Уз ова два корака, приметимо да није неопходно испитати све могуће z у формули (*). Самим тим рачунање S_{n,k}, које се у претходном подзадатку радило у временској сложености O(MK), може да се уради у O(M). Укупна временска сложеност је O(NMK).

За оне који желе да знају више: овај задатак је инспирисан игром Blotto.

[MladenP]

Бурад

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

Решење када l_i = r_i

Пошто ће киша сваког дана падати над тачно једним буретом, можемо свако буре гледати засебно. Избројаћемо колико литара је прогнозирано да упадне у i-то буре, назовимо тај број cnt_i. Уколико cnt_i > a_i, значи да долази до преливања и морамо прекрити буриће cnt_i - a_i дана. Урадимо то за свако i и сумирајмо како бисмо добили крајње решење. Временска сложеност је O(N+M), а меморијска O(N).

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

Једина места на којима може доћи до преливања јесу бурад са капацитетом 0, а пошто су сви интервали дисјунктни, то значи да је укупна дужина свих интервала до N, па је довољно ефикасно да за сваки дан прођемо кроз све буриће у које би упала киша и проверимо да ли неки од њих има капацитет 0. Временска сложеност О(N+M), а меморијска O(N).

Решење када a_i \in \{0, 10^9\}

Једина места на којима може доћи до преливања јесу бурад са капацитетом 0, у које не сме упасти ни литар кише. Зато, Марко мора прекрити све буриће на дане када би у макар једно буре капацитета 0 упала киша, што је еквивалентно са провером да ли у интервалу низу постоји 0. Ово можемо проверити нпр. бинарном претрагом над индексима где се појављује 0 или префиксним сумама којим бројимо нуле на префиксу. Временска сложеност O(N+M) или O(N+MlogN), а меморијска O(N).

Решење када N, M \leq 2000

Прво је потребно да одредимо колико литара кише је прогнозирано за свако буре. То можемо једноставно урадити тако што за сваки дан пролазимо кроз све буриће и увећамо број литара за један. Назовимо тај број литара за i-то буре cnt_i. Сада је потребно да посматрамо искључиво буриће за које важи cnt_i > a_i, односно оне који би се прелили када ништа не бисмо учинили.

Сада, идемо слева надесно и сваки пут када наиђемо на такво буре, знамо да морамо да покријемо буриће на макар cnt_i - a_i нових дана. Чувајмо у неком низу све дане за које нисмо одредили да ли ћемо прекрити буриће тај дан (зваћемо их необрисани интервали). Кад год морамо да обришемо нови интервал, обрисаћемо онај интервал који садржи i, а просеже се што је могуће даље у десно. Ово је оптимално, јер су тако највеће шансе да ћемо тим брисањем смањити cnt_j других критичних бурића. Када одаберемо такав интервал, бришемо га из низа, и смањујемо одговарајуће елементе cnt низа. Настављамо десно док не обрадимо цео низ.

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

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

Идеја иза овог решења иста је као за претходно, само је потребно да све урадимо ефикасније. Први део, проналажење низа cnt_i, урадићемо конструкцијом новог низа, b. На почетку, он ће бити испуњен нулама. За сваки дан i, ми ћемо повећати b_{l_i} за један, а смањити b_{r_i+1} исто за један. Низ cnt добијамо као низ префиксних сума над низом b.

Други део ћемо радити слично као у претходном решењу, само што ћемо уместо низа необрисаних интервала, чуваћемо скуп (std::multiset), сортиран по десном крају интервала. Чуваћемо само оне интервале који садрже тренутни елемент, дакле додаћемо интервал j тек кад важи l_j = i, а избацити тек кад је обрисан или када r_j = i. Сваки пут када треба да обришемо интервал, обрисаћемо највећи у скупу. Слично се може урадити и са приоритетним редом (std::priority_queue), са мало додатне анализе.

Временска сложеност је O(N+MlogN), а меморијска O(N+M).

[MladenP]

Концерт

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

Како није дозвољено понављање поља на путу, у сваком реду се иде само у једном смеру (улево или удесно) или директно на горе. Промена стрктуре реда гурањем не утиче на даљи део пута јер није дозвољено враћање уназад.

У Подзадатку 1 је довољно користити класично динамичко програмирање за рачунање броја одговарајућих путева у O(nm) или применити мало комбинаторике: за сваки од n редова можемо на m начина изабрати поље у које долазимо из претходног реда (за последњи ред, то је поље из кога почињемо) а након тога је пут јединствено одређен. Дакле, одговор је m^n mod (10^9 + 7). За Подзадатак 2 је довољно испробати све могуће путеве, наједноставније користећи рекурзију/бектрек у сложености O(m\cdot m^n).

Задатак је најприродније решавати динамичким програмирањем. Дефинишимо d[i][j] = број (валидних) путева који се завршавају у пољу (i,j) дате матрице a при чему је последњи потез “нагоре”. Коначно решење је \sum_{1 \leq j \leq m, \ a[1][j]=0} d[1][j] а почетне вредности су d[n][j] = a[n][j] за j=1,2,\ldots,m. Рекурентна веза је дата са d[i][j] =\sum_x d[i+1][x], где се сумирање врши по свим индексима x таквих да је (гурањем) у (i+1)-ом реду могуће доћи од позиције x (која треба бити празно поље) до позиције j (која не мора нужно бити празно поље). Најједноставнији начин је испитати сваку позицију x из (i+1)-ог реда; ако је x_L позиција (k+1)-ве особе лево у односу на позицију x а x_R позиција (k+1)-ве особе десно у односу на позицију x, тада, са позиције x можемо гурањем доћи до било које које (и само те) позиције из сегмента [x_L+(k+1), x_R-k]. Вредности x_L и x_R за свако x можемо одредити у свега два пролаза кроз (i+1)-ви ред (слева удесно и сдесна улево) нпр. убацивајући позиције јединица на које наиђемо у неки помоћни вектор. Ово даје решење сложености O(nm^2) што је довољно за Подзадатак 4.

У Подзадатку 3 нема гурања па се рекурентна веза може упростити увођењем помоћних матрица, нпр. L[i][j]= број путева који се завршавају у пољу (i,j) при чему је последњи потез “улево” и аналогно за R[i][j] и “удесно”. Сада се све ове матрице могу паралено израчунати, d[i][j] = d[i+1][j]+L[i+1][j]+R[i+1][j], L[i][j] = L[i][j+1]+d[i][j+1], R[i][j] = R[i][j-1]+d[i][j-1] (у одговарајућем редоследу i проверу заузетости поља). То је O(1) по пољу тј. O(nm) укупно.

За коначно решење, треба убрзати O(nm^2) алгоритам. Из тог решења, знамо да ће за свако поље (i+1,x), вредност d[i+1][x] учествовати у формули за рачунање вредности d[i][j] за свако j\in[x_L+(k+1),x_R-k] (уз проверу d[i][j]=0 и границе за сегмент). Зато можемо, након обраде (i+1)-ог реда, за свако x повећати све d[i][j] из реда изнад који су у одговарајућем сегменту за d[i+1][x]. Наравно, директна имплементација овога не би смањила сложеност али можемо користити познати трик; довољно је додати елементу на почетку сегмента +d[i+1][x] и додати елементу након краја сегмента -d[i+1][x] (за свако x) и на крају ће тражене вредности у новом реду бити префиксне суме тренутних вредности. Ово даје алгоритам сложености O(nm).

Алтернативно (и нешто једноставније решење) је дефинисати d[i][j]= број путева који почињу из поља (i,j). Тада вредности можемо рачунати одозго надоле и, на основу претходне дискусије, важи d[i][j] = \sum_{j_L + k + 1 \leq x \leq j_R - k} d[i-1][x], где се вредности j_L и j_R односе на тренутни, i-ти ред. Користећи префиксне суме, претходну суму можемо израчунати у O(1) (прецизније, један ред матрице d рачунамо у O(m)) па добијамо алгоритам сложености O(nm).

[MladenP]

Шмекер

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

Решење када N, M \leq 500

У овом случају, као решење можемо да за свако дете само избројимо колико постоји деце у сваком од 4 квадранта. За ово напросто итерирамо кроз сву децу после сваког додавања, и са пар провера услова нађемо шмекера. Сложеност O(N^3)

Решење када тачке имају исте x и y координате

У овом случају, можемо да видимо да је други услов тривијално испуњен, па само треба да нађемо дете за које важи да има једнако деце горе десно и доле лево. Ово је еквивалентно са тиме да ако посматрамо да су деца на правој, тражимо оног чија је позиција медијана низа. Стога нам је потребна нека структура која нам омогућава одржавање медијане низа у којем додајемо нове елементе. Ово може да се уради неким јаким структурама као ordered statistic set, али најелементарније решење би било да одржавамо две heap структуре, један где се чува највећих и други где се чува најмањих пола елемената. Када додајемо један елемент у низ, убацимо га у неки од њих, и онда највише једним пребацивањем можемо да одржимо тражену структуру.

Решење када N\leq 4000

Приметимо да је услов да је неко дете шмекер еквивалентан са тиме да је његова x-координата медијана по свим x-координатама, и његова y-координата медијана по свим y-координатама. Заиста, ако је горе лево a_1, горе десно a_2, доле десно a_3 и доле лево a_4 деце, услов за медијане је a_1+a_2=a_3+a_4 и a_1+a_4=a_2+a_3, па сабирањем имамо 2a_1+a_2+a_4=a_2+2a_3+a_4\iff a_1=a_3, из чега закључујемо и a_2=a_4, па дете које је по обе координате медијана је заиста шмекер. Обратно, ако је a_1=a_3 и a_2=a_4, услови a_1+a_2=a_3+a_4 и a_1+a_4=a_2+a_3 су тривијално испуњени, па смо доказали тражену еквиваленцију.

Сада имамо врло лако решење у O(N^2logN) тако што после сваког додавања по обе координате нађемо медијану у O(NlogN), и у зависности од тога јел припада истом детету смо нашли шмекера или нашли да шмекер не постоји.

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

Овде је неопходно само комбиновати идеје из претходна два подзадатка. Као у другом подзадатку одржавамо медијану, али засебно за x- и за y-координату у нашој омиљеној структури. Онда после сваког новог детета, видимо да ли су деца који одговарају тим медијанама једнаки. Укупна сложеност O(NlogN).

[MladenP]

Конструкта

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

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

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

Увек можемо постићи да најудаљенији чвор буде на удаљености D = \frac{N}{4} + 1. Ако чворове на путу индексирамо са x_1, x_2, \dots, x_N поставићемо грану између чворова x_{D + 1} и x_{N - D + 1} и Евровизију ћемо одржати у првом од њих. Лако се може показати да не можемо постићи боље решење за граф који је пут. Потребно је бити пажљив за путеве дужине 4 и 5.

Други подзадатак:

Фиксираћемо чворове између којих ћемо додати грану (O(N^2) могућности) и фиксираћемо чвор у коме ће бити одржана Евровизија (O(N) могућности). Потребно је наћи најкраћи пут од чвора у коме ће бити одржана Евровизија до осталих чворова, што можемо урадити алгоритмом претраге у ширину (БФС). Можемо искористити и одређене модификације претраге у дубину (ДФС), пошто граф садржи тачно један циклус. Временска сложеност овог алгоритма износи O(N^4), док меморијска износи O(N) или O(N^2) зависно од репрезентације графа.

Трећи подзатак:

Обзервација 1: Евровизију увек треба одржати у једном од крајева гране којe додајемо. Ово не повлачи да у неким другим чворовима не можемо одржати Евровизију, већ да је један од крајева гране увек међу оптималним изборима. Приметимо да специјалан случај представљају графови који имају дијаметар (најдужи пут) дужине 2, у том случају додавање нове гране не побољшава решење.

Ово нам пружа подлогу за алгоритам временске сложености O(N^3), пошто за фиксну грану треба да проверимо само две могућности за место одржавања Евровизије. У случају да је дијаметар дужине 2, можемо исписати било коју грану.

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

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

Нека низ чворова x_1, x_2, \dots, x_d представља дијаметар стабла. Приметимо да је максимална удаљеност неког од чворова бинарно претражива и да не може износити више од \frac{d}{2} (ако се Евровизија одржава у чвору x_{\frac{d + 1}{2}}). Претпоставимо да тренутно проверавамо у бинарној претрази да ли може максимална удаљеност бити мања или једнака од c. У том случају оптимално је поставити грану између чворова x_{c + 1} и x_{d - c + 1} и одржати Евровизију у првом од њих или између чворова x_c и x_{d - c} и одржати Евровизију у другом од њих. Када знамо између која два чвора ћемо поставити грану и да један од њих мора бити место одржавања Евровизије, остало је само проверити да ли неки од њих задовољава услов да након постављања гране сви остали чворови буду удаљени не више од c. То можемо поново урадити неким од алгоритама за проналазак најкраћег пута у графу. Укупна временска сложеност O(N log N) и меморијска O(N).

Бонус: Решите задатак у временској сложености О(N).