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: http://pastebin.com/BH2uir8P

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: http://pastebin.com/ARRudC7t

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: http://pastebin.com/uKm4TvN2

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

h2. 'Petrecere2':problema/petrecere2

h2. 'Petrecere2':problema/petrecere2
 
Aceasta a fost problema grea a setului. Ea a fost rezolvata corect doar de 8 concurenti. Cu toate astea, problema nu era atat de grea odata ce se faceau niste observatii cheie. Codarea solutiei trebuia facuta cat mai simplu posibil si aici, altfel puteau aparea buguri care sa compromita toata problema.
 
Pentru inceput, putem considera fiecare persoana un nod intr-un graf si fiecare relatie o muchie neorientata in graf. Daca tipul relatiei era 0, vom numi muchia muchie de tip 0, altfel muchia va fi de tip 1. Problema cere o colorare a grafului. Vom spune ca un nod are culoare alba daca persoana corespunzatoare lui vine la petrecere si neagra daca nu vine. In exemplu, nodurile 1 si 2 sunt albe si nodul 3 este negru.
 
Observatia cheie care rezolva problema este ca daca stiu culoarea unui nod x pot afla culoarea tuturor nodurilor din componenta conexa a lui x. Pentru asta sa analizam mai atent tipul muchiilor:
 
* O muchie de tip 0 dintre doua noduri x si y arata ca x si y au aceeasi culoare. Sa presupunem ca x este alb. Persoana X ar veni la petrecere numai daca toate persoanele cu care se afla in relatii de tip 0 ar veni. Implicit, persoana Y trebuie sa vina, deci culoarea lui Y este tot alb. Acum, daca x ar avea culoarea neagra, Y este obligat sa aiba culoarea neagra si el. Rationamentul este asemanator: Y vine la petrecere doar daca vine si X, cum X nu vine, nici Y nu vine.
* O muchie de tip 1 dintre doua noduri x si y arata ca x si y au culori diferite. Presupun si aici ca x e alb. Daca x vine la petrecere, y nu va veni (conform definitiei relatiei de tip 1). De asemenea, daca x nu vine, y trebuie sa vina ("Paftenie mai stie ca daca 2 prieteni de-ai sai se afla in relatia de dusmanie, trebuie neaparat sa il invite pe unul din ei altfel vor fi amandoi suparati.")
 
De aici se contureaza ideea algoritmului. Pornim dintr-un nod arbitrar, presupunem ca el are culoare alba. Apoi aflam toate nodurile din componenta conexa a nodului ales (se poate face prin parcurgeri precum BFS si DFS) si pentru fiecare nod y descoperit dintr-un nod x vom actualiza culoarea lui y in functie de culoarea lui x si tipul muchiei dintre x si y. Daca nodul ales arbitrar ar avea culoarea neagra, tot ce s-ar intampla ar fi ca nodurile albe din componenta conexa sa devina negre si nodurile negre sa devina albe. (Las tema de gandire pentru cititori demonstrarea acestei proprietati). Astfel, e nevoie sa parcurg graful doar pentru culoarea alba initiala, pentru culoarea neagra se poate afla prin contrast.
 
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