Inundatii
O prima observatie necesara in rezolvarea problemei este urmatoarea: putem rezolva problema independent pentru valorile X, Y si Z datorita functiei de distanta. Astfel, avem de rezolvat de fapt urmatoarea problema: Se da un sir de N numere intregi A1,A2...AN cu Ai > Ai+1, sa se gaseasca un sir de numere intregi B1,B2...BN cu Bi < Bi+1 care minimizeaza suma |Ai-Bi|. Vom rezolva astfel aceasta problema pentru X, Y si Z, la final adunand rezultatele.
Vom mai simplifica un pic problema, inlocuind restrictia Bi < Bi+1 cu Bi ≤ Bi+1 astfel: scadem din Ai valoarea i, rezolvam pentru ≤, si la final adunam i la loc in A si B.
Exemplu:
- A = (10, 7, 4, 1)
- Scadem i si obtinem A = (9, 5, 1, -3)
- Gasim un B optim care respecta Bi ≤ Bi+1. Sunt mai multe solutii posibile, vom lua B = (5, 5, 5, 5)
- Adunam la loc i si obtinem ca solutia este B = (6, 7, 8, 9)
Se poate observa ca pentru a obtine rezultat optim pentru problema simplificata, B va avea valori egale. Daca privim valorile din A si valoarea din B pe care o cautam ca puncte pe axa, putem recunoaste problema clasica a oficiului postal in 1 dimenisune (se gaseste si in Cormen la capitolul de Statistici si ordine). Putem trage imediat concluzia ca valoarea din B pe care o cautam va fi mediana lui A (nu conteaza pe care o luam cand N e par). Valorile din A sunt sortate descrescator (si dupa scadere), deci putem determina mediana in O(1).
O solutie alternativa foloseste cautare ternara in O(N*log1.5(N)). Pentru sirul A de mai sus fie functia f:[AN, A1] -> R, cu f(x) costul obtinerii din inegalitatile A1 > .. > Ai >= x >= Ai+1 > .. > AN pe urmatoarele A1 < .. < Ai <= x <= Ai+1 < .. < AN cu A2 = A1 + 1, .. AN = A1 + (N-1) pentru minimalitate. Functia f indeplineste proprietatea necesara pentru aplicarea cautarii ternare: exista un X astfel inca functia descreste pe intervalul [AN, X] si isi schimba monotonia pe [X, A1]. Pentru determinarea acestui punct folosim cautarea ternara si in final rezultatul va fi f(X).
