Задатак А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).