[Rešenja zadataka] 2021/2022 Kvalifikacije - Prvi krug

Несуседни

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

Како имамо тачно 2 различита слова, једини начин да стринг не садржи два иста суседна слова је да се слова појављују наизменично у стрингу тј. c_1c_2c_1c_2\ldots или c_2c_1c_2c_1\ldots. Ово је могуће ако и само ако је |a_1 - a_2| \leq 1. Заиста, ако је |a_1 - a_2| > 1, “истрошићемо” једно слово у наизменичном појављивању пре краја стринга. Са друге стране, ако је a_1 = a_2, имамо 2 могућа решења (било које слово може бити прво), а ако је |a_1 - a_2|=1, решење је јединствено јер морамо почети (и завршити) словом које се појављује више пута.

Сложеност алгоритма је O(a_1 + a_2), због исписа.

4 Likes

Трансфузија крви

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

За почетак, пацијенти О групе су једноставни: могу да приме само крв О
групе, тако да код њих немамо никаквих одлука. У првом пролазу кроз
пацијенте, можемо њима доделити одговарајуће количине О крви, и
затим у следећем пролазу разматрати само пацијенте А, Б и АБ групе.

У следећем пролазу можемо доделити крв пацијентима А групе. Код њих
имамо избор између А и О, али је одлука једноставна: сада када нема
више пацијената О групе, крв А групе је строго “мање корисна” од О,
јер сви који могу да је приме могу да приме и крв О групе. Дакле, ако
можемо, боље је да додељујемо крв А групе и чувамо О, коју ћемо
користити само ако више уопште нема крви А групе.

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

Ако је у било ком тренутку у залихама недовољно крви за неког
пацијента, прекидамо програм и исписујемо “nemoguce”. У супротном,
потребно је да за сваког пацијента сачувамо додељене јединице крви
(нпр. у низу) и испишемо их на крају.

2 Likes

Преписивачи

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

Приметимо прво да је удаљеност тачака са координатама (x_A, y_A) и (x_B, y_B) једнака \sqrt{(x_A-x_B)^2 + (y_B-y_А)^2}, а провера да ли су паралелне праве одређена овим двема, и тачкама (x_C, y_C) (x_D, y_D) је провера једнакости коефицијента правца ових права \frac{y_А-y_B}{x_А-x_B}=\frac{y_C-y_D}{x_C-x_D}, што како бисмо избегли дељење нулом можемо записати овако: (y_A-y_B)(x_C-x_D) = (x_A-x_B)(y_C-y_D).

Случај N \leq 4

Уколико је N мање од 4, јасно је да нема решења. Уколико је N тачно 4, можемо покушати да обележимо унете тачке са A,B,C,D у сваком редоследу и да проверимо да ли важи релација дата у задатку (да су праве AB и CD паралелне и да је удаљеност између A и B два пута мања од удаљености између C и D или обратно).

Случај N \leq 100

Можемо фиксирати било које 4 тачке и проверити да ли важи релација (прву фиксирану означимо са А, другу са B итд).

Случај N \leq 400

Можемо приметити да ако фиксирамо A, B, и C, тачка D се налази на јединственој правој кроз C, и то на јединственој удаљености (два пута мањој од \overline{CD}), те треба посматрати само 2 могућности за тачку D: тачка на тој правој на удаљености \overline{AB}/2 “лево” и “десно” од C. Ако додамо те тачке у почетни низ и сортирамо, свако додатно појављивање неке тачке m пута значи да та тачка може бити на краћој основици за m тројки, те је решење збир свих m вредности за све тачке, подељено са 2 (јер смо урачунали обе тачке краће основице).

Сви поени

Ако посматрамо пример сумњивог четвороугла, може нам пасти на памет да продужимо дуж AC и BD, и дуплирамо их (инспирација из АB=2\overline{CD}), и тада ћемо због Талесове теореме добити да је услову задатка еквивалентан услов да се те две дужи секу у истој тачки (покушајте да докажете, здраво је и забавно). Ова тачка је слика тачке A у односу на C и тачке B у односу на D. Како је N<1500, природно је размишљати у смеру решења с квадратном сложеношћу, те и посматрања свака два пара тачака. Уколико за сваке две тачке X,Y памтимо све тачке које се добијају као слика X у односу на Y, видимо да тачка која се појављује k пута одређује \binom{k}{2}=\frac{k*(k+1)}{2} сумњивих четвороуглова, те за сваку упамћену тачку треба сабрати ову вредност. Ово је могуће имплементирати сортирањем слика тачака представљених као пар бројева (координата) и бројањем појављивања сваке.

3 Likes

Цен*ура

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

Забрањена реч је ‘a’

У овом подзадатку је очито довољно само цензурисати сва појављивања слова ‘a’, што можемо да урадимо тако што линеарно прођемо кроз T и нађемо свуда где се појављује то слово, заменимо са *, и избројимо колико се пута појавио.

Сва слова забрањене речи су ‘a’

Исто је решење као у претходном подзадатку, само прескочимо првих M-1 појављивања слова ‘a’.

Да ли је једна реч подсеквенца друге?

Да бисмо умели да приступимо овом проблему потребно је анализирати алгоритам како проверавамо да ли је једна реч подсеквенца друге.
Ово се врши похлепним алгоритмом. Наиме, нека проверавамо да ли је реч S подсеквенца речи T. Онда пролазимо линеарно кроз реч T док памтимо најдужи префикс S који нам се појављује до сад као подсеквенца. Сада, када следећи пут наиђемо на следеће слово које би нам требало да бисмо повећали дужину тог највећег префикса (то јест следеће слово у S), знамо да нам је оптимално да га искористимо у конструкицији S као подсеквенце. То значи да у том случају можемо да повећамо дужину тог најдужег префикса, док он у супротном остаје исти. На крају видимо да ли је најдужи префикс S који је подсеквенца T управо цео S у том случају је одговор “ДА”, а у супротном “НЕ”.

Пуно решење

Сада када смо проучили тај алгоритам, можемо да решимо цео задатак.
Решење ћемо вршити динамичким програмирањем, најсличније ДП решењу за најдужу заједничку подсеквенцу две ниске. Наиме нека је DP[n][k] вредност "колико најмање карактера треба цензурисати у првих n слова T да би најдужи префикс S који је подсеквенца тих првих n карактера дужине тачно k". Сада ове вредности у динамичком програмирању се лако рачунају: ако не желимо да повећамо вредност k, онда кад наиђемо на слово које би нам га повећало, морамо да цензуришемо, а у супротном само повећамо вредност k. Како стања има MN и свако има константно прелаза, добијамо укупно временску и меморијску сложеност O(MN).

3 Likes

Ноћна вожња

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

Подзадатак када је N, Q \leq 4000

Можемо да одржавамо тренутни редослед насеља у низу. Операција замене се своди на једноставно замењивање два члана низа, док је одговарање на други тип догађаја мало компликованије. Можемо да пустимо DFS или BFS алгоритам из насеља x како бисмо нашли удаљености од истог до сваког другог насеља. Након што смо нашли и сачували удаљености можемо да прођемо кроз део низа од l до r и нађемо највећу удаљеност. Временска сложеност овог решења је O(QN).

Подзадатак када је свако насеље суседно са највише два друга насеља

У овом случају насеља заправо формирају ланац и можемо да их поређамо у низ почевши од једног краја. За свако насеље запамтимо његову позицију у овом низу. Када тражимо највећу удаљеност од насеља x до скупа насеља од l до r битна су нам само два насеља из тог скупа, насеље са најмањом и насеље са највећом позицијом (удаљеношћу од краја ланца). Ово можемо ефикасно да имплементирамо коришћењем неке структуре података која подржава упите за минимум/максимум на поднизу и промену члана низа. На пример можемо да користимо сегментно стабло и добијемо временску сложеност О(N + QlogN).

Подзадатак када је у сваком догађају x = 1 и p_a, p_b \neq 1

Како се у сваком питању тражи највећа удаљеност од насеља 1, на почетку пустимо DFS или BFS алгоритам из овог насеља и нађимо узаљености до сваког другог насеља. Чувајмо низ где је i-ти члан удаљеност од насеља 1 до насеља p_i. Питања се своде на тражење максимума на поднизу овог низа. Можемо и овде да искористимо сегментно стабло за ефикасне операције тражења максимума и промене у низу након догађаја првог типа. Временса сложеност је O(N + QlogN).

Решење без додатних ограничења

Слично као код решења за ланац за свако питање можемо да нађемо два насеља од којих ће увек једно бити најдаље без обзира на одабир насеља x. За ово решење треба нам мало теорије везане за стабла. Пречник стабла је највећа удаљеност између два чвора, а крајеви пречника су чворови који су на тој највећој удаљености. Корисна особина пречника стабла је то да је најдаљи чвор од произвољног чвора увек један од крајева пречника. Насеља која ћемо тражити су крајеви пречника подстабла које обухвата насеља p_l, p_{l+1}, \dots, p_r. И у овом решењу можемо користити сегментно стабло. За сваки сегмент чувајмо крајеве пречника, а пречник за два спојена сегмента тражимо тако што нађемо највећу удаљеност између 2 од 4 чвора који су крајеви пречника левог и десног сегмента. Остаје још да нађемо начин како ефикасно да нађемо удаљеност између два чвора. Можемо да поставимо чвор 1 као корен и израчунамо дубину сваког чвора depth(x). Дистанца између два чвора x и y је depth(x) + depth(y) - 2 depth(LCA(x, y)), где је LCA(x, y) најмањи заједнички предак чворова x и y, односно чвор на ком се пут од x до корена и пут од y до корена срећу. Најмањи заједнички предак може се наћи у O(logN) са binary lifting техником или у О(1) са sparse табелом над Ојлеровим путем. Препроцесирање за обе опције је временске и меморијеске сложености О(NlogN), а цело решење верменске сложености O(NlogN + Q log^2 N) или O(NlogN + QlogN) у зависности од одабране технике.

2 Likes