[Rešenja zadataka] SIO 2019


#1

Комбиновање

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

Комисијско решење састоји се од следећег.

Сa обзиром да почетна конфигурација матрице може бити циљано постављена у неповољан положај колоне, и редови матрице се измешају на следећи начин. За свако i случајно се бирају два броја j и k и затим се i-та колона замени са j-том а i-ти ред са k-тим редом.

Затим прође се кроз све парове (i, j) и уколико би се заменом i-те и j-те колоне резултат побољшао колоне се замене, затим уколико би се заменом i-тог и j-тог реда резултат побољшао редови се замене.

Претходно проlazeње кроз све парове понови се 20 пута.

Након тога изаберу се 4 случајна броја a, b, c и d и уколико би се заменом a-те и b-те колоне а затим заменом c-тог и d-тог реда побољшао резултат поменуте колоне и редови се замене.

Последњи описан део поновимо 20\cdot n^2 пута.


#2

Звезда

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

Анализа

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

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

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

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

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

Решимо сада проблем динамичким програмирањем, дефинишимо:

  • d[i][j][0] - број начина да се на цикличном сегменту [i, j) (укључује i, не укључује j) нађе тачка s боје 0 и да се тачке сегмената [i,s) и [s + 1, j) споје у грбове (сваки грб (односно његова темена) да се налазе тачно у једном од сегмената, у [i,s) или у [s + 1, j))

  • d[i][j][1] - аналогно само за s боје 1

  • d[i][j][2] - број начина да се тачке сегмената [i, j) споје у грбове.

Пре него што почнемо приметимо да d[i][j][0] и d[i][j][1] могу бити не нула само уколико је дужина (број тачака) у цикличном интервалу [i, j) облика 4k + 1, док d[i][j][2] може бити не нула само уколико је уджина тог интервала облика 4k.

Наши почетни услови су

  • За свако 1 \leq i \leq n, d[i][i][2] = 1
  • За свако 1 \leq i \leq n, d[i][i + 1][a[i]] = 1
  • За сваке i, j, k, d[i][j][k] = 0 сем за горе поменуте

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

Сада кадa рачунамо d[i][j][0] јасно је да за сваки s из интервала [i, j) такав да A[s] = 0, требамо d[i][j][0] да увећамо за d[i][s][2] * d[s + 1][j][2], по дефиницији.

Аналогно за d[i][j][1].

У случају рачунања d[i][j][2] знамо да је тачка i у грбу са још три тачке назовимо ону која се у смислу цикличног поретка налази између друге две, односно “средњу” тачку, s. Уколико је она исте боје као тачка i број начина да се тачке интервала [i, j) споје у грбове на такав начин је по дефиницији d[i + 1][s][0] * d[s + 1][j][1] + d[i + 1][s][1] * d[s + 1][j][0] (тачке које су неспарене у попуњавању мањих сегмената сада узимамо у исти грб са тачкама i и s, и водимо рачуна о томе да су различитих боја), док аналогно уколико су i и s истих боја број начина је d[i + 1][s][0] * d[s + 1][j][0] + d[i + 1][s][1] * d[s + 1][j][1].

Све претходно речено даје нам укупну сложеност О(n^3).

Додатак

Решење се може додатно убрзати уколико се примети да ао на сегменту [i, j) има a тачака боје 0 и b тачака боје 1, систем једначина 3A + B = a, A + 3B = b, мора имати ненегативна решења (уколико посматрамо да је A број грбова којима је теме обојено бојом 1, а B број грбова којима је теме обојено бојом 0 једначине директно следе). Овиме и аналогним условом за случајеве када рачунамо сегмент ком остављамо једну тачку негруписану можемо избећи беспотребне проласке кроз унутрашњу петљу алгоритма.

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


#3

Камера

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

Код прва два подзадатка било је довољно имплементирати било који ефикасан алгоритам за налажење минималног покривајућег стабла - у наставку MST од minimum spanning tree, такође, са MSF ћемо означити минималну покривајућу шуму графа, тачније, то је подграф који је шума минималне тежине а има исте повезане компоненте, при чему је за први подзадатак био довољан било који тачан brute force приступ.

За 3. и 4. подзадатак могла је да се користи било која 2D структура података која ефикасно одговара на упите “који је минимум у подматрици”. За 3. подзадатак (N=2) довољно је само наћи грану минималне тежине. За 4. подзадатак (N=3) потребно је наћи минималну тежину гране међу свим гранама које спајају чворове 1,2, аналогно за чворове 2,3 и 1,3. Уколико се међу овим гранама јавља једна или ниједна, онда стабло не постоји. Ако се јављају тачно две онда управо оне чине стабло, а ако се јаве три онда се стабло добија одбацивањем најтеже од те три гране. Најлакша за имплементацију (а ипак довољно брза) таква структура би била следећа асиметрична табела: За сваки подсегмент сваког реда израчунамо минимални елемент, ово радимо у сложености O(R \times C^2), сваки упит решавамо у O(R) пролазом кроз одговарајуће редове.

Да би се задатак решио за 100 поена кључна је следећа опсервација везана за појам MST-а:

Нека је A скуп грана графа са чворовима V = \{1, \ldots, N\}, и нека је T(A) минимална покривајућа шума тог графа (уколико их има више, онда било која). Тада важи следеће: T(T(A) \cup T(B)) је минимална покривајућа шума за скуп грана A \cup B. Ово се може доказати анализом рада Kruskal-овог алгоритма за налажење MST-а. У преводу, ово значи да, ако хоћемо да израчунамо MSF за неки, потенцијално велики скуп грана, ми га можемо поделити на два мања скупа, који се чак могу и преклапати (потребно је само да је њихова унија једнака почетном скупу), затим наћи њихов MSF а затим заједнички MSF на сада већ знатно мањем скупу грана.

Ово нас усмерава ка томе да направимо дводимензиону sparse table структуру података, где ћемо за свако i,j,k (1 \leq i \leq R, 1 \leq j \leq C, 0 \leq k \leq \log_2(\min(R,C)) чувати скуп грана који учествује у MSF-у скупа грана које се налазе у квадратној подматрици чије је горње лево теме поље i,j а страница тог квадрата је 2^k. Јасно је да се свако поље ове табеле може израчунати као унија четири поља где су странице квадрата дупло мање. Ако са \alpha(N) означимо сложеност једне операције помоћне структуре података за дисјунктне скупове (DSU, Disjoint Set Union) а која је за овако мале вредности N практично константна, тада се цела ова табела може конструисати у сложености O(RC\log(\min(R,C))N \alpha(N)).

Још једна кључна ствар је та што, услед тога што је количник страница правоугаоника код сваког упита број између \frac23 и \frac32, сваки овакав правоугаоник може да се “покрије” са највише 6 квадрата чија је страница степен двојке, што нам омогућава да решимо сваки упит у сложености O(N \alpha(N)).


#4

Складиште

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

Посматрајмо тренутак доставе једне од кутија. Нека се у складишту тренутно налази n кутија које ће бити извађене у тренуцима T_0, T_1, \dots, T_n, и нека је време вађења оне коју тренутно убацујемо t.

Ако је укупно време потребно да се изваде кутије које су тренутно у складишту R (ако нема даљих достава), након што додамо нову, постоје две могућности:

  • нову кутију ставимо на крај: времена вађења појединачних кутија које су већ у складишту се неће променити. Када нова кутија дође на ред, испред ње ће бити оне за које важи T_i > t, тако да је укупно време R + |i : T_i > t|.
  • нову кутију ставимо на почетак: за кутије које се ваде пре ње (T_i < t), време ће се повећати за 1, а за нову кутију ће време вађења бити 0. Ново укупно време је дакле R + |i : T_i < t|.

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

Да би добили решење чија је временска сложеност \mathcal{O}(N \log{N}), неопходна нам је структура која подржава следеће операције у логаритамском времену:

  • додај x у скуп,
  • избаци x из скупа, и
  • одговори на “колико елемената скупа су мањи од x?”

Једна опција је структура слична set-у, али C++ стандардна библиотека не подржава директно упит који нам је потребан. Пошто су сви елементи мали (максимално 2N), једна алтернатива је сегментно стабло (или Fenwick стабло). Овде, у i-том елементу чувамо 1 ако је i у скупу, и 0 у супротном. Упит се у том случају своди на проналажење збира на интервалу [0, x).


#5

Планине

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

Анализа

Потребно је у квадратној матрици A пронаћи елемент који је строго највећи у својој врсти и строго најмањи у својој колони – назовимо такав елемент (уколико постоји) седло (то је, иначе, стандарни термин). За почетак приметимо да уколико седло постоји, онда је јединствено; заиста, претпоставимо да су A_{i,j} и A_{k,l} седла. Очигледно, i \neq k и j \neq l. Уколико је A_{i,j} \leq A_{k,l}, тада, због дефиниције седла, A_{i,j} > A_{i,l} > A_{k,l} што је контрадикција; за A_{i,j} > A_{k,l} поново добијамо контрадикцију преко A_{i,j} < A_{k,j} < A_{k,l} па је немогуће да постоје два или више седла.

Из претходног разматрања следи: уколико су нам познате вредности нека два поља (нпр. A_{i,j} и A_{k,l}), можемо елиминасти бар једно од њих као потенцијалног кандидата за седло упитом над највише једним додатним пољем (A_{i,l} или A_{k,j}). Дакле, произвољних M потенцијалних кандидата за седло (за које знамо вредности) можемо свести на само 1 уз не више од M-1 питања коритећи овај метод који ћемо једноставно звати Елиминација.

Подзадаци 1 и 2: Овде је K = N^2 па једноставно можемо питати за вредности свих поља и наћи седло у познатој матрици у сложености O(N^3) уколико за свако поље пролазимо целу његову врсту и колону или у сложености O(N^2) уколико прекалкулишемо максимуме по врстама и минимуме по колонама.

Подзадатак 3: Како су вредности из скупа \{1,2,3\}, јасно је да елемент A_{i,j} може бити седло ако и само ако је A_{i,j} = 2, сви остали елементи у његовој врсти су 1 и сви остали елементи у његовој колони су 3. Према томе, уколико упитамо за вредност A_{i,j} и добијемо вредност 1, елиминисали смо целу j-ту колону (тамо не може бити седло), ако добијемо вредност 3 – елиминисали смо целу i-ту врсту, а ако добијемо вредност 2 - елиминисали смо целу i-ту врсту и j-ту колону осим потенцијално баш елемента A_{i,j}. Упите можемо постављати тако да у сваком упиту елиминишемо бар једну врсту или колону па ћемо након највише 2N упита елиминисати све врсте и колоне и остаће нам највише N поља која могу бити потенцијална седла. Сада применимо Елиминацију (највише још N упита) и још највише 2N упита за проверу да ли је преостали елемент заиста седло (може се показати да је за овај метод горња граница за број упита заправо 4N уместо 5N).

Подзадатак 4: Поставимо упите за све елементе са главне дијагонале и пермутујмо врсте и колоне тако да важи A_{1,1} \leq A_{2,2} \leq \ldots \leq A_{N,N} (ово није проблем, довољно је само запамтити те пермутације и за свако наредно Pitaj(i,j) заправо постављати Pitaj(row[i], col[j])). У новодобијеној матрици, ниједан елемент испод главне дијагонале не може бити седло (немогуће да за i > j важи A_{i,j} > A_{i,i} и A_{i,j} < A_{j,j} јер A_{j,j} \leq A_{i,i}) па седло можемо тражити само на главној дијагонали и изнад, питајући за вредности све кандидате (њих \frac{N(N+1)}{2}) и примењујући Елиминацију (показати да нам приликом Елиминације никада неће требати вредности елемената испод главне дијагонале јер можемо користити поредак на њој!). Овај део можемо и једноставније, налазећи седло као у Подзадатку 2 не користећи елементе испод главне дијагонале (показати да ћемо и у случају “полу-матрице” са соритраном дијагоналом добити највише једног кандидата!). Када добијемо јединственог кандидата, довољно је још N-1 упита за проверу јер је највише толико поља из његове врсте и колоне (од њих 2N-1) испод главне дијагонале. Дакле, треба нам \frac{N(N+1)}{2} + N - 1 упита, што се уклапа у ограничења.

Подзадатак 5: У претходном подзадатку, уместо да питамо за сва поља изнад главне дијагонале, можемо нпр. рекурзивно применити логику за горњи-десни квадрат (и опет питати само око половину свих елемената у њему). Прецизније, радимо следеће

  • Уколико је тренутни квадрат димензија 1 \times 1 питамо и вратимо то поље као потенцијалног кандидата; иначе
  • Питамо за све елементе главне дијагонале тренутног квадрата и пермутујемо врсте/колоне тако да важи поредак као у претходном подзадатку
  • Рекурзивно поновимо поступак за горњи-леви, доњи-десни и горњи-десни подквадрат (за прва два поставимо маркер да не морамо питати/сортирати дијагоналу јер је већ сортирана као део оригиналне) и од 3 добијена кандидата Елиминацијом вратимо само један.

Ако је T(N) број позива Pitaj овог алгоритма за квадрат димензије N \times N, није тешко закључити да важи T(1) = 1 и Т(N) = 3T(\lceil \frac{N}{2} \rceil) за N > 1 (како има пуно “преклапања” дијагонала, можемо замислити да заправо не питамо за поља осим ако је квадрат 1 \times 1) па је T(N) = 3^{\log_2 N} = N^{\log_2 3} (поља која питамо образују неку врсту фрактала а имплементација је благо згоднија јер је N степен двојке). За Елиминацију нам у најгорем случају треба још толико упита (а у пракси много мање због преклапања) и рачунајући коначну проверу то је највише 2\cdot N^{\log_2 3} + 2N упита, што се уклапа у ограничења.

Подзадаци 6 и 7: Назовимо скуп поља S (матрице) добрим уколико никоја два поља из S нису у истој врсти или колони и уколико се седло (уколико постоји) целе матрице налази у пресеку врсте у којој је неки елемент из S и колоне у којој је неки елемент из S. Нпр. један добар скуп је D = \{(1,1), (2,2), \ldots, (N,N)\}.

(*) Приметимо да ако је S добар скуп, тада седло не сме бити веће од највећег елемента из S и не сме бити мање од најмањег елемента из S. Заиста, како седло припада некој колони из S, оно је мање или једнако од бар једног елемента из S па и од максимума; слично и за минимум.

Нека је S произвољан добар скуп и нека је (i, j) \in S такво да је A_{i,j} најмања вредност од свих вредности из S a (k, l) \in S такво да је A_{k,l} највећа вредност од свих вредности из S. Од доброг скупа S можемо добити добар скуп са једним елементом мање на следећи начин: питамо за вредност елемента A_{i,l} и разликујемо 3 случаја:

  • A_{i,l} \leq A_{i,j}: Ако је седло у колони l онда је оно мање од A_{i,l} а самим тим и од A_{i,j} тј. од свих елемената скупа S што је немогуће због (*) . Дакле, у колони l нема седла. Са друге стране, у врсти k је једини кандидат за седло А_{k,l} (иначе би седло морало бити веће од свих елемената из S што је немогуће због (*) ) али већ смо закључили да у колони l нема седла па седло није ни у врсти k. Дакле, избацивањем елемента (k, l) из S опет добијамо добар скуп.
  • A_{k,l} \leq A_{i,l}: Аналогним разматрањем као у претходном случају, добијамо да се избацивањем елемента (i, j) из S опет добија добар скуп.
  • A_{i,j} < A_{i,l} < A_{k,l}: Користећи (*) као у претходним случајевима, добијамо да је A_{i,j} једини кандидат за седло у колони j и да је A_{k,l} једини кандидат за седло у врсти k. Међутим, A_{i,j} и A_{k,l} не могу бити седла због, редом, A_{i,j} < A_{i,l} и A_{i,l} < A_{k,l} па следи да седло није ни у врсти k ни у колони j. Ову врсту и колону можемо избацити тако што из скупа S избацимо елементе (i, j) и (k, l) али убацимо елемент (i, l) (јер морамо задржати i-ту врсту и l-ту колону). Новодобијени скуп је добар и садржи елемент мање.

Када добијемо добар скуп са једним елементом, он је једини кандидат за седло. Дакле, алгоритам је следећи: кренемо од нпр. доброг скупа са дијагоналним елементима D (N упита), сведемо га на добар скуп са једним елементом помоћу додатних N-1 упита и на крају потрошимо још највише 2N упита за проверу. У зависности да ли минимум/максимум у сваком кораку тражимо у O(N) (тривијално) или у O(\log N) (уз помоћ неке структуре), ово пролази за првих 6 или за свих 7 подзадатака.

Решење са очекиваним бројем упита реда O(N): Приметимо да уколико знамо вредности нека два поља (нпр. A_{i,j} и A_{k,l}) можемо елиминисати бар једно од поља A_{i,j}, A_{k,l}, A_{i, l}, A_{k,j} као потенцијалног кандидата за седло без икаквих додатних упита (нпр. ако је A_{i,j} \leq A_{k,l}, можемо закључити да A_{j,k} не може бити седло иако му можда не знамо вредност). Према томе, уколико смо поставили X упита, теоретски можемо елиминисати \frac{X(X-1)}{2} поља гледајући сваки пар упита. Наравно, овде може доћи до пуно преклапања (различити парови упита елиминишу исто поље) али се може показати (а и интуитивно је јасно) да је очекивани број упита (ако их постављамо рандом) потребан за елиминацију свих N^2 поља (осим евентуално једног) реда величине O(N). Додатно, упити не морају бити постављани било како већ у сваком кораку питати само неко тренутно не-елиминисано поље (и помоћу њега и претходних упита радити поменуту елминацију); уколико остане O(N) не-елиминисаних поља у неком тренутку, можда је боље пребацити се на стандардну Елиминацију итд.

Овај приступ, уз евентуалну рандомизацију или боље одабрани редослед упита, пролази за Подзадатке 1, 2, 4 и 5 а често и за 3 (због специфичних вредности и мало веће константе за дозвољени број упита у односу на Подзадатке 6 и 7). Са друге стране ово (вероватно) не може решити Подзадатак 6 (због строжег ограничења у броју упита и евентуално меморијског ограничења) као ни Подзадатак 7 (јер је сложеност O(N^2)).


#6

Филм

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

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

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

На сличан начин се може решити и трећи подзадатак, само је у случају када имамо N = 3 стринга повећава се сложеност генерисања преклапања.

Постоји и другачије решење за ова два подзадатка, чија идеја је јако важна за решавање задатка за максимални број поена. Рецимо, за N=3, посматрајмо једно парцијално решење, односно, префикс неког најкраћег валидног стринга. Нека је mask бит-маска са 3 бит-позиције која нам говори да ли се i-ти стринг до сада већ јавио, и нека су p_1,p_2,p_3 дужине најдужег стринга који је суфикс тренутног решења а уједно и префикс првог, другог и трећег стринга, редом. Додавањем једног слова ми можемо да проверимо које су нове вредности најдужег суфикса за сва три стринга. Ако је нека од тих дужина суфикса постала једнака дужини целог стринга, то је ново појављивање тог стринга. Ако се тај стринг већ јавио, решење постале невалидно, иначе, у одговарајући бит тренутне бит-маске треба уписати бит 1. Корисно је унапред израчунати прелазе, тј. тројке (l, x) \rightarrow l', где је l стара дужина префикса стринга, x слово које се додаје, l' је нова дужина тог најдужег префикса. Ови прелази се могу израчунати KMP алгоритмом, али и не морају, с обзиром да brute-force имплементација има временску сложеност O(L_i^3). Нас онда само занима најкраћи пут (гледано по броју слова) од стања (mask=000_2, p_1=0, p_2=0, p_3=0) до неког стања где је mask=111_2. Поред прелаза, ово решење ради у сложености O(K \times L_1 \times L_2 \times L_3).

За максимални број поена довољно је да приметимо да не морамо да памтимо најдужи префикс за сваки појединачни стринг, већ је довољно да нам стање буде најдужи суфикс тренутног парцијалног решења који је уједно и префикс неког од датих стрингова, тачније, стање ће нам бити тачно о ком префиксу се ради - ових префикса може бити највише \sum L_i. Прелазе можемо израчунати у линеарном времену помоћу Aho-Corasick алгоритма али, као и раније, не морамо, јер поново brute-force налажење прелаза ради у временској сложености O((\sum L_i)^3) и може се имплементирати елементарним (и спорим) алгоритмима претраге стрингова. Сада, коначно решење изгледа овако: Направимо граф чији су чворови уређени парови (mask, prefix) где је mask бит-маска са N позиција која нам говори о томе да ли се i-ти стринг до сада јавио, а гране су усмерене и од сваког чвора излази тачно K грана, по једна за свако слово, долазни чвор за сваку грану се може наћи горе описаним поступком помоћу израчунатих прелаза. Сада је решење најкраћи пут у овом графу од чвора (0, "") до неког чвора чија се бит-маска састоји само од јединица. Овај најкраћи пут можемо наћи обичним BFS алгоритмом. Временска сложеност је O((\sum L_i)^3 + (\sum L_i) \times 2^N \times K).