Nave Ordonate

Alexandru Petrescu
28 septembrie 2020

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 sau de actualitate) si 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.

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.

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), si vom analiza solutiile plecand din acest punct.

Intrepatrunderea Cerintelor

Ce nu am mentionat inca este marimea valorilor din sir. In problema Ordonare, ele sunt, in modul, mai mici ca 10⁹. Dincolo, desi in enunt scrie 10⁴, voi creste dificultatea problemei si voi spune ca sunt restrictionate sa fie maxim 2N. Practic, problema Ordonare pare mai complicata deoarece valorile pot fi mai mari.

Dintr-o alta perspectiva - mai exact, ignorand faptul ca limitele pentru valori sunt diferite - Ordonare este o subproblema a cerintei de la Nave: daca facem un subtask al problemei Nave in care garantam K = N, obtinem exact enuntul de la Ordonare.

Reducerea

Acum vom face o transformare a problemei Ordonare in asa fel incat sa devina cu totul o subproblema a noului enunt de la Nave. Tot ce ne trebuie este un algoritm (daca se poate, liniar, ca sa fim siguri ca am facut reducerea fara sa afectam in vreun fel complexitatea finala) care sa rezolve urmatoarea problema:

Se da un sir de N numere intregi cu valori oricat de mari. Sa se construiasca un sir de N numere cu valori intre 0 si 2N care sa fie echivalent cu primul, din punct de vedere al cerintei problemei Ordonare.

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 cand va mai poticniti.

Cateva solutii posibile

Dupa cum puteti intui din subtaskurile problemelor, exista multe solutii, de diverse complexitati, care le rezolva. Puteti vedea, in aceste linkuri, editorialele de la problema Nave Planare, respectiv Interdimensionale, precum si de la Ordonare. Cu toate acestea, discutia care urmeaza nu se foloseste decat intr-o mica masura de aceste descrieri.

Ordonare: O(N), fara reducere

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.

Puteti gasi aici 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.

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

Adrian Budau •freak93 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 si la cateva hinturi: 1, 2, 3, 4.

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:

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 Lucian Bicsi •retrograd. 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, 2, 3, 4, 5, 6), un mic articol care merge mana in mana cu indiciile, precum si doua surse foarte asemanatoare, bine comentate si codate cat mai clar. Prima mi se pare mai intuitiva, iar a doua (recomand text-compare.com) urmeaza ceva mai indeaproape implementarea originara 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. 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.