h1(#niciomare). 'Solutia':algoritmiada-2019/runda-maraton/solutii/niciomare problemei 'Niciomare':problema/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: !https://wcipeg.com/wiki/Convex_hull_trick!. Nu este nevoie sa stiti varianta complet dinamica a batch-ului pentru solutia finala.

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':https://wcipeg.com/wiki/Convex_hull_trick. Nu este nevoie sa stiti varianta complet dinamica a batch-ului pentru solutia finala.

h2. Pentru 30 de puncte

h2. Pentru 60 de puncte.

Pentru 60 de puncte, observam ca putem optimiza calcularea recurentei dinamicii la complexitatea de $O(log^2^(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 (!https://cp-algorithms.com/geometry/convex_hull_trick.html!).

Pentru 60 de puncte, observam ca putem optimiza calcularea recurentei dinamicii la complexitatea de $O(log^2^(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':https://cp-algorithms.com/geometry/convex_hull_trick.html).

h2. Pentru 70 de puncte.