[Rešenja zadataka] Okružno 2019


#1

Пирамида

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

Лако се закључује да се проблем своди на утврђивање да ли пар узастопних стрингова могу бити узастопни редови пирамиде. Провера да ли два стринга могу бити узастопни редови се своди на утврђивање броја појављивања појединих слова енглеског алфабета (над којим су стрингови написани).
Ако са n_x[A], n_x[B], n_x[C], ..., n_x[Z] означимо број појављивања, редом, слова A, B, C, ..., Z у стрингу x, а са n_y[A], n_y[B], n_y[C], ..., n_y[Z] означимо број појављивања, редом, слова A, B, C, ..., Z у стрингу y, онда стрингови x и y могу бити узастопни редови пирамиде ако и само ако важи

|n_y[A]-n_x[A]| + |n_y[B]-n_x[B]| + |n_y[C]-n_x[C]+...+|n_y[Z]-n_x[Z]| = 1.

Смернице за алгоритам

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


#2

Фотографисање

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

Анализа

Практично је у задатку дат сортиран низ од N природних бројева и захтева се промена највише једног члана тог низа тако да се минимизује највећа разлика чланова који су суседни не по индексима, већ по вредностима.

Да би се то постигло, потребно у једном проласку кроз низ одредити највећу разлику између два суседна члана. Та највећа разлика може бити јединствена или нејединствена, а може се појављивати на рубовима (почетак и/или крај) низа и/или у средини низа.

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

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

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

Смернице за алгоритам

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


#3

Групе

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

Приметимо да ако збир свих елемената низа није дељив бројм L, онда не постоји решење, јер се низ не може поделити у L група који имају једнаке збирове. Значи у том случају је решење нула (0).
Ако је S збир свих елемената низа S и ако је S дељиво бројем L, онда збир сваке од група мора бити S/L. Нека је L' број група за које важи да је збир различит од S/L. Тада важи следеће:
Ако L'\not\in\{0,2\}, онда не постоји нити једна размена којом би се изједначио збир елемената у свим групама, па је решење нула.
Ако је L'=0, онда све групе већ имају једнак збир, па због тога размена било ког пара елемената из исте групе или било ког пара елемената који имају исту вредност доводи до низа који задовољава услов (да све групе имају исти збир). Број размена у којима се размењују елементи из исте групе је

L \times \frac{N/L(N/L-1)}{2}.

Број размена у којима се размењују једнаки елементи се добија тако што се преброји број појављивања сваке од вредности. Ако су V_1, V_2, V_3, ..., V_K различите вредности који се појављују у низу a, а n_{V_1}, n_{V_2}, n_{V_3}, ..., n_{V_K}, бројеви појављивања тих вредности онда је број размена елемената који имају исту вредност једнак:

\frac{n_{V_1}(n_{V_1}-1)}{2} + \frac{n_{V_2}(n_{V_2}-1)}{2} + ... + \frac{n_{V_K}(n_{V_K}-1)}{2}.

Међутим, у овом изразу фигуришу и размене једнаких који се налазе у истој групи. Због тога те размене треба одузети, а то ћемо извести тако што ћемо исти поступак пребрајања вредности извести за сваку групу и израчунати вредност одговарајућег израза (еквивалентног горњем).
Ако је L'=2, онда постоје две групе у којима се збир не поклапа са просечном вредношћу (тј. са S/L). У једној групи је збир већи од просека, а у другој је мањи од просека (при чему су апсолутне разлике тих сума и просека једнаке). Означимо са d апсолутну разлику суме једне од тих група и просека S/L. Тада се може разменити било који пар елемената из те две групе за који важи да је разлика елемента који се налази групи са већим збиром и елемента који се налази у групи у којој је мањи збир једнак d. Значи, потребно је пребројати број појављивања појединих вредности у две групе, након тога измножити одговарајуће бројеве појављивања и производе сабрати.

Смернице за алгоритам

Будући да су вредности елемента мање од или једнаке 10^6, може се формирати низ у коме ће се рачунати бројеви појављивања појединих вредности. Због тога бројеве појављивања појединих вредности можемо одредити једним пролазом кроз низ. Поред тога потребан је један пролаз кроз низ како би се одредили збирови елемената по групама. Али како се у оба случаја ради о једном пролазу кроз низ, алгоритам има линеарну сложеност.


#4

Изгубљени низ

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

Пре почетка кључно је увидети да пошто за свако x важи x\ \text{or}\ x = x, а како низ B између осталих садржи и резултате операције или примењене над истим чланом изворног низа, закључује се да је тражени низ A заправо подскуп задатог низа. Намеће се наивно решење да се формирају сви подскупови низа B који садрже тачно N чланова, а затим испита који тачно од њих даје задати низ B, међутим, ово решење пати од изузетно високе временске сложености.

Није тешко даље закључити да резултат или операције над битовима два природна броја (операнди) никада није мањи, већ искључиво број већи или једнак већем операнду. Из претходног лако се изводи да су два по вредности најмања члана датог низа B, означимо их са B_{S1} и B_{S2}, сигурно и чланови изворног низа A, односно A_1 = B_{S1} и A_2 = B_{S2}. Следећи члан изворног низа A_3 биће или трећи по вредности члан низа B, то јест B_{S3}, или пак четврти, B_{S4}, уколико је A_1\ \text{or}\ A_2 = B_{S3}. Понављањем овог поступка, може се доћи до свих чланова изворног низа, на много ефикаснији начин од претходно поменутог.

Наиме, у сваком кораку алгоритма из низа B треба елиминисати или на неки начин означити све чланове које је могуће формирати помоћу чланова низа A који су већ одређени, а затим у низ A додати први следећи по вредности члан задатог низа.

Смернице за алгоритам

По учитавању чланова низа B најпре је задати низ неопходно сортирати у неопадајућем редоследу користећи се неким ефикасним алгоритмом. Пошто низ B не садржи јединствене вредности, већ се једна вредност може понављати више пута, у једном проласку кроз добијени сортиран низ означити индексе када се свака вредност појављује први пут. Затим, у главној петљи, пролазити кроз сортиран задати низ B и додавати чланове у низ A, али само под условом да тај члан већ није могуће добити неком комбинацијом чланова који су већ додати у низ A. Да би се ово извело на ефикасан начин, приликом сваког новог додавања у низ A проверити и означити све индексе чланова низа B које је могуће формирати упаривањем последње додатог члана са свим претходним који се већ налазе у низу A. Другим речима могуће је користећи се већ означеним индексима појединих вредности и њиховим инкрементирањем знати до ког индекса низа B је изводљиво генерисати све чланове, а затим додати први следећи када се до њега дође. Овај процес наставити док се не прође кроз читав задати низ. Како низ B садржи \frac{N(N+1)}{2} чланова, главна петља има заправо квадратну сложеност, односно \mathcal{O}(N^2). Међутим, како је задати низ претходно сортиран, то ће ова операција доминирати, те је заправо \mathcal{O}(N^2\log N) укупна временска сложеност овог алгоритма.


#5

Слепи бројеви

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

Приметимо да, у свим потпроблемима, можемо на почетку издвојити све слепе бројеве - проверу да ли је неки број слеп можемо урадити у сложености O(\log B) , тако да можемо издвојити све такве у \mathcal{O}((B - A)\log B) , што је довољно брзо.

Потпроблем 1

Приметимо да можемо да пробамо све парове слепих бројева (има их највише (B - A) ^ 2 (груба граница)), и видети који од тих парова је клеп, провером да ли K дели њихов производ, у сложености \mathcal{О}((B - A) ^ 2)

Потпроблем 2

Заправо, нас само интересују остаци свих слепих бројева при дељењу са K - само од остатака при дељењу два броја неким бројем зависи и остатак производа. Дакле, можемо имати бројач колико постоји слепих бројева са сваким остатком, и у \mathcal{O}(K^2) израчунати колико има клепих парова.

Потпроблеми 3 и 4

Нека је z број слепих бројева дељивих са К . Посматрајмо све остале слепе бројеве. Уколико посматрамо неки број x , нека је t = gcd(x, k) . Пар (x, y) ће бити клеп уколико важи \frac{k}{t} \mid y - дакле, када тражимо све бројеве који формирају клеп пар са бројем x , треба нам број бројева дељивих са неким бројем. То можемо лако урадити проласком кроз низ слепих бројева (тј. њихових остатака при дељењу са K ) - када наиђемо на број x, додамо \mathrm{count}[K / gcd(x, K)] на решење, и увећамо \mathrm{count} сваког делиоца броја x за 1. Ово решење ради у сложености \mathcal{О}(\mathrm{brSlepih} \cdot \sqrt{K}) , што је сигурно довољно брзо, јер не постоји улаз за који је број слепих бројева већи од 50000. На ово добијено решење треба додати z \choose 2 , као и z \cdot (\mathrm{brSlepih} - z) .


#6

Жетони

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

Доделимо жетону на позицији (x, y) вредност 2^{2-x-y}. Приметимо да се након једног потеза при нормалној игри збир вредности свих жетона неће променити, што значи да је потребан (али не и довољан) услов да Буба каже “Стоп!” да збир вредности свих жетона буде тачно 1. Пошто се додавањем новог жетона у debug моду ова вредност повећава, ово значи да ће у највише једном тренутку збир вредности свих жетона на табли бити једнак 1. Ако вредност табле “прескочи” 1 или никад не достигне 1, знамо да нема решења.

У тренутку када вредност достигне 1, покушаћемо да реконструишемо низ потеза који таблу доводи у то стање. Ово ћемо радити грабљивим алгоритмом одназад. Посматрајмо све жетоне у последњој непразној дијагонали (под дијагоналом подразумевамо скуп поља са константном вредношћу x+y). Решење постоји ако и само ако се они могу упарити тако да сваки пар чине два жетона који се налазе на пољима која имају заједничко теме.

Ово упаривање се може урадити на јединствен начин, ако је уопште могуће, поново грабљивим алгоритмом редом од жетона са најмањом x-координатом. Ако смо успешно упарили све жетоне из ове дијагонале, за сваки пар упарених жетона на позицијама (x, y+1), (x+1, y) креирамо један жетон на позицији (x, y). Овај поступак понављамо све док не дођемо до прве дијагонале или не дођемо у ситуацију да не можемо да упаримо жетоне.

Ако дођемо до стања где је само један жетон у првој дијагонали, решење штампамо као обрнути низ жетона које смо креирали током обиласка дијагонала.

Смернице за алгоритам

Тренутак када збир вредности свих жетона постане једнак 1 можемо пронаћи тако што одржавамо бинарни запис разломка који садржи тренутни збир вредности. Када додајемо жетон на позицију (x,y), у помоћном низу c треба повећати број c_{x+y-2} за 1. Ако његова вредност постане 2, онда је постављамо на 0 и исти поступак понављамо за цифру на позицији x+y-3, и тако даље, до заустављања.

Амортизованом анализом сложености се може показати да овај поступак има временску сложеност O(N). У решењу доминира временска сложеност за сортирање сваке дијагонале, пошто ће све оне укупно садржати O(N) жетона временска сложеност је O(N \log N) док је меморијска сложеност O(N).


#7

Da li mozda kojim slucajem znate zasto u necijem kodu 18. i 20. test primer ne rade za B3? n=2e5 pa ne mogu da vidim sam…


#8

Ako se ne varam, nisi lepo pokrio slučaj kada su sume u grupama jednake.


#9

Ovaj zadatak moze da se resi u O(N^2+2^20) counting sortom?


#10

Moze, cak je i kod veoma jednostavan