Solutia problemei Niciomare

Pentru rezolvarea acestei probleme complet este nevoie de o intelegere a "Smenului de la Batch" (numit in engleza "Convex hull trick"), care este explicat bine aici: . Nu este nevoie sa stiti varianta complet dinamica a batch-ului pentru solutia finala.

Pentru 30 de puncte

Pentru 30 de puncte, se poate calcula, cu ajutorul programarii dinamice, o matrice d[i][j], cu semnificatia care este modul optim de a selecta j secvente dintre primii i DJ. Recurenta este d[i][j] = max { d[k][j-1] + (w[i] - w[k])² : k ≤ i si (w[i] - w[k]) ≤ S }, unde w[i] este definit ca v[ 1] + ... + v[i]. Complexitatea este N² * K.

Pentru 60 de puncte.

Pentru 60 de puncte, observam ca putem optimiza calcularea recurentei dinamicii la complexitatea de O(log²(N)) pentru fiecare celula a matricii d. Pentru a face aceasta, observam ca recurenta se reduce la a calcula maximul a mai multor functii lineare, la un punct dat (caci d[k][j-1] + (w[i] - w[k])² = d[j][k-1] + w[i]² - 2 * w[i] * w[k] + w[k]²; dupa ce scoatem constanta w[i]² in fata maximului recurentei, ramane o functie lineara cu parametrii d[j][k-1] + w[k]², respectiv -2 * w[k], evaluata la w[i]), fiecarui functii lineare asociindu-se cate o pozitie intr-un sir. Subtaskul acesta este facut pentru solutii mai tehnice ale acestei probleme, fara observatii, dar cu mai mult cod -- asa ca nu va speriati daca vi se pare prea tehnica solutia aceasta intermediara (la nivel de tehnica, e chiar mai complicata ca solutia completa). Un mod simplu ca idee dar dificil de implementat prin care se poate rezolva asta este prin a folosi un arbore de intervale, fiecarui nod/interval din arbore fiind-ui asociat cate un batch complet dinamic sau un Li-Chao tree (!https://cp-algorithms.com/geometry/convex_hull_trick.html!).

Pentru 70 de puncte.

Pentru inca 10 puncte, folosim solutia precedenta, doar ca observam ca interogarile se fac in ordine crescatoare a pantei. Astfel, un batch complet dinamic este inutil. Mai degraba, se poate folosi cate o stiva cu dreptele vazute cu fiecare nod in parte (precum la problema Vmin). Aceasta scoate un log fata de solutia de 60 de puncte.

Pentru 100 de puncte.

Pentru solutia completa, vom vrea complexitatea O(NK). Voi descrie aici cum se trece de la o linie a dinamicii enuntate mai devreme la urmatoarea, in timp linear. Iarasi, noi trebuie practic sa calculam, dintr-un sir dat d, un sir nou d' dupa formula d'[i] = max { d[k] + (w[i] - w[k])² : k ≤ i si (w[i] - w[k]) ≤ S }. Altfel spus, fie f[i] o functie astfel incat f[i](x) = d[i] + w[i]² - 2 * x * w[i]. Atunci, noi vrem sa calculam d' astfel incat d'[i] = w[i]² + max { f[k](w[i]) : k ≤ i si (w[i] - w[k]) ≤ S }. Practic, pentru niste intervale de query [st[i], i], unde st[i] e pozitia minima din sir astfel incat w[i] - w[st[i]] ≤ S, noi vrem sa stim functia lineara f[j] din intervalul asta care da valoarea minima pentru argumentul w[i]. Observatiile cheie sunt ca valorile din st nu scad (ca valorile lui v sunt pozitive), ca w[i] creste mereu, si ca pantele functiilor lineare din f tot scad. Sa observam, cum st nu scade, ca putem sa ne imaginam ca avem o coada de drepte, si ca noi vrem mereu sa aflam dreapta care da maxim la o abscisa data. Mai mult, mereu primim in coada drepte cu pante din ce in ce mai mici, si interogari la abscise crescatoare.

Acum observatia tare: o coada poate fi modelata prin doua stive. Hai sa ne gandim exact cum arata aceasta simulare. Tinem o "stiva din fata" F si o "stiva din spate" B. Cand o dreapta intra, intra in F. Cand o dreapta iese, vedem daca B este gol. Daca da, transferam toate dreptele din F in B, si continuam. Observam ca dreptele se insereaza in F in ordinea descrescatoare a pantei, si se insereaza in B in ordinea crescatoare a pantei. Interogarile vin in continuare in ordine crescatoare a abscisei. Problema este urmatoarea: noi putem sa modelam stergerile din F ca o resetare la starea initiala a batch-ului (ca toate stergerile sunt parte a unei goliri totale). Pe de alta parte, stergerile din B sunt mai dificile -- le-am putea modela cu un batch persistent precum in problema harbingers, dar asta e si urat, si ineficient. Aici, solutia mea se bazeaza pe faptul ca noi putem sa raspunde la interogari in oricare ordine am vrea noi. Astfel, eu voi stoca toate dreptele ce le-as insera in B, impreuna cu interogarile,

Prima parte a rezolvarii problemei este data de gasirea inaltimii pisicii. Pentru a evada, pisica isi poate alege un unghi si o pozitie in interiorul custii sub care sa realizeze o translatie pentru a evada printre doua bare ramase consecutive. Practic, Pisica va fi incadrata de doua drepte paralele iar distanta dintre ele trebuie sa fie minima.

Pentru a minimiza distanta dintre cele doua drepte paralele care vor incadra pisica, e suficient sa incercam ca una din ele sa fie data de un segment a doua varfuri consecutive ale Pisicii. Se observa ca daca ne fixam segmentul, dreapta paralela care va incadra Pisica va atinge varful de pe Pisica aflat la cea mai mare distanta de dreapta aleasa.

Pentru calculcul inaltimii, e suficient sa tinem un indice la punctul care obtine aria cea mai mare cu cele doua puncte ale segmentului. Acest indice se muta odata cu schimbarea segmentului ales. Pentru fiecare segment, calculam distanta ca fiind aria celor trei puncte impartit la lungimea segmentului, si luand minimul tutoror acestor valori aflam inaltimea Pisicii. Astfel, obtinem in O(M) intaltimea dorita.

A doua parte a rezolvarii este data de alegerea varfurilor Custii, in asa fel incat fiecare doua puncte alese consecutive sa se afle la o distanta cel putin egala cu inaltimea Pisicii.

Pentru 60 de puncte

E suficient sa fixam in O(N) unul din punctele pe care le pastram. Pentru fiecare fixare, putem parcurge in O(N) toate punctele in ordine trigonometrica, luand decizia greedy daca pastram sau nu punctul - il vom pastra doar daca urmatorul punct ar fi la distanta prea mare de ultimul ales. Dintre toate variantele in care am fixat un punct, o alegem pe aceea care obtine solutia optima. Obtinem complexitatea de O(N^2).

Pentru 100 de puncte

Putem calcula urm[i] = punctul urmator din poligon pe care trebuie sa il pastrez daca pastrez punctul i. Datorita faptului ca poligonul este convex, urm[i + 1] este fie urm[i], fie mai incolo in sens trigonometric. Calculul sirului urm[] se poate realiza in O(N).

Apoi putem folosi aceste salturi pentru a putea obtine rapid solutia optima in complexitate mai buna. De exemplu, putem tine d[i][j] = cat de mult ma extind in sens trigonometric daca fac 2ⁱ salturi de forma x -> urm[x] daca plec din j. Initializarea este d[ 0 ][i] = distantaTrigonometrica(i -> urm[i]) iar recurenta se realizeaza in O(1). Dupa aceasta precalculare de O(N * logN), putem afla in O(logN) care este numarul de puncte pe care trebuie sa le pastrez daca aeg sa il pastrez neaparat pe i. Luand pe rand toate valorile posibile ale lui i, aflam solutia optima.

Complexitate finala: O(M + NlogN) timp si O(M + NlogN) memorie. Mentionam ca exista si solutii liniare.