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).