h1. 'Soluţia':incalzire2020/solutii/ordonare problemei 'Ordonare':problema/ordonare

h1(#ordonare). 'Soluţia':incalzire2020/solutii/ordonare problemei 'Ordonare':problema/ordonare

h3. 10 puncte $O(n^n)$

Solutia de $40$ este bazata pe urmatoarea observatie: daca sortam punctele, nu vom avea niciodata 2 puncte $i,j$ pentru care $x(i)<x(j)$ sa ajunga in solutia finala la coordonate $x'(i)>x'(j)$ (nu ar aduce niciun beneficiu sa le schimbam ordinea relativa). Prin urmare, daca sortam punctele, acestea vor trebui ca in final sa formeze un sir strict crescator, obtinut cu operatiile enumerate.
Stiind ca punctele vor fi in intervalul $(xmin-n,xmin+n)$ in final, putem sa facem o dinamica $dp[i][j]$ avand urmatoarea semnificatie: am procesat primele $i$ puncte in ordinea sortata, iar ultimul din ele se afla la coordonata cel mult egala cu $j$. Recurenta va fi:

* $dp[i][j]=min{dp[i-1][j-1]+|x[i]-j|,dp[i][j-1]}

* $dp[i][j]=min{dp[i-1][j-1]+|x[i]-j|,dp[i][j-1]}$

h3. 60 de puncte $O(n*n)$

h3. 100 de puncte $O(nlogn)$

A doua solutie de mai sus, avand o forma mai simpla, poate fi optimizata. Acest lucru poate fi facut cu 'slope trick':https://codeforces.com/blog/entry/47821

A doua solutie de mai sus, avand o forma mai simpla, poate fi optimizata. Acest lucru poate fi facut cu 'slope trick':https://codeforces.com/blog/entry/47821
 
Nota: A mai fost facuta publica o explicare a 'slope trick-ului':https://codeforces.com/blog/entry/77298

private

protected