[Rešenja zadataka] Državno 2019


#1

Задатак Б1: Хакерисање

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

Пoдзадатак 1

У првом подзадатку, за сваки упит прођемо кроз подниз за који се тражи одговор и извршимо битовску конјункцију свих елемената. Временска сложеност је O(NQ).

Подзадатак 2

У другом подзадатку у низу су само јединице и нуле. Приметимо да је одговор на упит или 0 или 1. У овом подзадатку направимо префиксне суме, тј. проверимо колико пута се појављује 1 до неког индекса i. Нека је овај број p_{i}. Услов да одговор буде 1 је да између индекса l и r буду све јединице, тј. да важи p_{r}-p_{l-1}=r-l+1. Временска сложеност је O(N).

Подзадатак 3 (комплетно решење)

За комплетно решење неопходно је да замислимо наше бројеве у бинарном систему и да приметимо да битове овде можемо да посматрамо независно. Сада радимо сличан поступак као и у претходном подзадатку, за сваки бит k, нађемо у колико бројева до индекса i је он 1. Нека је овај број p_{k,i}. Да би тај бит био 1 када извршимо конјункцију свих елемената, потребно је да важи p_{k,r}-p_{k,l-1}=r-l+1. Тада је одговор на упит од l до r једнак \sum 2^k, за све k за које важи p_{k,r}-p_{k,l-1}=r-l+1. Временска сложеност је O(N\log A_{i}).


Public
#2

Задатак Б2: Пољопривредник

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

Анализа

Поделићемо задатак на два случаја:

  • када K \geq N, и
  • када K < N.

У случају у ком је K \geq N, задатак можемо свести на решавање
задатка за N-1 и K - (N-1) тако што одаберемо први елемент низа
(нпр. поставимо га на 1), конструишемо низ са N-1 елемената где
имамо K - (N-1) парова на растојању већем од X, и “померимо” тај
низ тако да је на растојању већем од X од првог елемента (тј. на све
елементе додамо X).

У случају када K < N, задатак можемо решити на следећи начин:

  • поставимо први елемент на 1,
  • поставимо K елемената на X, и
  • остале елементе ставимо између ова два (на пример, на 2).

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

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


#3

Задатак Б3: Минирање

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

Анализа

Ако је минама снаге K могуће доћи до циља, очито је могуће на исти
начин и са снагом K+1. Самим тим, минимално K можемо наћи бинарном
претрагом “по решењу”. За ово нам је потребан алгоритам којим ћемо
одредити да ли, за фиксно K, можемо стићи од полазног до циљног
поља.

Ако поставимо мину на неко поље и тиме ослободимо квадрат димензија
2K+1 \times 2K+1, након што изађемо из тог квадрата нема разлога да
се враћамо у њега (у супротном, можемо “прескочити” део пута од
изласка до повратка). Због овога, мине можемо посматрати као
“телепорт” уређаје, који омогућавају да се пребацимо на произвољно
поље на растојању не већем од K (које може бити и заузето).

Дакле, наш пут од полазног до циљног поља ће имати следећи облик:

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

Поља до којих можемо стићи у првом кораку можемо наћи претрагом у
дубину или ширину од почетног поља. Затим маркирамо сва поља на
растојању не већем од K од неког од пронађених, и покренемо нову
претрагу од свих маркираних поља (за трећи корак). Ову процедуру
поновимо још једном за другу мину и кретање после ње. Ако је на крају
овај алгоритам нашао пут до циља, могуће је доћи до циља са минама
снаге K.

Укупна сложеност једне провере (за фиксно K) је \mathcal{O}(N^2)
(три претраге и два проласка кроз матрицу), а како нам за бинарну
претрагу треба \log{N} провера, сложеност алгоритма је
\mathcal{O}(N^2 \log{N}).

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

При имплементацији алгоритма, треба водити рачуна о кораку где
маркирамо сва поља на растојању не већем од K од скупа поља до којих
већ имамо пут. Ово не можемо радити тако што за свако сваког поље до
ког знамо пут обележимо његово окружење, јер је сложеност овога
\mathcal{O}(N^2 K^2), тј. у најгорем случају (за K=N) \mathcal{O}(N^4).

Овај део програма је могуће имплементирати на више начина. Једна
могућност је да покренемо претрагу у ширину од свих поља до којих
имамо пут (паралелно), коју прекидамо када дођемо на растојање K
(обратите пажњу да ова претрага не узима у обзир “блокираност” поља и
да растојање морамо гледати одвојено за вертикално и хоризонтално
кретање).

Друга могућност је да израчунамо матрицу префиксних сума на матрици
“да ли имамо пут до овог поља” (где поља имају вредност 1 ако имамо
пут до њих, а иначе 0). Помоћу ове матрице можемо у \mathcal{O}(1)
одредити колико поља до којих имамо пут постоји у квадрату 2K+1 \times 2K+1 центрираном на произвољном пољу, тј. да ли је до њега могуће “скочити”.


#4

Задатак А1: Нз

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

Потпроблем 1

У првом потпроблему је потребно обрисати тачно један број. Ако кренемо кроз низ са лева на десно, јасно је да први пут када важи услов А[i] > А[i+1] треба обрисати А[i], јер се у супротном сигурно добија лексикографски већи нз. Ако услов никада није задовољен, бришемо последњи елемент низа.

Потпроблем 2

У другом потпроблему у низу су само јединице и нуле. Уколико у низу има барем N-K нула финални нз ће бити састављен искључиво од њих, па бришемо све јединице и вишак нула.

У супротном, желимо да задржимо све нуле и онолико јединица колико је неопходно (нека је тај број N_1). Оптимално је задржати последњих N_1 јединица у низу, и финални нз можемо одредити проласком кроз низ са десна на лево. Као што је поменуто, свака нула на коју наиђемо мора да буде део нза, као и првих N_1 јединица на које наиђемо (остале јединице бришемо).

Потпроблем 3

Трећи потпроблем се може решити на два начина.

Први начин

Користићемо динамичко програмирање. Нека је S(l, c) лексикографски најмањи нз који се може добити брисањем тачно c елемената почевши од префикса оригиналног низа дужине l. Рачунамо комплетну DP табелу користећи рекурентну везу S(l, c) = \min(S(l-1, c-1), S(l-1, c) + a[l-1]), и решење налазимо полазећи од S(N, K) и пратећи пут кроз табелу уназад.

Рачунање табеле вршимо у \mathcal{O}(N^3), пошто је за лексикографско поређење два подниза наивно потребно \mathcal{O}(N). Свакако, ово је довољно добро за трећи потпроблем.

Други начин

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

Назовимо нз тражен у задатку кратко оптималан нз и дефинишимо најлевљи оптималан нз као оптималан нз добијем задржавањем елемената на индексима I = \{i_0, i_1, \dots, i_{N-K-1}\} таквим да не постоји други оптималан нз чији су индекси J = \{ј_0, j_1, \dots, j_{N-K-1}\} такви да је низ J лексикографски мањи од I. Другим речима, најлевљи оптималан нз је онај чији су задржани елементи ,,што левље’’ у оригиналном низу.

Најлевљи оптималан нз можемо одредити на следећи начин (низ индексирамо од нуле):
i_{-1} = -1,
i_r = LRMQ(i_{r-1} + 1, K+r), где LRMQ(a, b) представља индекс најлевљег од свих минималних елемената у интервалу [a, b].

Леви крај интервала следи из тога да мора важити i_r > i_{r-1}, а десни из тога да не смемо одабрати индекс i_r такав да до краја низа нема довољно бројева да се формира цео нз (одатле K+r = N - (N - K) + r). Коректност оваквог похлепног приступа следи директно из дефиниције лексикографског поређења.

Користећи ово, уз наивну имплементацију LRMQ која пролази кроз цео интервал, можемо у укупној сложености од \mathcal{O}(N^2) одредити оптималан нз. Ово је довољно само за трећи потпроблем. За наредна два потпроблема користимо исту идеју уз боље начине за рачунање LRMQ.

Потпроблем 4

У четвртом потпроблему све вредности у низу су у интервалу [0, 100]. Ово додатно ограничење нам омогућава да решимо LRMQ у \mathcal{O}(M) (где је М максимални елемент у низу). Ово можемо урадити на више начина.

Један од начина је изградња префиксних сума које чувају број појављивања сваке вредности у [0, М]. Конкретно градимо матрицу pre димензија N\times M, где је pre(l, v) број појављивања вредности v у префиксу низа дужине l, и рачуна се као pre(l, v) = pre(l-1, v) + (A[l-1] == v).

Сада LRQM на неком интервалу решавамо тако што нађемо минималну вредност одузимањем одговарајућих вредности из матрице pre, а затим пронађемо њено прво појављивање линеарном претрагом. Будући да у наредном позиву LRMQ крећемо од i_r+1 линеарна претрага не утиче на сложеност и укупна сложеност је \mathcal{O}(NM).

Потпроблем 5 (комплетно решење)

Наравно, у последњем потпроблему овај приступ решавања LRMQ не функционише. Постоје барем три начина да се ово реши и у питању су познате методе за RMQ проблем (Range Minimum Query).

Први начин

Можемо изградити сегментно стабло за минимуме над низом, уз пажљиво третирање једнаких вредности тако да се увек преферира левља. Овиме добијамо LRMQ упите у \mathcal{O}(\log N), сама изградња стабла је \mathcal{O}(N\log N), па је укупна сложеност \mathcal{O}(N\log N). Ово је довољно за максималан број поена.

Други начин

Кад год нема измена низа, уместо сегментног стабла се може користити sparse table Sparse table је једноставнији за имплементацију и даје одговоре на упите у константном времену (\mathcal{O}(1)). Како је сложеност изградње иста као у случају сегментног стабла и у овом случају доминира (\mathcal{O}(N \log N)), коришћење ове структуре не доводи до убрзања (на нивоу сложености), али представља алтернативан начин за решавање задатка.

Трећи начин

Иако су \mathcal{O}(N\log N) решења довољно добра за свих 100 поена, задатак је могуће решити и линеарно, у сложености \mathcal{O}(n). Ако приметимо да интервали за које желимо LRMQ нису угњеждени, тј. да су низови левих и десних граница неопадајући, можемо применити sliding window, тј. two pointers технику.

У општем случају, sliding window RMQ решавамо крећући се кроз низ са лева на десно, притом одржавајући интервал који нас интересује. У сваком кораку потенцијално померамо границе тог интервала удесно, и желимо да у сваком моменту у \mathcal{O}(1) имамо минимум на том интервалу.

У ову сврху одржавамо ,,листу кандидата’’ (најзгодније имплементирану као deque). Кључна опсервација коју користимо је да постоје елементи који од неког момента никада не могу бити минимални у интервалу (конкретно, такви елементи A[i], да унутар интервала постоји индекс j такав да је i < j и A[i] > A[j]). Важно је да стоји знак > а не \geq јер тражимо најлевљи минимум.

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

Резултат овога је да је листа кандидата сортирана неопадајуће и да је минимални елемент у тренутном интервалу увек на почетку листе, па му можемо приступити у константном времену, и решити цео задатак у \mathcal{O}(n).


#5

Задатак А2: Визаард

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

Анализа

На почетку, констатујмо да ни у једном оптималном решењу нећемо примењивати оба типа операција на исти број – или ћемо само повећавати, или само смањивати тај број.

Приметимо да, уколико желимо да је and свих елеманата већи од 0, мора постојати једна позиција на којој сви бројеви имају бинарну цифру 1. Уколико фиксирамо ту позицију t, можемо израчунати за сваки број у константном времену најмањи број додавања број 1 на њега тако да у том броју цифра на позицији t постане 1. Такође, можемо израчунати и најмањи број одузимања потребан за исту ствар. Оптимално нам је да изаберемо ону опцију за коју треба мање операција, али је такође корисно да сачувамо да ли је за неки број било могуће да узмемо било коју опцију (уколико је број додавања и одузимања исти).

Како смо испунили први услов (за фиксно t), прва следећа ствар коју треба проверити је да ли је xor свих овако добијених бројева 0 – ако јесте, нашли смо најмањи број операција за изабрану позицију. Уколико није, а постојала је друга опција за неки број, искористићемо њу и она ће променити xor, тако да није потребно додатних операција, уколико није постојала, требаће нам још 2 или 1 операција, у зависности од тога да ли је t изабрана позиција најдеснија или није.

Урадивши ово за свако t од 0 до 60 (максимални број битова), све што нам је преостало је да узмемо минимум добијених бројева операција.

Временска сложеност: O(NlogMAX), где је MAX максималан број у улазу (10^18).


#6

Задатак А3: Париз

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

Анализа

Потпроблем 1

Праволинијско решење се добија тако што се свака атракција посматра као последња на тури коју је обишла Ана. Ако је фиксирана последња атракција, онда се комплетна тура добија тако што се крене последње атракције и ‘враћа уназад’ померајући се сваки пут до атракције од које води једини пут до атракције у којој се тренутно налазимо. Наравно, током померања се сабирају лепоте атракција које је Ана посетила. Поступак се прекида у тренутка када би се наредним кораком враћања премашило укупно време које Ана има на располагању.

Потпроблем 2

Решење се добија уз малу дораду решења за потпроблем 1. Полазећи од атракције А и враћајући се дуж пута који води до тренутне атракције, пре или касније ћемо затворити петљу. Може се одредити време да се обиђу све атракције на петљи, а затим и колико пута се та петља може обићи а да се не премаши време T. На крају ако је остало времена треба започети још један пролаз кроз петљу и зауставити се у тренутку када време премаши време T. Наравно, током поступка је одређивана сума лепота атракција које су обиђене.

Потпроблем 3

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

Потпроблем 4

Ако је низ X пермутација бројева од 1 до N, онда сви путеви образују колекцију петљи (циклуса). За сваку петљу је довољно одредити чвор од кога треба кренути како би се добила максимална сума лепота атракција које су посећене. То се може обавити и линеарном времену (линеарном по броју атракција на петљи), коришћењем два показивача (индекса): један за почетак туре, а други за крај туре.

Потпроблем 5

Максимални број поена се добија тако што се за сваку атракцију A одреди сума лепота атракција (као и време потребно да се обиђу те атракције) на тури која се завршава на атракција A и чија је дужина 2^I (I=0, 1, 2, ... \lfloor \log T\rfloor). Дужина туре је једнака броју атракција на тури. То се може обавити у сложености O(N \times \log T). Наиме, ако знамо суме атракција за туре дужине 2^{I-1}, онда суму за туру дужине 2^I која се завршава на атракцији A добијамо тако што надовежемо две туре дужине 2^{I-1}: туру која се завршава на атракцији A и туру која се завршава у чвору од кога води пут до почетка туре дужине 2^{I-1} која се завршава на атракцији A.

Када смо одредили описане суме тура, онда је потребно за сваку атракцију одредити туру максималне дужине која се завршава у тој атракцији. То обављамо тако што комбинујемо туре одређене у претходном пасусу. Почињемо са туром дужине 2^{\lfloor\log T\rfloor}. Ако је време потребно за њен обилазак веће од дозвољеног преполовимо дужину (тј. поделимо са 2). Ако време није веће, додајемо ту туру на комплетну туру, померамо се на атракцију на којој та тура почиње (тачније на атракцију која претходи атракцији на којој та тура почиње) и настављамо са туром двоструко краћом од оне која је додата.


#7

Zasto ovo resenje za B3 dobija MLE (izbacio sam deo za m=2) Kod


#8

U poslednjoj pretrazi (od reda 86) polja obeležavaš kao obiđena nakon što ih izvadiš iz queue-a, umesto u trenutku kada ih ubaciš. Zbog ovoga, jedno polje može da se pojavi u queue-u više puta, čak i eksponencijalno mnogo.

Na primer, u situaciji gde pokrećeš pretragu od gornjeg levog ugla prazne table (brojevi predstavljaju broj pojavljivanja tog polja u queue-u):

1  1  1  1  1
1  2  3  4  5
1  3  6 10 15
1  4 10 20 35
1  5 15 35 70

#9

Au ovo nije smelo da se desi…


#10

Malo drugacije resenje za B2:
Postavimo niz a[i] od n elemenata (indeksiram od 1 do n), svaki na razdaljini x od prethodnog, tako da imamo n*(n-1)/2 odgovarajucih parova. Zatim, smanjujemo poslednja j broja za 1 (na pocetku j je 1, na kraju n). Primecujemo da svakim smanjivanjem jednog broja, smanjujemo i broj parova za 1 (jer nestaje par izmedju tog broja i broja a[n-j]). I tako radimo sve dok broj parova ne postane k.
Jos jedna stvar koja treba da bude na umu je da kad se smanje svih j brojeva za 1, postaviti te brojeve da budu isti kao a[n-j]ti broj, jer tako mozemo osigurati optimalno resenje za sledece j.
Slozenost: O(N^2) … Mada isto moze da se optimizuje na O(N) tako sto ne smanjujemo za 1 za svako j, nego smanjujemo j samo kad znamo da cemo tad da prekidamo sa smanjivanjem i da zavrsimo program.