[Решења задатака] 2022/2023 СИО - дан 2

Algoritam
1

Опет XOR

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

Решење када је Q \leq 10, X[i] \leq 10 за упите типа 2

У овом подзадатку можемо тестирати све могуће пермутације и проверити да ли су XOR-ови свих префикса растући. Сложеност овог решења O(Q\cdot N!).

Решење када је N, Q \leq 200

За овај подзадатак неопходно је да размотримо детаљније када је низ ксортастичан. За почетак, можемо да приметимо додавање елемента са вредношћу 0 на произвољну позицију не утиче на монотоност префиксних XOR-ева, па те елементе можемо да занемаримо. Додатно ћемо, зарад јасније нотације, у објашњењу овог подзадатка претпоставити да је дат само један упит на који треба одговорити. Разматраћемо следеће грамзиво решење: итеративно градимо пермутацију тако да наредни изабрани елемент проузрокује најмањи могући префиксни XOR, и да тај наредни префиксни XOR још увек буде већи од тренутног. Нека је тренутни префиксни XOR једнак x. Означимо са B_i позицију водећег бита броја A_i. Нека је баш A_i наредни одабрани елмент. Да би наредни XOR био већи, у бинарном запису броја x мора да стоји 0 на позицији B_i. Од свих наредних елемента који задовољавају овај услов, довољно је да одаберемо онај који ће што слабију 0 броја x променити у 1. Једна од стратегија која резултује у оваквом начину бирања елемената је управо одабир елемента који ће што мање да повећа префиксни XOR. На интуитивном нивоу, можемо схватити да овим избором што мање већих позиција на којима су 0 мењамо у 1. Ова стратегија ће увек произвести низ растућих префиксних XOR-ева кад год је низ ксортастичан. Претпоставимо да постоји решење у којем на позицији j у пермутацији није одабран елемент којим се најслабија 0 трансформише у 1 и означимо ту позицију на којој је најслабија 0 са p. Посматрајмо у том решењу прву позицију k > j у пермутацији након тренутне на којој се налази елемент A_l, такав да је B_l = p. Тада можемо да модификујемо пермутацију тако што на позицију j поставимо A_l, а све остале елементе померимо за једно место десно. Након тога, потребно је још да разрешимо проблеме који су могли настати са елементима A_m који су у пермутацији били између j и k и таквим да B_m < p. Након овог техничког детаља којег остављамо читаоцу, добија се пермутација која има неопадајући низ префиксних XOR-ева, а елемент A_l на позицији j. Сложеност овог решења је O(Q\cdot N^2).

Решење када N, Q \leq 5000

У претходном подзадатку смо приметили да је довољно одабрати елемент који што слабију 0 тренутног префиксног XOR-а трансформише у 1. Довољно је да елементе чувамо према њиховом најјачем биту и да итерацијом кроз све позиције на којима су 0 (почевши од најслабије) у бинарном запису тренутног префиксног XOR-а одаберемо произвољан елемент који има 1 као најјачи бит на тој позицији. Сложеност овог решења је O(Q\cdot N \cdot \log_2 \max_i A_i).

Решење када A[i] < 64.

Приметимо да су у овом случају и префиксни XOR-еви до 64. Уколико низ из упита има више од 64 позитивне вредност, одговор је false. У супротном можемо да применимо решење из претходног описаног подзадатка. Сложеност овог решења је O(Q\cdot \max_i A_i \cdot \log_2 \max_i A_i).

Решење када T[i] = 2

За овај подзадатак је неопходно да даље оптимизујемо проверу услова из грамзивог решења. Приметили смо да је било довољно бирати произвољан број који има највећи бит постављен на позицији што слабије 0 из тренутног префиксног XOR-а. Сада је потребно да видимо када ћемо успети да одаберемо све такве бројеве. Одабиром тог броја се 0 на тој позицији променила у 1 у наредним префиксним XOR-евима. Да би опет одабрали број који има 1 на тој позицији, потребно је да се поново у префиксном XOR-у нађе 0. Дакле, за свако (осим последњег) постављање тог бита на 1 у актуелном префиксном XOR-у, потребно је да га касније ресетујемо, постављањем на 0. Означимо са p_i број елемената у којима је бит на позицији i најјачи, а са q_i број елемената у којима је тај бит постављен, али не као најјачи. Потребан и довољан услов је да q_i \geq p_i + 1. Вредности p_i и q_i у неком поднизу можемо пронаћи коришћењем префиксних сума. Сложеност овог решења је O(Q \cdot \log_2 \max_i A_i).

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

За главно решење би било неопходно и да вршимо ажурирање тих префиксних сума. Ово захтева да користимо фенвиково стабло (тј. bit). У фенвиковом стаблу за свако i памтимо и ажурирамо колико елемената у одговарајућем интервалу има 1 као најјачи бит на позицији i, а колико њих има 1, али не као најјачи бит. Сложеност овог решења је O(Q \cdot \log_2 \max_i A_i \cdot \log_2 N).

2

Мајнкрафт вООда

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

Корени у коровима

Чак иако је инспирација за задатак заиста дошла из начина како се пропагирају тзв. source block-ови у игрици Мајнкрафт, поједини ученици могли су препознати везу између овог задатка и такмичарског задатка из фолклора: Дата је табла 10\times10 и 9 поља су обрасла коровом. Ако је поље суседно два поља обрасла коровом онда и оно постане обрасло коровом. Да ли је могуће да цела табла буде обрасла коровом? У овом задатку је одговор НЕ, а разлог зашто је одговор НЕ може нам послужити као добра водиља за решавање оваквог задатка.

Наиме обим фигуре на ком је обрасла коров никад не расте, може само да се смањи. Ако се појави поље које је суседно 3 или чак 4 корова, онда нам се обим смањује. Како је на почетку обим највише 36, а на крају треба бити 40, одговор на питање у задатку је негативан.

Главна хеуристика коју можемо одмах понети одавде је да никад (или барем да се трудимо да избегнемо) не поплавимо поље које је суседно већ неком поплављеном пољу

Анализа примера

Први пример је мали и може се урадити мање више ручно. Оцена обима из првог дела нам даје да је 27 оптималан одговор.

Други пример је већи али му је свака позевазана компонента правоугаоник. За правоугаонике се проблем може решити тачно, и да се докаже тачност оценом горе.

Трећи пример је мали, али је вероватно тешко решити ручно осим ако се уложи јако пуно времена, већ је реалније да га такмичар програмом направи некако и онда ручно доради ако треба. И овде је нађена оцена оптимална.

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

Примери 5-8 су мало дивљији, и оцена која је дата у првој секцији није толико близу конструкција која је нашла комисија. Примери 5 и 7 су цртани руком, док су 6 и 8 рандом шум, са различитим густинама. Пример 8 је огроман, тако да било шта мало спорије може јако дуго да се извршава. Са њим морамо бити посебно пажљиви

Ауторско решење 1 (86 поена, решава 4. пример)

Сваки пут кад поставимо нову воду лако можемо да симулирамо како се вода даље креће помоћу неког алгоритма налик flood-fill алгоритма. Прво поставимо воду у поља која имају макс једног проходног суседа. Даље сваком поље доделимо неку тежину са којом га треба изабрати. Ако је већ суседан неком поплављеном пољу, штетићемо обиму, тако да му на тежину додајемо -10000. За свако суседно поље које ће постати поплављено ако додамо воде на то поље додамо 1000. Боље је стављати у ћошкове него на отворено емпиријки, па додамо на тежину 100\cdot(4-\deg). Најзад (и ово се испоставља као кључно за налажења решења у приемру 4) додамо малу рандом тежину, до 10 на пример. У сваком тренутку бирамо поље са највећом тежину и њега поплавимо и испропагирамо све. За свако плављење морамо да ажурирамо тежине 12 поља који су на дистанци највише 2 од поплављеног поља, па цео алгоритам ради јако брзо. На пример, осми пример решава у року од једног минута.

Ауторско решење 2 (98 поена, решава све осим 4-ог примера)

Анлогно претходном решенју можемо прво поставити воду у она поља која имају тачно једног слободног суседа а затим симулирати додавање нових блокова применом неког алгоритма за обилазак графа. Кључна разлика овог решења у односу на претходно је што за наредно поплављено поље бирамо оно поље које ће поплавити највећи број поља уколико на њега поставимо блок са водом. За проналажење таквог поља неопходно је симулирати поплаву за сваког кандидата који може поплавити више од једног поља, то јест има бар једног суседа који је суседан са тачно једним поплављеним пољем. Приметимо да је сложеност једне итерације ограничена одозго са бројем кандидата у тој итерацији пута број поплављених поља након те итерације. На основу тога можемо закључити да сложеност овог решења није већа од О(N^2M^2). Међутим у приложеним примерима је број кандидата у свакој итерацији значајно мањи од NM па је и сложеност овог решења значајно мања и може се применити на примерима од 1 до 7. За решење примера 8 у временском периоду прикладном за дужину трајања такмичења неопходно је изделити целу таблу на мање табле димензија 300x300 и решити их засебно а затим спојити у једно решење. Да бисмо освојили последњих пар поена на овом задатку потребно је приметити да решење зависи од поља које изаберемо између оних поља са једнаким резултатом симулације. Како бисмо додатно побољшали скор могуће је применити исти алгоритам на разлиците изометријске трансформације улаза и изабрати најбоље решење.

3

Парови

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

Решење кад M \leq 18

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

Решење кад M = K, N \leq 50

Уочимо да ће тежина сваке гране бити 1. Дакле, МСТ је свако разапињујуће стабло, а како је и број чворова мањи, можемо да израчунамо решење за сваки пар на тзв. похлепан начин.
Овде је потребно урадити анализу случајева, пребројимо све чворове са директним везама до она два које посматрамо, одузимајући оне који су заједнички (с тим да се с једним
могу оба повезати уколико не постоји грана између њих).
Сложеност ће бити O(N^2(N+M)).

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

Можемо поново решавати за свака два чвора, с тим што пуштамо симулацију налажења МСТ са оптималним бирањем грана тако да се максимизују оне које укључују неки од два одабрана чвора.
Сложеност је у овом случају O(N^2 М\log{M}).

Решење кад K \leq 6

За ово решење потребно је прећи на другачији начин пребројавања (који се користи и у целон решењу) - групишемо гране са једнаким тежинама (кажемо да је чвор у групи ако
постоји грана у групи која га садржи) и бројимо колико пута гране
из дате групе “фигуришу” у коначном збиру (дакле бар један од селектованих чворова је неки из групе).
Пошто Крускалов алгоритам додаје гране у сортираном редоследу, можемо рачунати да када посматрамо групу тежине W су чворови већ повезани
у компоненте које формирају гране тежина испод W. Да би се формирао МСТ свакако се у њега додаје неки подскуп нових грана, а како је број K мали,
можемо ручно пробати сваки подскуп и видети колико гране доприносе збиру (за свака два чвора која се појављују у групи као крајеви веза). Како има \frac{M}{K} група,
а O(K) и чворова и грана у групи, сложеност је O(2^K MK).

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

Могуће је извршити пребројавање појављивања грана у макс степенинма чворова из групе и брже, тако да не постоји додатни фактор осим квадратног по K. Посматрајмо
везе чворова из групе са већ формираним компонентама.
Фиксирамо 2 чвора у групи и за њих додајемо број компоненти с којима су повезани, одузимајући број с којим су оба повезана, са обраћањем пажње на специјалне
случајеве (неки од два чвора повезан је са компонентом од овог другог, у истој су компоненти, или постоји директна веза између два селектована чвора).
Овде се ради нешто донекле слично као у другом подзадатку, с тим што је (условно речено) тада једина група био скуп свих чворова, сада треба додати и допринос грана у
тренутној групи на збир степена кад селектован пар укључује један чвор који се не појављује у групи, мада ово се рачуна само као број компоненти с којим је повезан
онај чвор који јесте у групи (наравно онолико пута колико има чворова ван групе). Након овог процеса, ажурирамо компоненте и прелазимо на наредну групу.
Укупна сложеност је (истим резоном као и пре) O(MK).