Soluţia problemei Ordonare

10 puncte O(n^n)

Putem, folosind bactracking, sa generam toate mutarile intr-o vecinatate a punctelor (-3-n, 3+n) poate fi suficient tinand cont ca numerele sunt in intervalul (-3,3).

20-30 de puncte O(n^4)

Putem incerca sa alegem configuratia optima a punctelor folosind cuplaj maxim de cost minim.
Vom cupla obiectele cu puncte din intervalul (xmin-n,xmin+n) (se poate observa ca acest interval este suficient) cu un cost egal cu lungimea segmentului dintre pozitia initiala si cea finala)

40 de puncte O(n*valmax)

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]}

60 de puncte O(n*n)

Putem optimiza solutia de 40, cu urmatoarea observatie: punctul i va ajunge in final in intervalul (x(i)-(n+1)/2),x(i)+(n+1)/2), deci putem sa adaptam dinamica de la solutia anterioara, folosind pentru fiecare punct doar coordonatele relevante. (si modificand usor recurenta, deoarece intervalele pentru 2 puncte consecutive nu vor corespunde neaparat)

O alta solutie se bazeaza pe urmatoarea observatie: avand sirul sortat de puncte, trebuie sa il transformam intr-un sir strict crescator. Acest lucru se poate realiza prin transformarea in urmatoarea problema:

Sa se transforme sirul v(i)=x'(i)-i intr-un sir (nu neaparat strict) crescator, unde x' este x sortat.

Aceasta problema se poate rezolva cu urmatoarea dinamica ( se observa ca doar coordonatele din sirul v sunt relevante ca pozitii finale):
dp(i)(j)- am transformat elementul i, in al j-lea element in ordine sortata din sirul v. (Recurenta este asemanatoare cu cea de la solutia de 40)

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