[Rešenja zadataka] SIO 2018 - Prvi dan

[ivan100sic]

Пацови

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

Решење задатка се оквирно може поделити на две фазе: У првој, идентификујемо на којим позицијама се налазе стрингови из низа B у стрингу A, где A посматрамо као цикличан стринг. У другој, проверавамо колико најмање стрингова из B нам треба да бисмо направили стринг еквивалентан стрингу A.

Прва фаза - тражење стрингова

Један од ефикаснијих начина да се ово уради јесте да се скуп стрингова из B представи у облику Trie структуре података. Затим, за сваку полазну позицију i у стрингу A крећемо се унапред низом слова A_i, A_{i+1}, \ldots A_j. Ако “излетимо” из стабла Trie прекидамо и настављамо са наредном вредношћу i. Иначе, ако се налазимо у чвору који одговара неком стрингу из B памтимо да је A_i, \ldots, A_j \in B. Овај део ради у временској сложености O(N^2 + \sum L_i).

Друга фаза - налажење минималног броја стрингова

Претпоставимо да је стринг A апериодичан. Уколико није, налазимо његову најмању периоду. Приметимо да се права може поплочати на еквивалентан начин поплочавању стрингом A ако и само ако постоји неки низ стрингова S_1, S_2, \ldots S_k из B који покривају позиције [x_1, x_2-1], [x_2, x_3-1], \ldots, [x_{k-1}, x_k-1] где је x_k = x_1. Стога, правимо граф са N чворова и стављамо грану (i, j) уколико је A_i, \ldots, A_{j-1} \in B, а затим тражимо најкраћи циклус у графу. У случају да A није апериодичан, у обзир долази сваки пут који води од чвора i до чвора j где важи d | i-j, где је d дужина најкраће периоде. Налажење најкраћег пута односно циклуса у овом графу је најједноставније урадити Флојд-Варшаловим алгоритмом, у свега 4 линије кода. Овај део ради у временској сложености O(N^3).

[ivan100sic]

Имање

Аутор, аутор решења: Алекса Плавшић
Тестери: Никола Спасић, Демјан Грубић

Као и већина других output only проблема, овај задатак захтева детаљнију анализу приложених фајлова и тестирање различитих решења на датим тест примерима. Решење не мора бити претерано временски и меморијски ефикасно, једино је важно да се програм изврши у неком догледном времену како би могле да се тестирају и друге стратегије. Основна идеја алгоритма који је користила комисија је максимизовање броја језера фарбањем једног језера (једне повезане компоненте воде) попут шаховске табле. На тај начин од једног језера величине X, добићемо отприлике \frac{X}{2} језера, са приближно толико утрошеног материјала. Пошто је очигледно да нећемо моћи да прекријемо сва језера на овај начин, нећемо имати довољно материјала, морамо на неки начин да одредимо која језера су најоптималнија за прекривање. За решавање овог подзадатка можемо користити динамичко програмирање и проблем ранца. Ранац би имао укупну запремину K, предмети су у овом случају еквивалентни језерима, тежине предмета би биле једнаке броју поља која морамо трансформисати из воде у земљу да би добили шаховску таблу, док би зарађени новац био еквивалентан броју језера која смо добили преграђивањем велике компоненте. Након бирања неких оптималних компоненти и њиховог фарбања, проћићемо кроз сва офарбана језера још једном и уклонити поља која су вишком промењена. Може се десити да неко поље нема потребе претварати у земљу, зато што је рецимо већ окружено земљом и уништили смо једно језеро, на тај начин мало рушимо изглед шаховске табле али је јасно да број језера не смањујемо и добијамо додатни материјал који можемо искористити.

Поставља се питање шта додатно можемо одрадити са преосталим материјалом, који нисмо искористили у првом бојењу или смо додатно уклонили. Наравно и њега је потребно расподелити на одређена места. Стратегија којом смо се водили у овом случају је, преграђивање неког од тренутних језера на два језера где би величина другог језера била 1 \times 1. Овде можемо запамтити за свако поље воде колико је потребно додавања земље да би се оно оградило (тај број може ићи од 1 до 4). У сваком потезу ћемо бирати језеро коме недостаје најмање поља да буде ограђено(требало би да се може лако показати да ће увек постојати водено поље коме неће недостајати више од 2 поља земље).

У приложеним материјалима имате још неколико стратегија решавања овог проблема, треба обратити пажњу на стратегију која користи BFS у одређивању оптималног решења. Она је имала најбоље резултате на неким од примера, али је поприлично спора и на решење се треба чекати и до 10 минута.

Сложеност описаног алгоритма је O(k \times BrojJezera).

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

Први део бојења језера попут шаховске табле можемо урадити једноставно коришћењем законитости да сва поља на шаховској табли исте боје дају уједно и исти остатак при дељењу са два њихових координата - (i+j) mod 2. Важно је пробати бојење и парних и непарних поља и на неки начин изабрати бољу од опција. Део са динамичким програмирањем и ранцем може бити врло меморијиски захтеван, тако да се мора осмислити пажљиво алгоритам за уклањање једне координате из динамичке матрице. Идеја коју смо користили је рачунање низа парова DP[i], који би давао информацију о максималном резултату који можемо добити ако смо офарбали не више од i поља и из ког стања смо дошли до ове позиције. Друга вредност нам помаже око даље реконструкције језера за бојење. За последњи део и фарбање језера може се користити нека од структура која би памтила поља са тачно i потребних ограђивања, која би могла лако да брише бројеве из скупа и да их поново убацује у други скуп. Детање имплементације можете видети у приложеним кодовима.

Волели бисмо да чујемо и ваше идеје за овај задатак, тако да будите слободни и напишите ако вас је заинтересовао.

[ivan100sic]

Попис

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

Размислимо прво како бисмо решили задатак у случају да није дата матрица већ низ вредности и да нема измена низа, па ћемо ово решење уопштити. Јасно је да се намеће Мо-ов алгоритам као потенцијално решење. Врло једноставно можемо одржавати за свако i, 1 \leq i \leq V број C_i - колико пута се вредност i јавља у тренутном прозору и такође за колико различитих вредности i важи да су једнаке C_i, B_i, нека је тај број Z. У 1-димензионој варијанти временска сложеност би била O(N \sqrt{N} + Q).

Генерализација у више димензија и измене

Посматрајмо 5-димензиони простор, где 4 димензије одговарају позицијама (x_1, y_1, x_2, y_2) прозора док последња димензија одговара редном броју упита. Посматрајмо колико нам елементарних корака треба да од тачке (x_1, y_1, x_2, y_2, t) дођемо до тачке (x_1', y_1', x_2', y_2', t'). Кроз просторне димензије се крећемо тако што повећавамо или смањујемо вредности x_1, y_1, x_2, y_2. Да бисмо једну од њих променили за тачно један, треба нам онолико времена колика је ширина прозора у другој димензији (толико вредности бива убачено тј. избачено). Кретање кроз време је једноставније, уколико је позиција прозора фиксна, само посматрамо да ли вредност која се мења у тренутку t упада у прозор. Ако не упада, само је променимо у матрици а ако упада додатно ажурирамо вредности C_i, Z. Сада, изделимо цео овај простор на блокове, који у просторној димензији имају ширину \frac{D}{N} а у временској D. Унутар једног блока могуће је доћи од било које до било које друге тачке у не више од 5D елементарних корака. Од једног блока до суседног блока могуће је доћи у D елементарних корака. Најзад, распоредимо упите у блокове и решавамо упите из једног блока, па из неког од суседних блокова, и тако даље. Укупан број елементарних корака потребан да се реше сви упити је не већи од DW + 5DQ, где је W = \frac{N^4Q}{(\frac{D}{N})^4 D} = \frac{N^8Q}{D^5} број блокова. Сада, нађимо најбољу величину блока. Ово се може урадити простим испробавањем различитих вредности D али се добра процена може наћи математички. Нађимо извод израза DW + 5DQ по D. Он износи 5Q - \frac{4N^8 Q}{D^5}. Ако га изједначимо са нулом и решимо по D, добићемо вредност која минимизује време извршења. Резултат је D \approx 0.956 N^\frac{8}{5}, односно, за N=840, D \approx 45600. Пошто је Q \leq 10000 ово значи да не морамо да делимо у блокове по временској димензији, док у просторној делимо на блокове ширине \approx 54, најближи делилац броја 840 је 56. Временска сложеност решења је O(Q N^\frac{8}{5}).