Solutii Algoritmiada 2019 Runda Maraton

Solutia problemei Niciomare

In primul rand, se observa ca raspunsul este maxim K * S * S, care nu depaseste 1018, deci putem face calculele pe long long chiar daca suma numerelor din input este pana la 1013.

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])2 : k ≤ i si (w[i] - w[k]) ≤ S }, unde w[i] este definit ca v[ 1] + ... + v[i]. Complexitatea este N2 * K.

Pentru 60 de puncte.

Pentru 60 de puncte, observam ca putem optimiza calcularea recurentei dinamicii la complexitatea de O(log2(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])2 = d[j][k-1] + w[i]2 - 2 * w[i] * w[k] + w[k]2; dupa ce scoatem constanta w[i]2 in fata maximului recurentei, ramane o functie lineara cu parametrii d[j][k-1] + w[k]2, 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 (aici).

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])2 : 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 - 2 * x * w[i]. Atunci, noi vrem sa calculam d' astfel incat d'[i] = w[i]2 + 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, vom stoca toate dreptele ce le-am insera in B, impreuna cu interogarile, memorand pentru fiecare interogare adancimea stive de drepte la momentul ei. Stocam de-asemenea cate drepte s-au sters din stiva B. Cand se sterg toate dreptele din stiva, vom raspunde la toate interogarile ce s-au acumulat in stiva de la ultima golire a stivei, in ordine inversa (adica vom raspunde mai intai la cele ce au aparut cand erau sterse aproape toate dreptele din stiva, apoi la cele de cand stiva era mai plina). Asta functioneaza ca odata umpluta la maxim stiva B nu mai primeste drepte pana se goleste. Astfel putem simula stiva B offline in timp linear iarasi. Per total, asta ne da o solutie in complexitate O(NK).

Solutia problemei Pisica

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). Acest lucru e posibil tocmai pentru ca: Se garanteaza ca in situatia in care se pastreaza toate barele, pisica se poate roti/translata succesiv astfel incat sa atinga orice bara cu orice varf al ei.

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 2i 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 aleg 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.

Solutia problemei Tubeyou

In primul rand, putem aduna la fiecare durata[i] numarul K, si de acum putem sa consideram K = 0.

Pentru 10 puncte

Vom mentine sirul next[i] si vom face operatiile in ordinea data. La update, putem parcurge tot sirul next[] si daca next[i] == x, il schimbam in next[x]. La query, putem merge din a in next[a] pana cand am mai ajuns intr-un nod vizitat la acest query si vom retine care este timpul timpA la care vom deschide fiecare videoclip vizitat. Apoi din b vom face o parcurgere asemanatoare. La final, se considera videoclipurile vizitate atat din a, cat si din b, si se ia acela pentru care max(timpA, timpB) este cat mai mic. Daca nu exista nod vizitat de ambii, afisam infinit.

Pentru 100 de puncte

Mai intai remarcam ca structura grafului format din muchiile orientate (i, next[i]) este o multime de componente conexe, iar fiecare componenta conexa este un ciclu simplu de care sunt agatati mai multi arbori. Ca observatie, ciclcul poate fi format si dintr-un singur nod, in caz ca next[x] == x.

La un query ce ar trebui sa vedem este in primul rand daca nodurile se afla in aceeasi componenta conexa. In caz ca nu, afisam infinit. Altfel, ar trebui sa stim daca fac parte din acelasi arbore cu radacina pe ciclul componentei lor, sau se afla in arbori diferiti. Daca se afla in acelasi arbore, afisam maximul intre distanta de la a la lca(a, b) si distanta de la b la lca(a, b) (prin lca am notat lowest common ancestor). Daca se afla pe arbori diferiti, notam cu A radacina arborelui lui a si cu B radacina arborelui lui b. Atunci raspunsul este minim(maxim(dist(a, A) + dist(A, B), dist(b, B)), maxim(dist(b, B) + dist(B, A), dist(a, A))).

La un update e ca si cand am modifica durata[x] = 0, mai putin pentru clipele in care se da un query in care a sau b este egal cu x, caz in care reconsideram durata[x] la valoarea ei normala. Vom face distinctie intre cazul in care nodul apartine unui ciclu sau strict unui arbore.

Prin urmare avem de efectuat operatii de genul:

  • Scade valoarea unui nod intr-un arbore
  • Scade valoarea unui nod intr-un ciclu
  • Afla distanta de la un nod la un stramos al sau intr-un arbore
  • Afla distanta de la un nod la altul intr-un ciclu

Aceste operatii ne duc cu gandul la liniarizarea plus-minus a arborilor si la mentinerea unui arbore indexat binar atat peste aceste liniarizari, cat si peste ciclii. Putem mentine un singur aib pentru toti arborii, daca le concatenam liniarizarile. Asemanator putem proceda cu ciclii. Mentionam ca mai trebuie sa obtinem si lca in timp logaritmic.

Complexitate finala: timp O((N + Q) * logN), memorie O(N * logN) (pentru precalcularea necesara pentru lca).

Solutia problemei Palatulvoltaic