[Rešenja zadataka] 2021/2022 SIO - dan 1

Algoritam
1

Лаж

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

Решење када q = 2000

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

Решење када q = 1000

Можемо да сазнамо да ли је неко лажов или истинољубац са само једним питањем. Ако особа x питамо за скуп \{x, y\}, где је y било која друга особа, сазнаћемо да ли је y лажов или истинољубац (само уколико каже да у њему има непарно лажова, онда је особа y лажов). Ово знамо, јер ако особа x говори истину, онда одговор зависи само од тога да ли је y лажов. Ако лаже, и ако су обојица лажови, x ће још увек рећи да је непарно лажова. У супротном, рећи ће да има непарно лажова.

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

Решење када q = 30 и постоји тачно један лажов

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

Ако је истинољубац, онда је лажов нека од особа на интервалу [2, N]. Поделимо овај интервал на пола. Лажов се мора налазити у једној од те две половине. Питајмо особу 1 да ли је лажов у првој половини. Уколико јесте, даље разматрамо само њу, у супротном, разматрамо само другу половину.

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

Решење када q = 30 и постоји непарно лажова

Слично претходном подзадатку, прво налазимо информацију о особи 1. Након тога, поново радимо бинарну претрагу на интервалу [2, N]. Овај пут, уместо да одржавамо само једног лажова, желимо да интервал који посматрамо увек има непаран број лажова. Када поделимо интервал који има непаран број лажова на две половине, једна половина имаће паран број лажова, а друга непаран. Претрагу настављамо у оној половини која има непаран број. Тако радимо док не дођемо до једног лажова.

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

Последњи подзадатак решавамо као претходни, само што је прво потребно да нађемо неки подскуп људи у којем има непарно лажова. То можемо урадити насумичним (рандомизираним) приступом.

Сваки елемент убацујемо у наш подскуп са вероватноћом 50\%. Самим тим, вероватноћа да ће тај подскуп имати непарно лажова је такође 50\%. Уколико подскуп који смо добили има парно много лажова, онда конструишемо нови подскуп, док не добијемо неки који нам одговара.

Вероватноћа да ће нам за то требати преко 19 покушаја је јако мала, \frac{1}{2^{19}}, па је можемо занемарити. Остала питања можемо искористити на други део решења, где опет радимо нешто налик на бинарну претрагу, само овај пут делимо скуп на два, уместо интервал.

2

ТСМ

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

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

Прво нађимо неко минимално разапињуће стабло графа који добијемо када као гране додамо сваки метро план (у даљем тексту МСТ). За то можемо користити неки познати алгоритам, попут Крускаловог или Примовог. Након тога, за сваки могући поредак проверимо да ли нам даје МСТ и од таквих узимамо лексикографски највећи.

Временска сложеност је O(M! \cdot M \cdot \alpha(M)), а меморијска O(M).

Решење када се сваки план линије налази у највише једном циклусу

Овакав граф се зове кактус граф. Можемо лако закључити да је у кактус графу, да бисмо добили МСТ, потребно да у сваком циклусу у графу избацимо најскупљу грану. Што значи, да се најскупља грана мора наћи у поретку након свих других грана у том циклусу.

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

Временска сложеност је O(MlogN), а меморијска O(M).

Решење када је МСТ пут и N,M \leq 5000

Пошто су цене свих грана различите, МСТ је јединствен. Дакле, нађимо МСТ и знамо да ће он бити пут. Поставимо његове гране редом у низ тако да је један крај пута индексиран са 1, а други са N-1.

Сада, за сваку грану која није у МСТ, рецимо да повезује станице x и y, мора да важи да се налази у пермутацији након свих грана на путу између x и y у МСТ. Ако то не важи, додали бисмо скупљу грану, а касније не бисмо могли да додамо јефтинију, што значи да не бисмо добили МСТ. Тај пут одговара неком интервалу у нашем низу.

Сада можемо конструисати нови, усмерени, граф, где су планиране метро линије чворови, а грана од чвора u до чвора v постоји искључиво ако линија u мора да се нађе пре линије v у крајњем поретку. Ове гране можемо лако наћи проласком кроз низ за сваку грану ван МСТ.

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

Временска сложеност: O(M^2\log M), а меморијски O(M^2).

Решење када је МСТ пут

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

Зато, уместо да конструишемо све гране усмереног графа, довољно је конструисати грану између најјефтиније гране на одређеном интервалу и гране коју посматрамо. То је довољно ограничава, јер знамо да по транзитивности онда неће се јавити пре ниједне гране на путу.

Сада можемо радити тополошко сортирање као у претходном подзадатку, само што овај пут имамо много мање грана. Такође, можемо приметити да је могуће и радити лексикографско спајање K низова као у другом задатку.

Временска сложеност је O(MlogN), а меморијска O(M).

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

Слично подзадатку у коме је МСТ пут, само како бисмо нашли гране усмереног графа, потребно је да прођемо кроз пут на МСТ, уместо кроз интервал низа. Ово можемо урадити тако што коренујемо стабло у неком чвору, па памтимо родитеља за сваки чвор.

Временска сложеност: O(M^2\log M), а меморијски O(M^2).

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

Слично подзадатку у коме је МСТ пут, само како бисмо нашли гране усмереног графа, потребно је да ефикасно нађемо најмању грану на путу МСТ, уместо на интервалу низа. Ово можемо урадити преко технике бинарног подизања (binary lifting). Коренујемо МСТ у произвољном чвору, нађемо претка сваког чвора (за претка корена ставимо самог себе). Након тога, за сваки чвор и за свако l od 0 do \log N памтимо најмању грану ако се 2^l грана пењемо на горе. То нам може помоћи да у O(\log N) нађемо минимум на било ком путу (слично алгоритму тражења минималног заједничког претка).

Временска сложеност је O(MlogN), а меморијска O(M).

3

Игрица

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

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

На упите за овај подзадатак могуће је одговорити директним израчунавањем тражене суме.

Решење када је S_i \leq 10

Упите можемо да решавамо из два дела. Првих S_i чланова суме можемо да урачунамо директно по формули као у прошлом подзадатку, а за остале чланове знамо да је m > S_i па је S_i mod m = S_i, те је довољно наћи њихову суму и помножити је са S_i. За брзе упите о суми на поднизу можемо да користимо структуру података бинарно индексирано стабло или сегментно стабло. Ове структуре подржавају измену чланова низа, тако да лако можемо да подржимо и ажурирања игрице. Временска сложеност је O((N+Q)logN).

Решење када је A_i = 1 и T_i = 1

У овом подзадатку упити се своде на израчунавање суме \Sigma_{m=1}^{R_i - L_i + 1} (S_i mod m). Приметимо да је S_i mod m = S_i - \lfloor \frac{S_i}{m} \rfloor \cdot m, па можемо суму да раставимо по минусу. Први део је S_i \cdot (R_i - L_i + 1) и од њега одузимамо други део који рачунамо из више делова. Првих \sqrt{S_i} чланова суме рачунамо директно по формули. За остале чланове постоји највише \sqrt{S_i} различитих вредности за \lfloor \frac{S_i}{m} \rfloor и можемо да одредимо леву и десну границу за сваку вредност тако да можемо да израчунамо \Sigma_{m=l}^{r} \lfloor \frac{S_i}{m} \rfloor \cdot m као \lfloor \frac{S_i}{m} \rfloor \Sigma_{m=l}^{r} m применом формуле за збир узастопних природних бројева или прекалкулисањем ових сума. Временска сложеност је O(Q \sqrt{S}).

Решење када је T_i = 1

Упите решавамо на сличан начин као у претходном подзадатку, али су формуле мало компликованије. Прекалкулисаћемо префиксне суме низа A_i и низа A_i \cdot i. Проналазимо групе као у прошлом подзадатку и уместо збира узастопних целих бројева, користићемо прекалкулисане вредности. \Sigma_{m=l}^{r} A_{L_i + m - 1} \cdot \lfloor \frac{S_i}{m} \rfloor \cdot m се своди на израчунавање \Sigma_{m=l}^{r} A_{L_i + m - 1} \cdot m пошто је вредност \lfloor \frac{S_i}{m} \rfloor фиксна за сваку групу. Израчунавање поменуте суме могуће је преко сума подниза низа A_i и А_i \cdot i. временска сложеност је O(Q \sqrt(S))

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

За цело решење потребно је још подржати операције измене низа. Довољно је уместо прекалкулисаних префиксних сума користити бинарно индексирано стабло за одржавање сума на поднизу. Временска сложеност овог решења је O(Q \sqrt{S} log N)