[Решења задатака] 2024/2025 Изборно Дан 1

Sprdalo · May 31, 2025, 3:53pm

Узумаки

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

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

У овом подзадатку можемо симулирати мешање клонова и на крају исписати моћ клона на позицији K.

За сваку операцију, подниз клонова можемо сортирати растуће било којим ефикасним алгоритмом сортирања (сложености N\log N).

Временска сложеност: O(QN\log N)
Меморијска сложеност: O(N)

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

Слично као претходни подзадатак, само за операцију другог типа подниз морамо сортирати у опадајућем поретку.

Временска сложеност: O(QN\log N)
Меморијска сложеност: O(N)

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

Потребно је приметити да је низ у Узумаки поретку ако и само ако је ,спирално сортиран’', односно, да је најмањи елемент на првој позицији, други најмањи на последњој позицији, трећи најмањи на другој позицији, четврти најмањи на претпоследњој позицији, итд.

Након тога, слично као претходни подзадатак, само за операцију трећег типа можемо подниз копирати у нови низ, сортирати растуће, и онда поређати назад у оригинални низ у Узумаки поретку.

Временска сложеност: O(QN\log N)
Меморијска сложеност: O(N)

Четврти подзадатак

Решење ће бити најмањи елемент који се налази у последњем интервалу који садржи први елемент (у тренутку те операције). Онда су у оптицају сви елементи који су на почетку низа у том интервалу, али и сви елементи који претходним операцијама заврше у том интервалу. Назовимо овај интервал x_1.

Идемо уназад по операцијама од овог интервала и нађимо први следећи који се сече са интервалом x_1 (назовимо га x_2). Сада знамо да решење може бити и било шта из уније x_1 \cup x_2, у тренутку операције (пошто ће најмањи елемент из x_2 завршити у интервалу x_1 након операције). Настављамо даље и у унију додајемо све интервале који се секу са досадашњом унијом.

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

Временска сложеност: O(N + Q)
Меморијска сложеност: O(N + Q)

Алтернативно решење: можемо приметити да у било ком интервалу, само најмањи елемент на том интервалу има потенцијал да буде решење. Такође, пошто је t_i = 1, решење ће се увек померати на лево.

Због тога, довољно је да за сваки интервал ефикасно нађемо најмањи елемент, и поставимо га на прву позицију у том интервалу. На крају, решење ће се налазити на првој позицији у низу. За ово можемо користити сегментно стабло.

Временска сложеност: O(Q\log N + N)
Меморијска сложеност: O(N)

Пети подзадатак

Пошто је A_i мало, има смисла да размишљамо о сортирању бројањем (counting sort) - ако имамо cnt_i појављивања броја i у неком интервалу и желимо да га сортирамо растуће, на првих cnt_1 позиција интервала поставићемо 1, на следећих cnt_2 позиција 2, итд. За сортирање опадајуће бисмо само ишли обрнутим редоследом.

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

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

Временска сложеност: O(QA_i\log N + N)
Меморијска сложеност: O(A_iN)

Шести подзадатак

Прва два типа операција извршаваћемо на исти начин као у претходном подзадатку - потребно је додатно анализирати како ефикасно постављати елементе по Узумаки поретку.

Уколико је cnt_1 парно, прву половину јединица ћемо ставити на почетак, а другу половину на крај интервала. Уколико је непарно, јединицу вишка ставићемо на почетак.

Уколико је cnt_2 парно, опет ћемо прву половину двојки ставити на почетак преосталог низа, а остатак на крај. Уколико је непарно, овај пут је нешто компликованије. Уколико смо до сад (за све претходне вредности) ставили једнако елемената на почетак и крај низа, онда ће вишак елемент ићи на почетак. У супротном, вишак елемент иде на крај преосталог дела интервала.

Овакав процес настављамо док не попунимо низ.

Временска сложеност: O(QA_i\log N + N)
Меморијска сложеност: O(A_iN)

Седми подзадатак

У претходна два подзадатка смо успели да генеришемо цео низ на крају, док ћемо овде користити чињеницу да нам је потребно да нађемо само елемент на позицији K.

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

Сада када можемо ово ефикасно проверити, можемо користити бинарну претрагу по решењу како бисмо нашли праву вредност одговора.

Временска сложеност: O(Q\log N\log A_i + N)
Меморијска сложеност: O(N + Q)

Решење за 100 бодова

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

Временска сложеност: O(Q\log N\log A_i + N)
Меморијска сложеност: O(N + Q)

Алтернативно решење: уместо сегментог стабла можемо поделити низ на интервале нула и јединица и одржавати скуп тих интервала. Сваком операцијом се број интервала повећава за највише 3, док се може значајно смањити. Зато ће укупан број промена ових интервала бити O(N + Q).

Временска сложеност: O((N + Q)\log N\log A_i)
Меморијска сложеност: O(N + Q)

Sprdalo · May 31, 2025, 3:54pm

Меси

Аутор: Марко Миленковић

Текст: и тест примери: Марко Миленковић

Анализа решења: Марко Миленковић

Тестирање: Драган Урошевић

Напомена

Дата структура у задатку је планаран граф са најмањим степеном чвора 3. За планарне графове важи Ојлерова формула и на основу ње се може доказати да у оваквом графу да је најмањи циклус дужине највише пет. Дакле опције су 3, 4 или 5 као одговор. Главна идеја је да тражимо циклусе дужине три и четири и уколико их нема, одговор је пет.

Нетачно решење

Вреди поменути да разматрање само лица графа није довољно. Пример графа таквог графа:

n <= 10

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

n <= 20

У овом подзадатку можемо да пробамо свих 2^n опција за циклус.

n <= 100

У овом подзадатку можемо да брут форсом претражимо све циклусе дужине три или четири. Како је граф редак, и има највише 3n грана, довољно је одрадити најпростију варијанту.

Решење је непаран број

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

n <= 5000

Тестирање за постојање циклуса дужине три радимо као и раније. Сличном методом можемо видети да ли постоји циклус дужине четири. За сваке две узастопне гране (оваквих нема много, јер је граф планаран) проверимо да ли имају заједнички суседан чвор.

Степен сваког чвора у графу је највише 5

Ово решење је јако слично као за потпун задатак (видети доле). Једина разлика је што за овај подзадатак не морамо да уочимо да постоји бар један чвор степена највише пет.

Постоје барем два чуња између којих најкраћи пут има барем 25 коридора

У овом подзадатку је могуће применити small-to-large технику приликом бројања циклуса дужине три и четири.

Без додатних ограничења

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

Уочимо чвор степена највише пет
Усмеримо све гране суседне том чвору ка ван
Обришемо уочени чвор и њему суседне гране

Можемо се уверити да граф који правимо на овај начин задовољава услове.

Циклусе дужине три већ знамо како да нађемо из ранијих подзадатака. За сваки циклус дужине четири постоје три конфигурације у којима може да се нађе:

Уколико идемо по циклусу гране су редом: у правом смеру, у правом смеру, у погрешном смеру, у погрешном смеру
Уколико идемо по циклусу гране су редом: у правом смеру, у правом смеру, у погрешном смеру, у правом смеру
Уколико идемо по циклусу гране су редом: у правом смеру, у погрешном смеру, у правом смеру, у погрешном смеру

Прва два случаја можемо да решимо ограниченом потрагом у ширину у линеарном времену. За трећи случај можемо меморисати све парове грана које излазе из чвора. Међу свима њима тражимо да ли постоје два пара са истим крајевима. Временска сложеност овде је, због тога што планарни граф нема много грана, \mathcal{O}(n\log n).

Sprdalo · May 31, 2025, 3:56pm

Шафлер

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

Сви елементи су различити

Пошто су сви елементи различити, а нас интересује само број различитих низова које можемо да добијемо, саме вредности елемената нам нису битне, па ће сви низови дужине n имати исто решење. Нека је s_n решење за низове дужине n. Приметимо да када додајемо нови елемент на крај низа је једино битно да ли операцију мењања последња два елемента радимо пре или после операције мењања претпоследњег и трећег од позади. Ако смо прво заменили последњи и претпоследњи елемент, онда се првих n-2 елемената заједно са оригиналним последњим понашају као низ дужине n-1 са свим различитим елементима. Ако смо прво заменили претпоследњи и трећи од позади, онда се првих n-1 елемената понашају као низ дужине n-1 са свим различитим елементима, при чему ће се у неком тренутку заменити последња два елемента и то неће имати никакве последице на остатак низа. Одавде следи да је s_n=2\cdot s_{n-1} за n>2 (јер смо користили барем три елемента у горенаведеној транзицији). Очигледно је s_1=s_2=1.

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

N\leq 8

У овом подзадатку је довољно испробати све могуће распореде операција. Како имамо N-1 могућих операција, број могућих распореда за те операције је (N-1)! и за сваки од тих распореда треба да видимо који низ добијамо и да елиминишемо дупликате.

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

Шта даље?

Посматрајмо замену на позицијама i и i+1, она ће пребацити тачно један елемент са леве на десну страну и тачно један елемент са десне на леву страну. Приметимо да је то једини начин да неки елемент из [1,i] пређе у [i+1,N] и обрнуто. Како се та замена мора догодити, за сваки префикс ће тачно један елемент прећи из њега у њему одговарајући суфикс, и један елемент из тог суфикса ће прећи у префикс. Ово нас наводи да пробамо да решимо задатак динамичким програмирањем са следећим стањима: dp_{i,j,k} = \text{број различитих пермутација за првих }i\text{ елемената ако у тај префикс уђе }j{ и из њега изађе }k.

Потребно је пронаћи транзиције. Удахнимо дубоко и посматрајмо два случаја:

k\neq A_i:

Како k мора да дође до позиције i пре него што изађе из префикса дужине i, тако су нам све замене између позиције где се налази k и i-те позиције једнозначно одређене и оне баш пребацују a_i у префикс првих i-1 елемената и из њега избацује k. Тако добијамо:
dp_{i,j,k} = dp{i-1,A_i,k}

k = A_i:

Ако се замена (i-1,i) десила пре замене (i,i+1):

у овом случају је јасно да се префикс првих i-1 елемената понаша изоловано и да је решење dp_{i-1,A_i,A_i}.

Ако се замена (i,i+1) десила пре замене (i-1,i):

Како је j ушао у префикс дужине i пре него што се десила замена (i-1,i), то ће j ући у у префикс дужине i-1, док ће из њега може изаћи било који елемент. У преводу, решење је \sum_{x\text{ у префиксу дужине }i-1}dp_{i-1,j,x}.

Сада приметимо да је могуће да смо у прошла два случаја неке распореде бројали два пута. То је једино могуће ако у првом случају A_i уђе и изађе (из префикса i-1) и ако у другом случају j уђе и изађе (из префикса i-1) или ако је A_i=j.

Урадимо прво случај када је A_i=j:

Ово је заправо случај у коме је A_{i-1}=A_i=A_{i+1}, тада се цео први случај садржи у другом и само је потребно одузети dp_{i-1,c,c}.

Сада разматрамо шта се дешава када A_i\neq j:

Прво приметимо да није могуће да се у оба пребројавања замена (i-2,i-1) десила пре замене (i-1,i), тако је у неком случају A_{i-1} баш елемент који излази из префикса дужине i-1 па је A_{i-1}=A_i или A_{i-1}=j.

A_{i-1}=A_i:

Детаљним разматрањем овог случаја добијамо да је вишак dp_{i-2,A_i,j}.

A_{i-1}=j:

Детаљним разматрањем овог случаја добијамо да је вишак dp_{i-2,j,A_i}.

Сада можемо да издахнемо и резимирамo:

if k != A[i]:
    dp[i][j][k] = dp[i-1][A[i]][k]
else:
    dp[i][j][k] = dp[i-1][A[i]][A[i]] + sum([dp[i-1][j][x] for x in range(1,N+1)])
    if A[i] == j:
        dp[i][j][k] -= dp[i-2][A[i]][j]
    elif A[i-1] == j:
        dp[i][j][k] -= dp[i-2][j][A[i]]

N\leq 100

Наивном имплементацијом горенаведених транзиција добијамо решење овог подзадатка.

Временска сложеност: O(N^4)
Меморијска сложеност: O(N^3)

N\leq 500

Полунаивном имплементацијом горенаведених транзиција добијамо решење овог подзадатка.

Временска сложеност: O(N^3)
Меморијска сложеност: O(N^3)

N\leq 5000

За решење овог подзадатка приметимо да dp_{i,j,k}, када је k\neq A_i, не зависи од j. Можемо сада направити две табеле:

dp^1 за случај када је k\neq c

dp^1_{i,k} := dp_{i,j,k} за k\neq c и dp^1_{i,k} := 0 за k=c

dp^2 за случај када је k=c:

dp^2_{i,j} := dp_{i,j,c}

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

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

N\leq 500000

За цело решење је довољно приметити да скоро све промене које се дешавју између dp^1_i и dp^1_{i+1} као и између dp^2_i и dp^2_{i+1} се дешавају паралелно. Тако можемо да, уместо да за свако i рачунамо цео низ изнова, приметимо да су нам потребна само претходна два низа и да на њима подржавамо операције: ”промени елемент на једној позицији”, ”додај број на све елементе низа”, ”одузми цео низ од другог”. За детаље можете погледати имплементацију комисијског решења.

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