Mai intai, cateva notatii:

  • A = sirul din input (va amintesc ca e sortat)
  • B = sirul sortat, la finalul modificarilor intr-o solutie optima (numar minim de operatii) oarecare
  • C = sirul echivalent, cu valori intre 0 si 2N, pe care vrem sa il returnam (tot sortat)
  • u[i] = upper bound pentru valoarea de pe pozitia i in B (nu neaparat cel mai mic upperbound, ca nu vrem sa analizam toate sirurile B)
  • l[i] = lower bound pentru valoarea de pe pozitia i in B (asemenea, nu ne trebuie o valoare maxima)

Sa presupunem ca exista o metoda de a obtine niste valori sensibile (obraz fin, de bun simt, adica nu toate u[i] = INF si l[i] = -INF de exemplu) pentru cele doua siruri.

Claim:

  • Daca u[i] ≥ l[i+1], diferenta intre C[i] si C[i+1] trebuie sa fie aceeasi cu diferenta intre A[i] si A[i+1].
  • Daca u[i] < l[i+1], diferenta poate fi mai mica, atata timp cat C[i+1] - C[i] > l[i+1] - u[i]

Claimul acesta, odata ce sunteti de acord cu el (adica dupa ce il demonstrati!) ne spune, de fapt, cum sa construim, una cate una, valorile din sirul C (pornim cu prima valoare din sir egala cu 0).

Daca ultima valoare din C va fi, asa cum se cere, ≤ 2N, nu mai depinde decat de cat de strict sunt calculate sirurile u si l. Din fericire, e suficient sa folosim un algoritm simplu, liniar, probabil incadrabil la categoria greedy, pentru a rezolva asta. Desigur, vom calcula doar sirul u, intrucat calculul sirului l se face echivalent. Si daca tot suntem la interviu, straduiti-va sa faceti o functie pe care sa o apelati de doua ori: nu cred ca i-ar placea cuiva sa vada cum rescrieti codul cu brutalitate fara tact.

Vom presupune, cand il calculam pe u, ca solutia optima nu foloseste niciodata operatia de decrementare. Poate ca exista un sir B care este obtinut asa, probabil ca in majoritatea cazurilor interesante nu se intampla asta, dar e clar ca asa vom obtine un upper bound, si, intuitiv cel putin, suficient de strict.

Parcurgem sirul A de la stanga la dreapta si, la pozitia i fiind, ne uitam daca:

  • u[i - 1] < A[i], caz in care alegem u[i] = A[i]
  • u[i - 1] ≥ A[i], caz in care alegem u[i] = u[i - 1] + 1

Ramane sa demonstrati ca aceste siruri u si l fac promisiunea ca ultima valoare din C este ≤ 2N.