Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-03-21 23:16:17.
Revizia anterioară   Revizia următoare  

Autor: stud. Cosmin Tututnaru, Universitatea „Babeş-Bolyai”, Cluj-Napoca
Descrierea soluţiei (Cosmin Tutunaru)

Soluţie – 100 pct
Putem descompune problema pe OX şi OY, având în vedere că mişcările sunt independente. În acest fel putem sorta separat toate valorile X şi toate valorile Y.
În continuare avem de rezolvat următoarea problema: având un vector V sortat, să se determine numărul minim de operaţii necesare astfel încât să avem minim K valori distincte în el. O operaţie înseamna creşterea/scăderea cu 1 a oricărui element din vector.

Vom folosi următoarea dinamică:
DP = numărul minim de operaţii necesare pentru a avea exact j poziţii distincte formate din primele i numere, iar numarul de pe poziţia i are orice valoare din intervalul [-inf, k]
DP = min(
DP + abs(V[i] - j), “Vom creste numarul de elemente distincte cu 1, deci va trebui sa ducem elementul v[i] la valoarea j”
● min(DP, DP)
);

Solutia va fi minimul dintre toate DP+size(v)))
Răspunsul la problema va fi suma acestor doua minime (pentru X şi pentru Y).
Complexitate: O(N*N*K)
O altă soluţie care obtine 100 de puncte se poate implementa cu flux.