Dandu-se un sir de $N$ numere intregi, numim $operatie$ schimbarea uneia (la alegerea noastra care anume) dintre valorile sirului, fie ea $x$, in $x - 1$ sau $x + 1$ (la alegerea noastra).
Pe scurt, problema Ordonare cere gasirea numarului minim de $operatii$ pentru a transforma sirul dat intr-unul care are toate elementele distincte.

Problema Nave, *spoiler*, cere ceva asemanator: dandu-se si un numar pozitiv $K ≤ N$, gasiti numarul minim de $operatii$ pentru a transforma un sir dat intr-unul care are cel putin $K$ elemente distincte. Adica numarul de valori care apar cel putin o data in sirul obtinut este cel putin $K$. Daca veti citi enuntul, totusi, veti vedea ca pare mai complicat decat ce spun aici, deoarece sirul din input e de perechi de numere si operatiile sunt 2-dimensionale. Incercati sa demonstrati ca simplificarea pe care am facut-o este justificata. Cand va poticniti, aruncati un ochi la 'hint':hint-de-ce-putem-simplifica-enuntul-la-nave.

Problema Nave, *spoiler*, cere ceva asemanator: dandu-se si un numar pozitiv $K ≤ N$, gasiti numarul minim de $operatii$ pentru a transforma un sir dat intr-unul care are cel putin $K$ elemente distincte. Adica numarul de valori care apar cel putin o data in sirul obtinut este cel putin $K$. Daca veti citi enuntul, totusi, veti vedea ca pare mai complicat decat ce spun aici, deoarece sirul din input e de perechi de numere si operatiile sunt 2-dimensionale. Incercati sa demonstrati ca simplificarea pe care am facut-o este justificata. Cand va poticniti, aruncati un ochi la 'hint':descriere/nave/hint-de-ce-putem-simplifica-enuntul.

*Pentru restul discutiei, vom presupune ca sirul este gata citit si gata sortat* (putem sorta inputul fie cu $std::sort$, fie, de dragul complexitatii, dar intinand simplitatea implementarii, cu 'radix sort':problema/radixsort), si vom analiza solutiile plecand din acest punct.

Ce ne dorim este un fel de normalizare, care sa fie justificata in contextul cerintei noastre. Spre exemplu, sirul $5 38 38 38 40 40 40 43 43 43$ se poate normaliza la $0 15 15 15 17 17 17 20 20 20$, intrucat distantele relative dintre valori s-au pastrat, mai putin in cazul $5 - 38$, care a devenit $0 - 15$, doar ca aceasta schimbare nu poate afecta rezolvarea problemei Ordonare: orice operatii am face pe valorile $≥ 38$ (respectiv $15$) intr-o solutie optima, nu se vor putea apropia de valoarea $5$ (respectiv $0$) (care e clar ca in solutia optima nu va suferi vreo modificare).

Va invit sa rezolvati si sa implementati problema aceasta. As zice ca e excelenta pentru un interviu de algoritmica si programare - aceasta afirmatie nu mi-ar fi trecut prin cap acum un an, dar asa e cand cresti :-) Va puteti ghida dupa 'aceasta descriere a solutiei':descriere-reducere cand va mai poticniti.

Va invit sa rezolvati si sa implementati problema aceasta. As zice ca e excelenta pentru un interviu de algoritmica si programare - aceasta afirmatie nu mi-ar fi trecut prin cap acum un an, dar asa e cand cresti :-) Va puteti ghida dupa 'aceasta descriere a solutiei':descriere/ordonare/reducere cand va mai poticniti.

h2. Cateva solutii posibile

Solutia oficiala (care nu face reducerea de care am vorbit mai devreme) are complexitatea $O(N logN)$. Cu toate acestea, particularitile problemei fac in asa fel incat sa pastram operatiile dar sa schimbam structura de date si sa obtinem complexitate liniara!

Am pregatit un 'hint':... care va deslusi care este structura aceasta de date. Incercati sa va prindeti cum se poate folosi. Am scris si 'un scurt articol':... care descrie noua solutie.

Am pregatit un 'hint':descriere/ordonare/wow-ce-poate-fi-asa-de-smecher care va deslusi care este structura aceasta de date. Incercati sa va prindeti cum se poate folosi. Am scris si 'un scurt articol':descriere/ordonare/prea-usor care descrie noua solutie.

Puteti gasi 'aici':job_detail/2652506?action=view-source o implementare usoara a ideii. Problema e ca are comportament patrati pe anumite teste. Sursa se poate modifica usor, asa cum puteti vedea in aceasta 'poza':... la un text-compare cu implementarea corecta, pe care o puteti gasi 'aici':job_detail/2653564?action=view-source.
 
Solutia oficiala (care nu face reducerea de care am vorbit mai devreme), deoarece foloseste ...['click daca vrei sa aflii numele structurii de date':afla-cu-ce-se-codeaza-slope-trick], are complexitatea $O(N logN)$. Cu toate acestea, particularitile problemei fac in asa fel incat sa pastram operatiile dar sa schimbam structura de date si sa obtinem complexitate liniara! 'click daca vrei sa aflii ce structura de date e asa de smechera':wow-ce-poate-fi-asa-de-smecher
 
Puteti citi 'un scurt articol':ordonare-prea-usor care extinde editorialul cu aceasta metoda. 'Aici':job_detail/2653564?action=view-source puteti vedea o posibila implementare. O alta 'sursa':job_detail/2652506?action=view-source arata varianta simplificata a solutiei (recomand citirea acesteia mai intai), dar care are comportament patratic pe unele teste. Pentru convenienta, pun un 'link':my-text-compare-ordonare cu o poza la un text-compare intre cele 2 submisii, pentru a fi si mai clar.

Puteti gasi 'aici':job_detail/2652506?action=view-source o implementare usoara a ideii. Problema e ca are comportament patrati pe anumite teste. Sursa se poate modifica usor, asa cum puteti vedea in aceasta 'poza':descriere/ordonare/my-text-compare la un text-compare cu implementarea corecta, pe care o puteti gasi 'aici':job_detail/2653564?action=view-source.

h3. Nave: $O(N logN)$, raspunde pentru toate valorile lui $K$

Mai intai, vom face o transformare a sirului dat, intr-o reprezentare echivalenta, si anume un sir de $2N$ frecvente, $input[i]$ = numarul de valori egale cu $i$ din sirul dat.

Pentru a va ghida spre patrunderea ei, am pregatit o serie de hinturi ('1':nave-lucian-hint1, '2':nave-lucian-hint2, '3':nave-lucian-hint3, '4':nave-lucian-hint4, '5':nave-lucian-hint5, '6':nave-lucian-hint6), 'un mic articol':nave-prea-usor care merge mana in mana cu indiciile, precum si doua surse foarte asemanatoare, bine comentate si codate cat mai clar. 'Prima':job_detail/2653120?action=view-source mi se pare mai intuitiva, iar 'a doua':job_detail/2653119?action=view-source (recomand "text-compare.com":https://text-compare.com/) urmeaza ceva mai indeaproape 'implementarea origina{*r*}a':job_detail/2651731?action=view-source a lui Lucian.

Pentru a va ghida spre patrunderea ei, am pregatit o serie de hinturi ('1':descriere/nave/lucian-hint1, '2':descriere/nave/lucian-hint2, '3':descriere/nave/lucian-hint3, '4':descriere/nave/lucian-hint4, '5':descriere/nave/lucian-hint5, '6':descriere/nave/lucian-hint6), 'un mic articol':descriere/nave/prea-usor care merge mana in mana cu indiciile, precum si doua surse foarte asemanatoare, bine comentate si codate cat mai clar. 'Prima':job_detail/2653120?action=view-source mi se pare mai intuitiva, iar 'a doua':job_detail/2653119?action=view-source (recomand "text-compare.com":https://text-compare.com/) urmeaza ceva mai indeaproape 'implementarea origina{*r*}a':job_detail/2651731?action=view-source a lui Lucian.

*Odata ce intelegeti solutia aceasta*, puteti rezolva (si o puteti privi ca pe o tema) si problema Ordonare, doar ca in timp liniar (reminder: dupa ce faceti reducerea!). In caz ca nu-i dati de cap, iata un 'indiciu':de-la-nave-la-ordonare. Avantajul aici e ca multe detalii la care trebuia sa aveti grija la Nave nu mai conteaza, deci sursa e mai lejer de scris.

*Odata ce intelegeti solutia aceasta*, puteti rezolva (si o puteti privi ca pe o tema) si problema Ordonare, doar ca in timp liniar (reminder: dupa ce faceti reducerea!). In caz ca nu-i dati de cap, iata un 'indiciu':descriere/ordonare/de-la-nave. Avantajul aici e ca multe detalii la care trebuia sa aveti grija la Nave nu mai conteaza, deci sursa e mai lejer de scris.

Va recomand sa si implementati aceste idei. Nu numai ca doar asa va puteti asigura ca ati inteles intru totul fenomenul (si va spun asta din proprie experienta), dar este o provocare fascinanta sa duci aceste surse la capat, adica la $100$ de puncte.