[Решења задатака] 2022/2023 Државно

Algoritam
1

Б1: Бактеријада

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

T = 1 и N \leq 20

У овом подзадатку је довољно у сваком потезу генерисати све могуће поделе бактерија, њих 2^N. Свака бактерија може да учествује у највише N мерења. Временска сложеност је O(N2^N).

Све бактерије имају исту тежину

Можемо уочити да је оптимално одвајати по једну бактерију у једну групу и преостале у другу. На овај начин максимизујемо укупну суму (доказ остављамо читаоцу за вежбу - помоћ: када quick sort ради најспорије?). Сума ће износити X(N + N + N - 1 + N - 2 + \ldots + 3 + 2) = X\left(\frac{N(N+1)}{2} + N - 1\right), где је X тежина бактерија. Временска сложеност је O(1).

1 \leq N \leq 1000

Слично, као у претходном подзадатку, одвајаћемо по једну бактерију и то баш ону са најмањом тежином (доказ сличан као у претходном подзадатку). После сваког мерења налазићемо најлакшу бактерију и сходно томе рачунати суму, а дељења ће бити тачно N. Временска сложеност је O(N^2).

Решење без додатних ограничења

Уместо симулације бирања у претходном подзадатку, лакше је изанализирати да ће се најлакша бактерија бројати два пута, друга најлакша три пута, …, друга најтежа N пута и најтежа N пута. Временска сложеност је O(N).

2

Б2: XOR фабрика

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

Решење када су све операције +

У овом подзадатку важи да је свака операција +1, тако да ће све што ће се десити +1 тачно R-L+1 пута, односно потребно је исписати X+R-L+1

N,Q\leq 2000

У овом подзадатку напросто можемо да идемо редом за сваки упит и изсимулирамо све операције за сложеност O(NQ)

Решење када су све операције ^

У овом подзадатку решавамо слично као први подзадатак. Приметимо да свака операција број ксорује са 1, а два ксора се поништавају, тако да је битна само парност R-L+1: ако је парно онда испишемо X, а у супротном X\text{ xor }1.

Решење када има највише 500 операицја ^

Поделимо наш интервал на (највише 500) интервала са свим операцијама +. Сваки од њих симулирамо по првом подзадатку, и онда само применимо по једну операцију ^. Сложеност O(500Q)

Решење без додатних ограничења

Приметимо да нам се у сваком потезу заправо мења парност. Тако да ће свака операција бити +1 осим неких ^ операција која ће бити -1 ако је тада број на ком вршимо иницијалне потезе непаран. Међутим, оно што треба приметити да нам је онда само потребан број ^ на местима одређене парности (та одређена парност зависи од L и X: ако је X парно онда исте парност као L нам треба, а у супротном супротна парност). Зато је довољно само запамтити два низа парцијалних сума: за парне и непарне позиције број операција ^, и онда класичним одузимањем десног краја од левог нађемо колико их је у интервалу. Сложеност O(N+Q)

3

Б3: Кирби

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

1 \leq N,M,P \leq 5

У овом подзадатку користимо то да су све вредности мале бројке. Можемо избрисати свако прљаво поље и затим испробати све путање да видимо која садржи највећи број упрљаних поља и да ли се то разликује од почетног максималног броја поља које Кирби може да очисти. Временска сложеност је O(TP2^{N+M}).

N = 2 или M = 2

Посматраћемо случај N=2, јер се други случај аналогно решава. Приметимо да ће се Кирби тачно једном спустити у други ред. Памтимо префиксни низ прљвих поља за први ред и памтимо суфиксни низ прљавих поља за други ред. Максималан број поља које Кирби може да очисти је S = \max_{1 \leq i \leq M}\{pref_i + suf_i\}. Нека је i_{min} прва колона у којој израз pref_{i_{min}} + suf_{i_{min}} достиже вредност S и нека је i_{max} последња колона у којој израз pref_{i_{max}} + suf_{i_{max}} достиже вредност S. Тражено решење је pref_{i_{min}} + suf_{i_{max}}. Временска сложеност је O(T(P+M)).

1 \leq N,M,P \leq 100

Нека је S поново максималан број поља које Кирби може да очисти у старту. То можемо израчунати стандардним динамичким програмирањем. Стање dp_{i,j} представља максималан број поља које Кирби може да очисти крећући са поља (1,1) до поља (i,j). Кренемо “редом” да обилазимо матрицу по редовима, па по колонама (као у улазу) и вршимо прелаз dp_{i,j} = \max(dp_{i-1,j}, dp_{i,j-1}) + a_{i,j}, где је a_{i,j} бинарни индикатор да ли је поље (i,j) урљано (1 ако јесте, 0 ако није). Сада можемо да избацујемо једно по једно упрљано поље и рачунамо изнова целу dp матрицу и видимо када је вредност dp_{N,M} < S. Временска сложеност O(TPNM).

Решење без додатних ограничења

Можемо приметити да када посматрамо редом поља која је Кирби очистио, њихове колоне формирају неопадајући низ. Односно, уколико сортирамо упрљана поља по редовима, максималан број поља која Кирби може да очисти је најдужи неопадајући подниз колона овог низа. Дати проблем је еквивалентан налажењу најдужег растућег подниза (\emph{Longest increasing subsequence}, или скраћено LIS), што је познат проблем и може се решити/имплементирати у временској сложености O(P\log P). Оно што нама треба јесу префиксни и суфиксни LIS низови. Формално, pref_i представља LIS од почетка низа до i-тог елемента, али тако да он засигурно фигурише у LIS-у. Слично, suf_i представља LIS низа од i-тог елемента до краја низа, тако да i-ти елемент учествује у LIS-у. За i-ти елемент низа упрљаних поља важи да је део неког од путања које садрже највећи број упрљаних поља ако и само ако је pref_i + suf_i - 1 = S. Са друге стране, елемент низа припада свим таквим путањама ако и само ако додатно важи и да је вредност pref_i јединствена међу свим префиксним LIS-овима. Потребно је само исписати број таквих поља. Временска сложеност је O(TP\log P).

4

А1: Живот у граду

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

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

У овом случају, због ограничења на дужину величину табле могуће је у датом временском ограничењу проверити све путеве и одредити за сваки од њих колико се концерта одржава на том путу. Наиме број разних путвеа је 2^{N+M-2}\leq 2^{18}. Наравно, ако је на неком путу број концерта баш K, прекида се проверавање путева, исписује одговор “DA” и ако је потребно исписује одговарајући пут. Ако ни на једном путу није било K концерта, исписује се одговор “NE”. Сложеност описаног решења је {\mathcal O}(2^{N+M}).

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

За почетак је потребно одредити подматрицу коју чине поља на којима се одржавају концерти. Након тога треба дискутовати (разликовати) неколико случајева, у зависности од димензија и позиције подматрице и броја K. Мислимо да нема потребе да изводимо комплетну дискусију. Сложеност описаног решења је {\mathcal O}(NM).

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

Ови подзадаци се могу решити применом динамичког програмирања. Нека је dp[i][j][l]=true, ако постоји пут од поља (1,1) до поља (i,j) на коме постоји l поља на којима се одржава концерт и dp[i][j][l]=false у супротном. Тада је dp[N][M][K] одговор на питање да ли постоји тражени пут или не. Низ dp попуњавама (рачунамо) врста по врста:

  • dp[1][1][1]=true, ако се на пољу (1,1) одржава концерт и dp[1][1][1]=false, ако се на пољу (1,1) не одржава концерт.
  • dp[1][1][0]=true, ако се на пољу (1,1) не одржава концерт и dp[1][1][0]=false, ако се на пољу (1,1) одржава концерт.
  • dp[1][1][l]=false, за 2\leq l \leq K.
  • Ако се на пољу (i,j) одржава концерт, онда је dp[i][j][l]=true, ако и само ако је dp[i-1][j][l-1]=true или dp[i][j-1][l-1]=true (наравно, ако је i \geq 2 и j \geq 2, у супротном, одговарајући елемент не постоји). Приметимо такође да је у овом случају dp[i][j][0]=false.
  • Ако се на пољу (i,j) не одржава концерт, онда је dp[i][j][l]=true, ако и само ако је dp[i-1][j][l]=true или dp[i][j-1][l]=true (наравно, ако је i \geq 2 и j \geq 2, у супротном, одговарајући елемент не постоји).

Ако тражени пут постоји, он се може реконстрисати коришћењем низа dp. Наиме, крећемо од поља (N,M) и тражимо пут на коме се одржава K концерта. Ако се налазимо на пољу (i,j) и тражимо пут на коме се одржава l концерта, онда мора бити dp[i][j][l]=true и могу наступити следећа два случаја:

  • На пољу (i,j) се оджава концерт. Тада број концерата смањујемо за један, тј. l се смањује за један (l \leftarrow l-1) и померамо се на поље лево или горе (ако постоји) за које одговарајући елемент низа dp (dp[i-1][j][l-1] или dp[i][j-1][l-1]) има вредност true.
  • На пољу (i,j) се не оджава концерта. Тада број коцерта остаје непромењен, а померамо се на поље лево или горе (ако постоји) за које одговарајући елемент низа dp (dp[i-1][j][l] или dp[i][j-1][l]) има вредност true.
  • Поступак прекидамо када стигнемо до поља (1,1).

Сложеност описаног решења је одређена сложеношћу попуњавања низа dp и износи {\mathcal O}(NMK).

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

У овом случају можемо формирати граф у коме су чворови поља на која је подељен град, а ивице постоје од поља до његових суседа лево и доле. Поља на којима се одржавају концерти су забрањена и на њих се не може стати. Тражени пут постоји, ако постоји пут у графу (пут заобилази забрањена поља). Тај пут можео пронаћи, на пример, применом обиласка у ширину. За свако поље можемо памтити одакле смо стигли и на тај начин реконструисати решење. Сложеност описаног решења је {\mathcal O}(NM).

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

Нека је dp_1[i][j] минимални број l такав да постоји пут од поља (1,1) до поља (i,j), на коме се одржава l концерата. Нека је dp_2[i][j] максимални број l такав да постоји пут од поља (1,1) до поља (i,j), на коме се одржава l концерата. Тада за свако поље (i,j) важи да постоји пут од поља (1,1) до поља (i,j) на коме се одржава l концерта, где је l било који број између dp_1[i][j] и dp_2[i][j] (dp_1[i][j]\leq l \leq dp_2[i][j]). Наиме од било ког почетног пута између два поља се може стићи до било ког завршног, тако што се прелази преко низа путева од којих се свака два узастопна разликују у само једном пољу. Када се на путу промени само једно поље и број поља на којима се одржава концерт се може променити (смањити или повећати) за највише један (1). Ако кренемо од пута са минималним бројем концерта према путу са максималним бројем концерта, проћи ћемо преко путева на којима је број концерта било који број између та два броја.
Због тога, постоји пут са тачно K концерата, ако и само ако је dp_1[N][M]\leq K \leq dp_2[N][M].
Низове dp_1 и dp_2 рачунамо на сличан начин као низ dp у четвртом и петом подзадатку:

  • Ако се на пољу (1,1) одржава концерт, онда је dp_1[1][1]=dp_2[1][1]=1.
  • Ако се на пољу (1,1) не одржава концерт, онда је dp_1[1][1]=dp_2[1][1]=0.
  • Ако се на пољу (i,j) одржава концерт, онда је dp_1[i][j]=\min(dp_1[i-1][j],dp_1[i][j-1])+1 и dp_2[i][j]=\max(dp_2[i-1][j],dp_2[i][j-1])+1.
  • Ако се на пољу (i,j) не одржава концерт, онда је dp_1[i][j]=\min(dp_1[i-1][j],dp_1[i][j-1]) и dp_2[i][j]=\max(dp_2[i-1][j],dp_2[i][j-1]).

Ако постоји пут са тачно K концерата, онда се он реконструише тако што се крене од поља (N,M) и тражи пут који има l=K концерата. Ако се налазимо на пољу (i,j) и тражимо пут који има l концерата (dp_1[i][j]\leq l \leq dp_2[i][j]), онда могу наступити два случаја:

  • Ако се на пољу (i,j) одржава концерт, онда треба смањити број концерата l за један и прећи на поље изнад или поље лево, тако да број концерата буде између dp_1 и dp_2 за то ново поље.
  • Ако се на пољу (i,j) не одржава концерт, онда се број концерата l не мења, а треба прећи на поље изнад или поље лево, тако да број концерата буде између dp_1 и dp_2 за то ново поље.
  • Поступак прекидамо када стигнемо до поља (1,1).

Сложеност описаног решења је одређена сложеношћу попуњавања низова dp_1 и dp_2 и износи {\mathcal O}(NM).

5

А2: Бекство

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

Анализа

Примена K операција се заправо може урадити одједном: избришемо највише K грана, и додамо нове тако да нам граф поново постане стабло. Приметимо да је оптимално да нове гране додајемо на крајеве дијаметара “изрезаних” стабала (стабла на која смо поделили оригинално стабло када смо избрисали неке гране) тако да од њих направимо пут. Тада ће, у оптималном решењу, крајњи дијаметар стабла бити једнак суми дијаметара изрезаних стабала плус број додатих грана.

Случај K=N је еквивалентан са K=N-1, па ћемо разматрати само 0 \leq K < N.

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

Бираћемо гране које бришемо и за сва стабла која нам остану израчунати дијаметре, и те дијаметре ћемо сумирати. Могућих подела у најгорем случају има 2^{N-1} (сваку грану или бришемо или не бришемо), а дијаметар стабла можемо наћи у O(N) - пустимо претрагу из насумичног чвора, обележимо најдаљи чвор од њега као први крај дијаметра, пустимо претрагу из тог чвора и обележимо најдаљи чвор као други крај дијаметра. Овај алгоритам ради јер је најдаљи чвор од произвољног чвора увек крај неког дијаметра, а најдаљи чвор од краја дијаметра је други крај тог дијаметра.

Временска сложеност овог алгоритма је O(2^NTN), што пролази први подзадатак. Међутим, не морамо разматрати свих 2^{N-1} подела - довољне су само оне где бришемо тачно K грана (ако смо избрисали неки број грана, никад не можемо добити лошије решење ако избришемо још неке). Овако ћемо разматрати само {N \choose K} \leq {N \choose N/2} подела, и решење нам лако пролази други подзадатак.

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

Пошто је K = 0, решење је само дијаметар почетног стабла. Овде дијаметар не морамо ни тражити O(N) алгоритмом: довољно је да из сваког чвора пустимо по претрагу.

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

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

Итерираћемо кроз све гране, и за сваку у O(N) рачунати дијаметре два стабла која добијемо њеним брисањем.

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

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

Није потребно експлицитно тражити дијаметре изрезаних стабала. Лакше нам је да уз свако изрезано стабло само изаберемо неки пут које му припада - у оптималном решењу ће се свакако испоставити да су то дијаметри.

Дефинишимо dp[u][k][x] као највећу могућу суму изабраних путева у подстаблу чвора u ако смо у њему применили k операција, а x је 0, 1, или 2 у зависности од тога колико још можемо да “додајемо” на наш изабран пут. Другим речима, ако је изабран пут тренутног подстабла само чвор u, онда на њега можемо додати путеве који долазе из два различита сина, па је x = 0. Ако се изабран пут тренутног подстабла завршава у u, онда је x=1, а ако је пут већ у потпуности изабран и не додајемо му ништа, онда је x=2.

dp[u][k][x] се налази динамичким програмирањем по стаблу: итерирамо кроз синове, нека је тренутни син v. У dp[u] имамо израчунат dp за подстабло од u, а у dp[u] имамо израчунат dp за стабло сачињено од u и подстабала свих синова кроз које смо до сада итерирали. Желимо да “спојимо” dp вредности за u и v, па да у dp[u] после буде израчунат dp за стабло коме је додато и подстабло од v.

Спајање dp-ова два стабла се може урадити у O(N^2): итерирамо кроз број грана које ћемо брисати у првом стаблу (i), након тога кроз број грана које бришемо у другом (j), и у неки нови dp низ ажурирамо вредности за i + j или i +j +1 избрисаних грана (у зависности од тога да ли бришемо грану од u до v). Постоји неколико случајева: да бришемо грану од u до v и додајемо дужине њихових изабраних путева, да не бришемо грану од u до v већ на пут који се завршава у u додајемо пут који се завршава у v, или да не бришемо грану али да изаберемо само један од два изабрана пута подстабала u и v.

Крајње решење ће бити max(dp[1][K][0], dp[1][K][1], dp[1][K][2]) + K. Ако разматрамо да свако стање у dp[u][k][0] припада и dp[u][k][1], и да свако стање у dp[u][k][1] припада и dp[u][k][2] (што значајно олакшава имплементацију), решење је dp[1][K][2] + K.

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

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

Главно решење је исто као за трећи подзадатак, само што током спајања подстабала не итерирамо кроз вредности које су сигурно немогуће. Другим речима, за сина (v) ћемо само итерирати до величине његовог подстабла, а за корен подстабла (u) ћемо само итерирати до величине тренутног стабла које његов dp представља (јер је немогуће избрисати више грана од тога).

Није тешко доказати да сложеност алгоритма сада постаје O(N^2). Када спајамо dp-ове два стабла, итерирамо до њихових величина - што можемо представити као да се сваки чвор који припада првом стаблу упарује са сваким из другог. Пошто ће након тога сви ти чворови припадати истом стаблу, можемо приметити да ће свака два чвора да се упаре тачно једном - што даје укупно O(N^2) упаривања.

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

Бонус: Решите задатак у O(TNlogN).

1 Like
6

А3: Туризам

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

Анализа

Прво, приметимо да ћемо увек посетити неки подниз који садржи почетно поље x. Ако је подниз који посетимо [L, R], НР на крају ће бити A_L \ \text{and} \ A_{L+1} \ \text{and} \ \ldots{} \ \text{and} \ A_R (записаћемо као f(L, R)), а минималан број корака да се посети је R - L + min(x - L, R - x) (тако што из почетка одемо до леве границе, па до десне, или обрнуто).

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

У овом подзадатку можемо итерирати кроз сваку могућу леву и десну границу, и укупну \text{and} вредност рачунати једним проласком кроз подниз.

Укупна сложеност: {\mathcal O}(QN^3)

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

Исто ћемо итерирати кроз сваку могућу леву и десну границу, али ћемо чувати вредности f(L, x) и f(x, R) и ажурирати их током итерација. Сада не морамо да итерирамо кроз цео подниз да бисмо нашли f(L, R), већ га добијемо из сачуване две вредности.

Укупна сложеност: {\mathcal O}(QN^2)

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

За наредне подзадатке потребна нам је још једна кључна опсервација: оптимални подниз ће увек имати леву и десну границу у пољима где се укупан НР мења, тј. у L и R таквим да важи f(L, x) \neq f(L + 1, x) (или L = x) и f(x, R) \neq f(x, R - 1) (или R = x). Ово је тачно јер, ако је на граници поље које не мења НР, можемо га само избацити из подниза.

У овом подзадатку је, дакле, могуће само неколико случајева: да директно идемо из x у најближу нулу, да идемо из x до најближе леве јединице и до најближе десне двојке (или обрнуто), или да, ако су жељена јединица и двојка са исте стране, одемо из x до даље од њих.

Позиције најближе леве и десне нуле, јединице и двојке можемо наћи преко структуре std::set и њене функције upper_bound.

Укупна сложеност: {\mathcal O}(QlogN)

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

Позиције које мењају НР су заправо оне за које важи да постоји неки бит који се не налази у њеном елементу, али се налази у елементима на свим позицијама од ње до x.

За сваки бит можемо једним проласком кроз низ наћи најближу леву и десну позицију чији елемент не садржи тај бит, нека су за i-ти би те две позиције l_i и r_i, а наш интервал мора да садржи или једну или другу. Другим речима, услов можемо да формулишемо као: ако је лева граница већа од l_i, онда је десна граница већа једнака r_i.
Зато можемо да итерирамо кроз сортиран низ потенцијалних левих граница (којих има log(A_i)) и да одржавамо тренутну минималну десну границу, и тако налазимо минимално решење.

Сложеност овог алгоритма је {\mathcal O}(QNlog(A_i)), што би уз покоју оптимизацију прошло. Међутим, налажење левих и десних граница може да се уради у {\mathcal O}(N + log(A_i)) уместо {\mathcal O}(Nlog(A_i)), тако што почнемо из x и крећемо се лево или десно (у зависности од тога коју границу налазимо), чувајући тренутну \text{and} вредност тог интервала. Када се та вредност промени, итерирамо кроз оне битове где се променила и за њих одређујемо да им је граница на тој позицији.

Укупна сложеност: {\mathcal O}(Q(N + log(A_i)))

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

У овом подзадатку ћемо брже налазити позиције нула: за сваки бит чувамо низ позиција чији елементи немају тај бит. Сада можемо бинарном претрагом да брзо нађемо жељене елементе.

Укупна сложеност: {\mathcal O}(Qlog(N)log(A_i))

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

Главно решење се ради на исти начин као пети подзадатак, само што се уместо низа позиција користи структура std::set, која се лако може ажурирати у случају догађаја првог типа.

Укупна сложеност: {\mathcal O}(Qlog(N)log(A_i))