elfus/editorial-runda-9

Editorial runda 9

Pentru sensul rosu, cum x < y, locatarul va trece intotdeauna prin cladirile x + 1, x + 2, ..., y - 1, y. Numarul acestora este y - (x + 1) + 1 = y - x. Pentru sensul albastru, locatarul va trece prin cladirile x - 1, x - 2, ..., 2, 1, 2 * N, 2 * N - 1, ..., y + 1, y. Pentru a calcula numarul de cladiri pe care le parcurge locatarul in acest caz, vom calcula intai cata distanta trebuie sa parcurga pentru a ajunge la cladirea 2 * N, dupa aceea ce distanta trebuie sa mai parcurga de la cladirea 2 * N la cladirea y. Pentru a ajunge la cladirea 2 * N, locatarul trebuie sa treaca pe langa cladirile x - 1, x - 2, ..., 1 si 2 * N.
Pentru a ajunge la coordonata 1, el trebuie sa parcurga x - 1 cladiri, iar pentru a ajunge la de la 1 la 2 * N mai trebuie sa mearga 1 unitate de distanta. Asadar, distanta dintre x si 2 * N este x. Acum, ppornind din 2 * N, locatarul trebuie sa ajunga in y. El parcurge cladirile 2 * N - 1, 2 * N - 2, ..., y + 1, y. In total, aceste cladiri sunt in numar de 2 * N - 1 - y + 1 = 2 * N - y. Deci distanta totala pentru sensul albastru este x + 2 * N - y. Evident, distanta minima dintre cladirea x si cladirea y va fi acum min(y - x, x + 2 * N - y).

Formula de baza folosita pentru rezolvarea problemei a fost ca numarul de numere dintr-o multime {A, A + 1, A + 2, .., B - 1, B} este B - A + 1. Complexitatea algoritmului este O(N) timp si O(1) memorie. Pentru o sursa de referinta, puteti consulta sursa mea din arhiva Monthly:

Formula de baza folosita pentru rezolvarea problemei a fost ca numarul de numere dintr-o multime {A, A + 1, A + 2, .., B - 1, B} este B - A + 1. Complexitatea algoritmului este O(N) timp si O(1) memorie.

h2. 'Traseu2':problema/traseu2

Tot ce mai ramane de facut este sa verificam daca drumul ales este valid. Un drum este valid cand orice 2 elemente consecutive din el sunt vecine in matrice. Fie (x0, y0) o pozitie oarecare si (x1, y1) pozitia urmatoare din drum. Daca (x1, y1) nu este vecin al lui (x0, y0), drumul nu este valid. Cum vedem daca 2 pozitii (x0, y0) si (x1, y1) sunt vecine? O prima idee ar fi sa generam toti cei 8 vecini ai lui (x0, y0) ssi sa verificam daca (x1, y1) apare printre ei. O abordare mai rapida de scris ar fi sa observam ca (x0, y0) si (x1, y1) sunt vecine daca si numai daca <tex> \left | x0 - x1 \right | \leqslant 1 </tex> si <tex> \left | y0 - y1 \right | \leqslant 1 </tex>. Lasam demonstratia acestei proprietati ca tema cititorului.

O sursa care implementeaza ideea de mai sus este a lui Ciprian Olariu. Postez aici codul sursa:

O sursa care implementeaza ideea de mai sus este a lui Ciprian Olariu.

h2. 'Intersort':problema/intersort

\end{pmatrix}
</tex>

Mai trebuie mentionat ca complexitatea algoritmului este data de complexitatea descompunerii in cicluri, care se face in O(N). Ca sursa de referinta voi folosi sursa mea din Arhiva Monthly:

Mai trebuie mentionat ca complexitatea algoritmului este data de complexitatea descompunerii in cicluri, care se face in O(N).

h2. 'Petrecere2':problema/petrecere2

Mai departe, calculez pentru nodul ales arbitrar mai sus daca e mai bine sa-l colorez in alb sau negru. Evident, o colorare se considera buna cand aduce un numar maxim de noduri albe. Fie N = nr de noduri din componenta conexa curenta si white = numarul de noduri albe. Pentru o colorare pornind cu culoarea initiala alba, numarul de noduri albe va fi white. Daca am porni cu negru initial, numarul de noduri negre ar fi white si numarul de noduri albe ce mai ramane din cele N noduri ale componentei (N - white). Astfel, pentru o componenta conexa, la solutie se va adauga valoare max(white, N - white). Dupa aceea componenta conexa se elimina si algoritmul se reia.

Timpul de rulare al algoritmului este O(N + M). Practic, eliminarea unui nod se poate face in O(1) daca il marchez ca fiind vizitat, iar in timpul unei parcurgeri consider numai nodurile nevizitate. Ca sursa de referinta recomand sursa mea - parcurgerea grafului a fost facuta cu DFS pentru a scurta codul:

Timpul de rulare al algoritmului este O(N + M). Practic, eliminarea unui nod se poate face in O(1) daca il marchez ca fiind vizitat, iar in timpul unei parcurgeri consider numai nodurile nevizitate