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>
In imagine avem x1 = 1, x2 = 5, x3 = 2, x4 = 3, x5 = 4.

Ce legatura are problema de mai sus cu problema noastra originala?
h2. 'Petrecere2':problema/petrecere2

Ce legatura are problema de mai sus cu problema noastra originala? Daca fac interschimbari numai cu elementul 1, problema se reduce la cea de sus. (costul unei operatii este min(1, x) = 1). Vom considera 4 cazuri diferite (care acopera defapt toata problema):
 
Caz 1. Lungimea ciclului curent este 1 (punct fix). In acest caz, ciclul este deja sortat, costul sortarii lui fiind 0.
Caz 2. Consideram un ciclu x1, x2, ..., xn, in care x1 = 1. Costul sortarii acestui ciclu este n - 1 (aceasta este exact problema de mai sus, deoarece la fiecare pas voi face interschimbari cu elementul 1).
Caz 3. (Caz particular, corespunzator testului 7) Avem un ciclu x1, x2, iar x1 = 2. Voi face pur si simplu swap(x1, x2), avand costul 2.
Caz 4. Avem un ciclu x1, x2, ..., xn si x1 este diferit de 1. Costul sortarii acestui ciclu este n + 1. Sa presupunem ca perm(1) = 1 (adica am rezolvat intai cazul 2). Fac intai swap(1, xn). Apoi fac algoritmul de la cazul 2. (in total n - 1 pasi). Apoi fac swap(1, x1). Astfel, sunt in total n + 1 operatii. Pentru a intelege mai bine, am mai luat un exemplu mai jos. De remarcat ca daca am aplica cazul acesta si pentru rezolvarea cazului 3, am obtine costul 3, care este incorect (cum am aratat mai sus, pot sorta cazul 3 numai cu costul 2). Pentru n >= 3, acest caz sorteaza optim, indiferent de permutare.
 
<tex>
\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 4 & 2 & 3
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 &2  &3  &4 \\
2 &4  &1  &3
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 & 3 &4 \\
2 & 4 & 3 &1
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 & 3 &4 \\
2& 1 & 3 & 4
\end{pmatrix}
\rightarrow
\begin{pmatrix}
1 & 2 &3  &4 \\
 1& 2 &3  & 4
\end{pmatrix}
</tex>
 
Mai trebuie mentionat ca complexitatea algoritmului este data de complexitatea descompunerii in cicluri, care se face in O(N).
 
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