[Решења задатака] 2023/2024. Окружно

Algoritam
1

Усамљеност

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

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

Пролазимо по поднизовима узастопних ученика преко две угнежђене петље. Затим за сваки подниз проверавамо да ли је усамљен или не. Број поднизова је O(N^2), а сложеност провере за сваки је O(N). Стога је укупна временска сложеност O(N^3).

Решење када N\leq 5\,000

Понављамо идеју претходног подзадатака - пролазимо по свим поднизовима. Проверу је неопходно извршити ефикасније. Најједноставније је то учинити наредним псеудо-кодом, у коме “успутно” рачунамо број математичара и физичара:

for (i in [1,N]):
	br_mat=0
	br_fiz=0
	for (j in [i,N]):
		if S[i] is 'M':
			br_mat+=1
		if S[i] is 'F':
			br_fiz+=1

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

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

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

Нека су F_1 < F_2 < \ldots < F_K позиције свих физичара. За 1 < i < K важи да је физичар i поцепао слике које представљају под-интервале [L,R] \sub [F_{i-1}+1,F_{i+1}-1] који садрже i. Тачније, важи F_{i+1}+1 \leq L \leq F_i и F_i \leq R \leq F_{i+1}-1.

  • За L имамо F_i - F_{i-1} опција;
  • За R имамо F_{i+1}-F_i.

Како је избор L и R независан, укупан број избора је (F_i-F_{i-1}) \cdot (F_{i+1}-F_i) - 3. Одузимамо поднизове дужине мање од 3 (њих има тачно 3). Уколико је вредност израза негативна, узимамо 0 (дешава се да ученик не поцепа ниједну слику).

Приликом рачунања формуле, у случају i=1 можемо узети F_{i-1}=F_i, а у случају i=K можемо узети F_{i+1}=F_i.

Сада знамо како да за сваког физичара израчунамо број слика које је поцепао. Исти поступак примењујемо и за математичаре. Када све бројеве добијене као резултате формула просумирамо, добијамо коначан одговор. Сложеност наведеног решења је O(N).

2

Дeјн

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

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

Пошто је већ дат целобројни низ t у коме чланови низа t_i ако су строго позитивни, t_i>0, представљају излазак, а уколико су негативни, t_i<0 улазак, то је најсврсисходније најпре испитати да ли је број излазака једнак броју улазака и исписати -1 ако се утврди да број строго позитивних чланова не одговара броју негативних чланова низа. Ово пребрајање позитивних и негативних чланова могуће је извести једним проласком кроз све чланове низа, односно у временској сложености \mathcal{O}(n), где је n број чланова низа.

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

Када је низ сортиран, на једноставан начин могуће је довршити проверу да ли је он заиста и исправан. Наиме, сви јединствени чланови низа на парним индексима (укључујући и први) морају бити позитивни, а на непарним (укључујући и последњи) негативни, поштујући конвенцију да први члан низа има нулти индекс. Приметити да сви исправни низови имају парну дужину (на основу услова да број позитивних чланова мора бити једнак броју негативних), односно да је n дељиво са два. Стога, ако су се први излазак и последњи улазак десили у јединственим временским тренуцима то је први члан сортираног низа позитиван, а последњи негативан.

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

Коначно, како је најсложенија операција у претходно описаном решењу заправо алгоритам сортирања, то \mathcal{O}(n \log n) представља укупну временску сложеност решења овог задатка која је логлинеарна по дужини улазног низа. Иако је задатак било могуће решити и без употребе сортирања у линеарној временској сложености \mathcal{O}(n) користећи се неким мало напреднијим структурама података, ово решење се није захтевало за максималан број поена на овом нивоу такмичења.

3

Битвајз орањe

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

Решење када N=2

Видимо да уколико је у питању интервал дужине 1, Ања има победничку стратегију само са један број (управо ту вредност). Уколико је интервал дужине 2, онда Богдан бира да ли ће на та два применити or или xor, тако да Ања може победити само за једну вредност и то само уколико су a\bigoplus b и a|b једнаки.

Када Ања има победничку стратегију?

Докажимо следеће тврђење: За сваки позицију бита i погледајмо у колико елемената је иницијално постављен на 1. Уколико је сваки бит највише једном постављен на 1, онда Ања побеђује за тачно једну вредност, а уколико није тако, онда Ања никад не побеђује.

Заиста, ако се сваки бит јавља највише једном, онда ма шта радили Ања и Богдан, на крају ће се добити број који има јединице управо на позицијама на којима постоји јединица на неком иницијалних бројева. (ово се може нпр формално видети индукцијом). Уколико постоји неки бит на ком бар два иницијална броја имају јединице, онда Богдан може да намести да је вредност на тој позицији или 0 или 1 на крају како жели, и самим тим избегне било који Ањин циљни број. Наиме, он може да увек бира да ради a|b, док не остану тачно два броја са тим битом. Надаље ради произвољно док га не пита управо за та два броја што имају јединицу на биту који посматрамо (ако учествује само један такав број у операцији, не смета Богдану ништа јер шта год радио, нови број ће опет имати јединицу на тој позицији, па ће још увек остати тачно два броја са јединицом на тој позицији). Уколико жели да добије на крају 0 на тој позицији, урадиће a\bigoplus b и неће остати ниједна јединица на тој позицији, па ће и на крају ту бити 0. Са друге стране ако жели на крају да добије 1 на тој позицији, урадиће a|b, па ће остати једна јединица на тој позицији, а надаље шта год Ања и Богдан радили ће остати тачно једна јединица на тој позицији, слично првом решењу. Овиме је тврђење доказано.

Решење када су све вредности 1, 2 или 3

Може се лако доказати из претходног да овде Ања има победничку стратегију за једну вредност ако је низ дужине 1 или је скуп карата управо \{1,2\}, у супротном је одговор 0.

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

Може се доказати из претходног да овде Ања има победничку стратегију за једну вредност ако и само ако су све вредности низа различите, а у супротном је одговор 0. Имплементацију овог можемо урадити тако што ако је интервал дужине преко 60 само кажемо да је одговор 0 (јер постоји само 60 различитих вредности), а у супротном можемо да га сортирамо и видимо да ли су суседне вредности различите, што нам даје да на сваки упит можемо одговорити у сложености O(\log\max A_i\log\log\max A_i).

Решење када је N\leq 100

Овде за сваки бит можемо да идемо редом кроз и видимо да ли је на јединственој позицији сетован на један, и тиме сваки упит решимо у O(N\log\max A_i).

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

Уколико нема промена низа, можемо за сваки бит да запамтимо прво следеће и прво претходно појављивање на свакој позицији. Онда можемо преко тих низова лако у O(\log\max A_i) по упиту да нађемо одговор.

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

Слично као у трећем задатку видимо да ако је интервал дужине >60 онда је одговор 0. Заиста, јер је сваки број позитиван, сваки има барем по један бит сетован на 1, али онда по Дирихлеовом принципу мора да постоје два броја са заједничким битом, па Ања не може да победи. Ако је интервал дужине до 60 можемо да извршимо проверу у линеарном времену као у 4 подзадатку, па нам треба O(\log^2\max A_i) по упиту.

4

Хормутацијe

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

T = 1 и N \leq 9

У овом подзадатку је довољно изгенерисати све пермутације дужине N+1 и израчунати за сваку од њих израз X. Како би се избегла непотребна константа N у сложености, израз X рачунамо док генеришемо све пермутације. Укупна сложеност је онда \mathcal{O}((N+1)!) или \mathcal{O}((N+1)! \cdot N) у зависности од тога како рачунамо израз X.

N+1 је степен двојке

Приметимо да је могуће да упаримо бројеве x и N-x. Они су комплементарни у бинарном запису - када на неком месту у бинарном запису број x има јединицу, тада је на истом том месту нула у броју N-x, и обрнуто. То значи да ће \oplus сваког пара бити N, а онда и укупна сума N\cdot(N+1). Временска сложеност овог алгоритма је \mathcal{O}(N).

P_i = i за свако i = 0, 1, 2, \ldots, N

Приметимо да уколико имамо решење када важи P_i = i, онда имамо и решење у општем случају - само је потребно да измапирамо који елемент иде коме уместо да их исписујемо редом за i=0,1,2,\ldots,N.

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

Посматрајмо највећи број K мањи од N, за који важи да је K+1 степен двојке. Јасно је да уколико упаримо K и K+1 не губимо ниједан бит применом операције \oplus, јер су комплементарни бројеви у бинарном запису. Исто то важи и за бројеве K-1 и K+2, K-2 и K+3, и тако даље. Након што упаримо број N са његовим парњаком, рекурзивно решавамо за преостале бројеве. Из ове конструкције се лако може показати да је највећа могућа вредност израза X управо једнака N(N+1). У зависности од имплементације мапирања елемента или проналажења броја K, укупна временска сложеност биће \mathcal{O}(N) или \mathcal{O}(N\log N).

5

Монопoл

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

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

У овом подзадатку можемо да симулирамо свих 2^N могућности грађења продавница и потом за сваки град пронађемо најближу продавницу у O(N). Укупна временска сложеност је O(2^N \cdot N^2).

Решење када у сваком граду станује исти број људи

Нека је број становника сваког града g. Посматрајмо две постојеће узастопне продавнице. Нека су оне у градовима i и j и нека између те две продавнице постоји барем један град. Приметимо да са градњом две додатне продавнице, једном у i+1 а другом у j-1, Сања може да преузме муштерије из свих градова из (цикличног) интервала [i+1,j-1]. Дакле, ако градимо две продавнице у (цикличном) интервалу [i+1,j-1], преузећемо све муштерије из тог интервала. Ако градимо само једну, преузећемо пола муштерија, тачније: g \cdot ( \frac{j-i-2}{2} + 1 ) муштерија. Задатак решавамо greedy алгоритмом. У сваком кораку бирамо интервал у коме је оптимално изградити нову продавницу. Приметимо да, ако је то прва продавница из интервала, постављањем ње добијамо g \cdot ( \frac{j-i-2}{2} + 1 ) нових муштерија, док за другу добијамо g \cdot ( \frac{j-i-2}{2} ) нових муштерија. Дакле, довољно је да сортирамо свих 2K добитака опадајуће и одаберемо префикс најмање дужине тако да је његова сума строго већа од половине укупног броја становника. Ово решење ради у временској сложености O(K \log K).

Решење када N \leq 3\,000

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

Приметите да је неопходан услов да би greedy радио тај да прва продавница изграђена у интервалу доноси барем онолико муштерија колико ће донети и друга (Зашто?). Приметимо и да је тај услов овде испуњен, јер ће прва продавница преузети барем половину муштерија из интервала. Наиме, приметите да градњом на позицији i+1 преузимамо целу прву половину интервала, док градњом на позицији j-1 преузимамо целу другу половину интервала. Једна од ове две вредности је барем половина суме целог интервала.

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

За главно решење, довољно је оптимизовати решење претходног подзадатка. Коришћењем префиксних сума, могуће је у O(N) проверити колико ће муштерија из одговарајућег интервала преузери прва продавница изграђена у њему.

6

Линијопoлис

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

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

За сваки подскуп аутобуса проверавамо да ли могу прећи целу трасу. Када се одлучимо за неки такав, пуштамо аутобусе по принципу “један по један”. Сваком је циљ да коришћењем што мање додатних битова стигне до краја. Уколико му је то потребно, битове ће узимати у најкаснијем могућем тренутку. Ако је могуће испунити циљ, он неће узурпирати остале аутобусе. Временска сложеност је O(2^M \cdot M\cdot N).

Решење када N,M\leq 10^4

Надовезујемо се на претходни подзадатак. Уместо разматрања сваког подскупа, можемо уочити то да аутобуси са већом почетном количином битова имају већу шансу да стигну до краја и штеде више битова. Зато их сортирамо по том параметру и пуштамо их редом од највећег ка најмањем. Приметимо да не знамо унапред величину групе аутобуса, већ је одрећујемо накнадно након неуспешне трасе (или након што сви аутобуси стигну до краја). Највећа група ће управо бити последња “тренутна” група коју је описани алгоритам нашао. Временска сложеност је O(M\log M + M\cdot N).

Решење када N,M\leq 10^5

Оптимално је одредити неколико аутобуса са највећом почетном количином битова. Стога вршимо бинарну претрагу по вредности решења. Претпоставимо да смо се одлучили за групу од K аутобуса. Њих паралелно пуштамо да путују заједно кроз сваку станицу. Када доћу до станице употребљавају све доступне битове. Приоритет има аутобус који је “најпразнији”. Промене је могуће симулирати преко min heap (priority queue) структуре.

У њој памтимо количине битова, као и број аутобуса који имају исту. Уколико имамо довољно битова на располагању, десиће се да “спојимо” две најниже вредности, чиме се величина структуре смањује за један. Приликом једне овакве операције, смањивање се може десити произвољан број пута, али додавање се дешава највише двапут (приликом дељења недовољног броја битова са остатком). Како у структуру не можемо одузети више него што смо додали, сложеност провере је O((N+M)\log M.

Због употребе бинарне претраге, укупна временска сложеност је O((N+M)\log^2M).

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

Уместо min heap структуре користимо stack. Провера постаје линеарна, а укупна сложеност је O((N+M)\log M.