De dorul intalnirilor care aveau loc in anii mai darnici in concursuri onsite, simt sa va impartasesc cateva idei, vechi si (mai ales) noi, de rezolvare a unor cerinte. As dori sa deschid o discutie tehnica inspirata de noile solutii eficiente descoperite la problemele Nave (in varianta 'initiala':problema/naveplanare sau 'de actualitate':nave_interdimensionale) si 'Ordonare':problema/ordonare. Mi se ofera astfel ocazia sa implic intreaga comunitate: am structurat postarea in asa fel incat fiecare pasionat, indiferent de experienta sa in algoritmica, sa gaseasca o idee deosebita si o cerinta care sa il intrige. Mai mult: cu cat veti dori sa studiati mai adanc subiectul propus, cu atat mai multe lucruri frumoase veti descoperi. Pentru a nu va incurca din a gasi singuri tainele acestea, am ascuns prin linkuri orice cuvinte si referinte la detaliile tehnice ale solutiilor.

De dorul intalnirilor care aveau loc in anii mai darnici in concursuri onsite, simt sa va impartasesc cateva idei, vechi si (mai ales) noi, de rezolvare a unor cerinte. As dori sa deschid o discutie tehnica inspirata de noile solutii eficiente descoperite la problemele Nave (in varianta 'initiala':problema/naveplanare sau 'de actualitate':problema/nave_interdimensionale) si 'Ordonare':problema/ordonare. Mi se ofera astfel ocazia sa implic intreaga comunitate: am structurat postarea in asa fel incat fiecare pasionat, indiferent de experienta sa in algoritmica, sa gaseasca o idee deosebita si o cerinta care sa il intrige. Mai mult: cu cat veti dori sa studiati mai adanc subiectul propus, cu atat mai multe lucruri frumoase veti descoperi. Pentru a nu va incurca din a gasi singuri tainele acestea, am ascuns prin linkuri orice cuvinte si referinte la detaliile tehnice ale solutiilor.

h3. Enunturile
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

h3. Ordonare: $O(N)$, fara reducere

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

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!

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.

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':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$

==user(user="freak93" type="tiny")== a gasit un algoritm eficient care gaseste raspunsul pentru $K = 1$, apoi adapteaza structura pentru $K = 2$, si tot asa, pana ce determina raspunsul pentru toate valorile lui $K$, pana la $K = N$. Va recomand sa va ganditi cum se poate obtine o solutie atat de indestulatoare, dar, pentru moment, va pun linkuri doar la o sursa in 'Rust':job_detail/2652599?action=view-source si la cateva hinturi: '1':nave-bunicu-hint1, '2':nave-bunicu-hint2, '3':nave-bunicu-hint3, '4':nave-bunicu-hint4.

==user(user="freak93" type="tiny")== a gasit un algoritm eficient care gaseste raspunsul pentru $K = 1$, apoi adapteaza structura pentru $K = 2$, si tot asa, pana ce determina raspunsul pentru toate valorile lui $K$, pana la $K = N$. Va recomand sa va ganditi cum se poate obtine o solutie atat de indestulatoare, dar, pentru moment, va pun linkuri doar la o 'sursa in Rust':job_detail/2652599?action=view-source si la cateva hinturi: '1':descriere/nave/bunicu-hint1, '2':descriere/nave/bunicu-hint2, '3':descriere/nave/bunicu-hint3, '4':descriere/nave/bunicu-hint4.

Pana acum deja am avea cele mai bune solutii la care puteam spera la ambele probleme, dar sunt foarte diferite intre ele. Exista, totusi, un algoritm, care se poate folosi de faptul ca problemele sunt asa de asemanatoare, si, dupa ce face reducerea problemei Ordonare la un subtask al problemei Nave, obtine:
h3. $O(N logN)$ la Nave & adaptabila sa obtina $O(N)$ la Ordonare

Punctul culminant al postarii - si motivul principal pentru care ea exista - este solutia la Nave a lui ==user(user="retrograd" type="tiny")==. Tin sa mentionez ca este foarte diferita de toate celelalte. 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.

Punctul culminant al postarii - si motivul principal pentru care ea exista - este solutia la Nave a lui ==user(user="retrograd" type="tiny")==. Tin sa mentionez ca este foarte diferita de toate celelalte.
 
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':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.

private

protected

54522